Олимпиадные задачи по теме «Вспомогательная раскраска» - сложность 4-5 с решениями

Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.

В некоторых клетках доски 100×100 стоит по фишке. Назовём клетку <i>красивой</i>, если в соседних с ней по стороне клетках стоит чётное число фишек.

Может ли ровно одна клетка доски быть красивой?

В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет. <div align="center"><img src="/storage/problem-media/115497/problem_115497_img_2.gif"> </div>

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  2<i>N</i> + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  <i>N</i> + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.

Десять попарно различных ненулевых чисел таковы, что для каждых двух из них либо сумма этих чисел, либо их произведение – рациональное число.

Докажите, что квадраты всех чисел рациональны.

В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для каждых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).

В прямоугольную коробку с основанием <i>m</i>×<i>n</i>, где <i>m</i> и <i>n</i> – нечётные числа, уложены домино размера 2×1 так, что остался не покрыт только квадрат 1×1 (дырка) в углу коробки. Если доминошка прилегает к дырке короткой стороной, её разрешается сдвинуть вдоль себя на одну клетку, закрыв дырку (при этом открывается новая дырка). Докажите, что с помощью таких передвижений можно перегнать дырку в любой другой угол.

Можно ли прямоугольник $5 \times 7$ покрыть уголками из трёх клеток (т.е. фигурками, которые получаются из квадрата $2 \times 2$ удалением одной клетки), не выходящими за его пределы, в несколько слоёв так, чтобы каждая клетка прямоугольника была покрыта одинаковым числом клеток, принадлежащих уголкам?

Игроки <i>A</i> и <i>B</i> по очереди ходят конем на шахматной доске 1994×1994. Игрок <i>A</i> может делать только горизонтальные ходы, то есть такие, при которых конь перемещается на соседнюю горизонталь. Игроку <i>B</i> разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок <i>A</i> ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока <i>A</i> существует выигрышная стратегия.

Докажите, что существует такое натуральное число<i> n </i>, что если правильный треугольник со стороной<i> n </i>разбить прямыми, параллельными его сторонам, на<i> n² </i>правильных треугольников со стороной 1, то среди вершин этих треугольников можно выбрать1993<i>n </i>точек, никакие три из которых не являются вершинами правильного треугольника (не обязательно со сторонами, параллельными сторонам исходного треугольника).

Натуральные числа от 1 до <i>n</i> расставляются в ряд в произвольном порядке. Расстановка называется <i>плохой</i>, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются <i>хорошими</i>. Докажите, что количество хороших расстановок не превосходит 81^<i>n</i>.

На плоскости нарисована замкнутая самопересекающаяся ломаная. Она пересекает каждое свое звено ровно один раз, причём через каждую точку самопересечения проходят ровно два звена. Может ли каждая точка самопересечения делить оба этих звена пополам? (Нет самопересечений в вершинах и звеньев с общим отрезком.)

Ширина реки один километр. Это по определению означает, что от любой точки каждого берега можно доплыть до противоположного берега, проплыв не больше километра. Может ли катер проплыть по реке так, чтобы в любой момент расстояние до любого из берегов было бы не больше:

  а) 700 м?

  б) 800 м?

(Берега состоят из отрезков и дуг окружностей.)

Куб размером10×10×10 сложен из 500 чёрных и 500 белых кубиков в шахматном порядке (кубики, примыкающие друг к другу гранями, имеют различные цвета). Из этого куба вынули 100 кубиков так, чтобы в каждом из 300 рядов размером1×1×10, параллельных какому-нибудь ребру куба, не хватало ровно одного кубика. Докажите, что число вынутых чёрных кубиков делится на 4.

На рёбрах произвольного тетраэдра выбрано по точке. Через каждую тройку точек, лежащих на рёбрах с общей вершиной, проведена плоскость. Докажите, что если три из четырёх проведённых плоскостей касаются вписанного в тетраэдр шара, то и четвёртая плоскость также его касается.

Прямоугольный лист бумаги размером<i>a</i>×<i>b</i>см разрезан на прямоугольные полоски, каждая из которых имеет сторону 1 см. Линии разрезов параллельны сторонам исходного листа. Доказать, что хотя бы одно из чисел<i>a</i>или<i>b</i>целое.

Найдите необходимые и достаточные условия, которым должны удовлетворять числа <i>a, b</i>, α и β, чтобы прямоугольник размером <i>a</i>×<i>b</i> можно было разрезать на прямоугольники размером α×β. Например, можно ли прямоугольник размером 50×60 разрезать на прямоугольники размером

а) 20×15;   б) 5×8;   в) 6,25×15;   г)  <img align="absmiddle" src="/storage/problem-media/73679/problem_73679_img_2.gif">

Правильный 100-угольник разрезали на несколько параллелограммов и два треугольника. Докажите, что эти треугольники равны.

В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу даётся 3 очка, за поражение 0 очков, а в случае ничьей назначается дополнительное время, победитель которого получает 2 очка, а проигравший – 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее <i>N</i> матчей закончились дополнительным временем. Найдите наибольшее возможное значение <i>N</i>.

<i>Триангуляцией</i>многоугольника называют его разбиение на треугольники, обладающее тем свойством, что эти треугольники либо имеют общую сторону, либо имеют общую вершину, либо не имеют общих точек (т. е. вершина одного треугольника не может лежать на стороне другого). Докажите, что треугольники триангуляции можно раскрасить в три цвета так, что имеющие общую сторону треугольники будут разного цвета.

Плоскость раскрашена в семь цветов. Обязательно ли найдутся две точки одного цвета, расстояние между которыми равно 1?

Правильный треугольник разбит на <i>n</i>²одинаковых правильных треугольников (рис.). Часть из них занумерована числами1, 2,...,<i>m</i>, причем треугольники с последовательными номерами имеют смежные стороны. Докажите, что<i>m</i>$\le$<i>n</i>²-<i>n</i>+ 1.

Дан квадратный лист клетчатой бумаги размером100×100 клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами обязательно выходят на границу. Докажите, что кроме вершин квадрата найдется еще узел (внутри квадрата или на границе), не принадлежащий ни одной ломаной.

Можно ли доску размерами 4 × <i>N</i>обойти ходом коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?