24-Я НЕДЕЛЯ (6-Я НЕДЕЛЯ 3 ЧЕТВЕРТИ)
ПОЛУИНВАРИАНТЫ

1. На материке есть несколько стран, в каждой из которых правит либо партия правых, либо партия левых. Раз в месяц в одной из стран может поменяться власть. Это может произойти только в случае если в большинстве стран, граничащих с этой страной, правит другая партия. Докажите, что смены партий не могут продолжаться бесконечно.  

2. Шоколадка имеет размер 4×10 плиток. За один ход разрешается разломать один из уже имеющихся кусочков на два вдоль прямолинейного разлома. За какое наименьшее число ходов можно разбить всю шоколадку на кусочки размером в одну плитку? 

3. В стране дальтоников все города подняли над ратушами флаги — черно-синие либо бело-золотые. Каждый день жители узнают цвета флагов у соседей в радиусе 100 км. Один из городов, где у большинства соседей флаги другого цвета, меняет свой флаг на этот другой цвет. Докажите, что со временем смены цвета флагов прекратятся. 

4. На длинной скамейке сидели мальчик и девочка. К ним по одному подошли ещё 20 детей, и каждый из них садился между какими-то двумя уже сидящими. Назовем девочку отважной, если она садилась между двумя соседними мальчиками, а мальчика - отважным, если он садился между двумя соседними девочками. Когда все сели, оказалось, что мальчики и девочки сидят на скамейке, чередуясь. Сколько из них были отважными? 

5. Шеренга новобранцев стояла лицом к сержанту. По команде "налево" некоторые повернулись налево, а остальные - направо. Всегда ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось поровну новобранцев, обращенных к нему лицом? 

6. На плоскости даны 10 точек: несколько из них — белые, а остальные — чёрные. Некоторые точки соединены отрезками. Назовем точку особой, если более половины соединённых с ней точек имеют цвет, отличный от ее цвета. Каждым ходом выбирается одна из особых точек (если такие есть) и перекрашивается в противоположный цвет. Докажите, что через несколько ходов не останется ни одной особой точки.

Самая распространенная формулировка принципа Дирихле, как ни странно, связана с кроликами:

если в n клетках сидит n+1 кролик, то по крайней мере в одной клетке сидит не менее двух кроликов. 

Если в первую клетку посадить учеников, которые не сделали ни одной ошибки, во вторую - сделавших две ошибки и т.д., а в тринадцатую посадить Вову, то решить задачу можно опять методом от противного:

Пусть среди класса нет учеников, сделавших одинаковое количество ошибок. Тогда в каждой клетке максимум 2 ученика. Т.к. клеток всего 14 (в последней сидит один Вова), то суммарное количество учеников не может превышать 13*2+1=27 человек. Мы пришли к противоречию, т.к. диктант писало 30 ребят.

1. Можно ли разрезать квадрат 10 х 10 на прямоугольники 1 х  4? 

2. Отметьте на доске  8 х 8 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.  

3.  Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее? 

4. В каждой клетке доски в 5 х 5 клеток сидел жук. Затем каждый жук переполз на соседнюю (по стороне) клетку. Докажите, что осталась хотя бы одна пустая клетка. 

5. Дана доска в 19 х 19 клеток. На каждой клетке поставлено по шашке. Можно ли переставить шашки так, чтобы каждая шашка оказалась на соседней клетке (по горизонтали или по вертикали, но не диагонали)? 

6. Докажите, что плоскость можно раскрасить девятью красками так, что никакие две точки одного цвета не будут находиться на расстоянии 1 м друг от друга.