МАЛЫЙ МЕХМАТ МГУ

Кружок 10 класса

Принцип Дирихле (03.10.2009)

1.

На клетчатой бумаге отмечен прямоугольник размером 2×6 клеток. Можно ли раскрасить узлы клеток, лежащие на границе и внутри этого прямоугольника (всего их 21), в два цвета так, чтобы никакие четыре одноцветные точки не оказались в вершинах прямоугольника со сторонами, идущими вдоль линий сетки?

2.

Каждый из 1994 депутатов парламента дал пощёчину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, которые не выясняли отношений между собой указанным выше способом.

3.

Каждый голосующий на выборах вносит в бюллетень фамилии n кандидатов. На избирательном участке находится n + 1 урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе (n + 1)-го бюллетеня по одному из каждой урны найдётся кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.

4.

Можно ли клетки доски 5×5 покрасить в четыре цвета так, чтобы клетки, стоящие на~пересечении любых двух строк и любых двух столбцов, были покрашены не менее, чем в три цвета?

5.

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

6.

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

7.

На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает n точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает ему расстояние от этой точки до ближайшей неразгаданной. Если оно оказывается нулевым, то указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и проводить построения циркулем и линейкой. Докажите, что он может разгадать все выбранные точки менее, чем за (n + 1)² попыток.