Принцип дирихле План: Введение Различные формулировки принципа Дирихле

II. 3. Принцип Дирихле и геометрия
Задача 1. В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.
Решение: Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадёт, по крайней мере, три точки из 51 брошенной.
Задача 2. Внутри равностороннего треугольника со стороной 1см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5см.
Решение: Можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середину сторон. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».
Задача 3. В квадрате площадью S расположено 100 фигур, сумма площадей которых больше 99S. Доказать, что у всех этих фигур есть общая точка. Решение. Пусть S₁, S₂, . . . , S₁₀₀ - площади данных фигур, а , …, - площади фигур, дополняющих их до квадрата. Понятно, что . По условию S₁+S₂+. . .+S₁₀₀ > 99S, поэтому
+ + … + = (S- S₁)+ (S- S₂)+. . .+ (S- S₁₀₀) = 100S-(S₁+ S₂+. . .+ S₁₀₀) < 100S-99S = S.
Таким образом, сумма площадей дополняющих фигур меньше площади квадрата, и, значит, они не могут покрыть весь квадрат (по принципу Дирихле), т.е. найдётся точка, не принадлежащая ни одной из них. Тогда эта точка принадлежит каждой из исходных фигур и является искомой.
II. 4. Принцип Дирихле и комбинаторные задачи
Задача 1. Докажите, что в любой момент турнира по шашкам (в котором каждый встречается с остальными участниками по одному разу) найдется два игрока, сыгравшие одинаковое число партий.
Решение: Если в турнире k+1 участник, то количество сыгранных партий у каждого спортсмена меняется от 0 до k. Однако, если хотя бы у одного участника не сыграно ни одной партии. То ни у кого не может быть сыграно k партий (т. е. количество групп-k). Если же хотя бы один сыграл все k партий, то ни у кого не может быть 0. Если k+1 игрока распределять по k группам, то найдется группа, в которой не менее 2 игроков.