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

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

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

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

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

Можно ли прямоугольник $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> существует выигрышная стратегия.

Натуральные числа от 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.

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

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

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

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