Принцип крайнего

Задача 1

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

Решение

Все зайчата барабанить не могут, так как заведомо не будет барабанить зайчонок, которому достанется самый маленький барабан. С другой стороны, если дать этому же зайчонку и самые короткие палочки, то все остальные зайчата будут барабанить.

Задача 2

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

Доказательство

Если рядом с 16 стоит число x , то 16+116+x=a² 16+15 , откуда a²=25 и x=9 . Поэтому у 16 не может быть более одного соседа, и удовлетворяющее условию расположение чисел по кругу невозможно. Пример расположения в строку: 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8.

Задача 3

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

Решение

Возьмём учёного A, число друзей у которого максимально (если таких учёных несколько, возьмём любого из них); обозначим это число через N. Каждый из N друзей учёного A имеет хотя бы одного друга (A), не имеет более N друзей и никакие двое не имеют равного числа друзей. Следовательно, эти люди имеют 1, 2, 3, …, N друзей. В частности, один из них дружит только с A.

Задача 4

Рассматривается конечное множество M единичных квадратов на плоскости. Их стороны параллельны осям координат (разрешается, чтобы квадраты пересекались). Известно, что для любой пары квадратов расстояние между их центрами не больше 2.
Докажите, что существует единичный квадрат (не обязательно из множества M) со сторонами, параллельными осям, пересекающийся хотя бы по точке с каждым квадратом множества M.

Доказательство

Проведем ось абсцисс через самый нижний, а ось ординат – через самый левый центр квадрата. Тогда центры всех квадратов находятся в квадрате  [0, 2] × [0, 2].  Ясно, что квадрат с центром в точке  (1, 1)  пересекается со всеми.

Задача 5

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

Решение 1

Рассмотрим наибольшую группу A депутатов, в которой никто никого не бил. Тогда каждый из оставшихся депутатов попадает в группу B тех, кого били депутаты из A, либо в группу C тех,кто бил депутатов из A (иначе его можно было бы добавить к A, что противоречит её максимальности). Ясно, что в B депутатов не больше, чем в A. Но и в C депутатов не больше, чем в A, поскольку в ней никто никого не бил. Следовательно, в A не меньше 150 депутатов.

Решение 2

Согласно задаче 108403 депутатов можно разбить на три группы, в каждой из которых никто никого не бил. В наибольшей из них не меньше 150 депутатов.

Задача 6

Солдаты построены в две шеренги по n человек, так что каждый солдат из первой шеренги не выше стоящего за ним солдата из второй шеренги. В шеренгах солдат выстроили по росту. Докажите, что после этого каждый солдат из первой шеренги также будет не выше стоящего за ним солдата из второй шеренги.

 Решение

Обозначим через a₁,a₂,…,a_n рост солдат из первой шеренги в порядке убывания, аналогично обозначим через b₁,b₂,…,b_n рост солдат из второй шеренги в порядке убывания (те же обозначения используем и для самих солдат). Пусть условие задачи неверно. Тогда для некоторого k выполнено a_k>b_k. Это означает, что до перестраивания по росту солдат a_k мог стоять только перед одним из k-1 солдат b₁,b₂,…,b_k-1. То же самое справедливо и для солдат a₁,a₂,…,a_k-1, поскольку они не ниже солдата a_k. Итак, мы получили, что до перестраивания шеренг k солдат a₁,a₂,…,a_k могли стоять только перед k-1 солдатами b₁,b₂,…,b_k-1. Ясно, что это противоречие.

Задача 7

Давным-давно страной Тарнией правил царь Ятианр. Чтобы тарнийцы поменьше рассуждали, он придумал для них простой язык. Его алфавит состоял всего из шести букв: А, И, Н, Р, Т, Я, но порядок их отличался от принятого в русском языке. Словами этого языка были все последовательности, использующие каждую из этих букв по одному разу. Ятианр издал полный словарь нового языка. В соответствии с алфавитом первым словом словаря оказалось “Тарния”. Какое слово следовало в словаре за именем Ятианр?

Решение

В первом слове буквы расположены в алфавитном порядке: Т, А, Р, Н, И, Я. Для удобства занумеруем буквы в алфавитном порядке:  Т = 1,  А = 2,  Р = 3, Н = 4,  И = 5,  Я = 6.  Заменим каждое слово соответствующим шестизначным числом. Если слова расположены по алфавиту, то числа – в порядке возрастания. Слово Ятианр запишется числом 615243. За ним следует 615324, что соответствует слову Ятиран.

Задача 8

В команде сторожей у каждого есть разряд (натуральное число). Сторож N-го разряда N суток дежурит, потом N суток спит, снова N суток дежурит, N – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)

Решение

Задача 9

Докажите, что любой выпуклый многоугольник Ф содержит два многоугольника Ф₁ и Ф₂, которые не пересекаются и подобны Ф с коэффициентом подобия 1/2.

Решение

Задача 10

Докажите, что если многоугольник имеет несколько (больше двух) осей симметрии, то все они пересекаются в одной точке.

Решение