Задача 111. На квадратном поле 10 × 10 девять клеток 1 × 1 поросли бурьяном. После этого бурьян может распространиться на клетку, у которой не менее двух соседних клеток уже поросли бурьяном. Докажите, что тем не менее бурьян не сможет распространиться на все клетки.
Решение:
Рассмотрим один из частых полуинвариантов/инвариантов – периметр. Давайте посмотрим, как изменяется периметр всех клеток, которые поросли бурьяном, когда прорастает новая клетка. Возможны 4 случая (красным отметим новую клетку, а черным старые):
Значит полуинвариант такой: периметр рассматриваемой области не увеличивается. Периметр исходных клеток не больше чем 4·9=36, но периметр всего квадрата 40, что больше чем 36, поэтому весь квадрат зарасти не мог.
Задача 112. Убирая детскую комнату к приходу гостей, мама нашла 9 носков. Среди любых четырех носков хотя бы два принадлежали одному ребенку, а среди любых пяти носков не более трех имели одного хозяина. Сколько могло быть детей и сколько носков могло принадлежать каждому ребенку, если у каждого был хотя бы один носок?
Решение:
Если бы детей было больше трех, то можно было бы взять 4 носка, принадлежащих разным детям, и получить противоречие с тем, что среди любых четырех носков хотя бы два принадлежат одному ребенку. Итак, детей максимум трое. С другой стороны, каждому ребенку принадлежит не более трех носков (иначе можно было бы взять пять носков, из которых более трех принадлежат одному хозяину), а так как всего носков 9, то детей не более трех.
Итак, детей ровно трое и каждому принадлежат ровно три носка.
Задача 113. Докажите, что никакая прямая не может пересекать все три стороны треугольника (в точках, отличных от вершин).
Решение:
Прямая делит плоскость на две полуплоскости, которые будем считать клетками. Три вершины треугольника будем считать кроликами. По принципу Дирихле найдется клетка, в которой сидит по крайней мере два кролика, т.е. найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.
Задача 114. Можно ли сложить из двенадцати пентамино квадрат 8×8 с центральным отверстием 2×2?
Решение:
Ответ: да, можно.
Задача 115. В каждой клетке шахматной доски записано число. Оказалось, что любое число равно среднему арифметическому чисел, записанных в соседних (по стороне) клетках. Докажите, что все числа равны.
Решение:
Рассмотрим максимальное число 𝑛, если таких несколько, то любое. Тогда все соседи, чтобы их среднее арифметическое было равно 𝑛, должны быть сами равны 𝑛 (если есть число, которое строго меньше, тогда и среднее арифметическое будет меньше 𝑛). Так как соседи тоже являются максимальными, то рядом с ними числа тоже равны 𝑛. Таким образом, все числа в таблице равны 𝑛.
Задача 116. В круг радиуса 3 произвольным образом помещены несколько кругов, сумма радиусов которых равна 25. Доказать, что найдется прямая, которая пересекает не менее девяти из этих кругов.
Решение:
Спроектируем все круги на произвольный диаметр AB большого круга (AB = 6). Сумма длин проекций, очевидно, равна сумме диаметров кругов, т.е. 50. Поскольку 50 > 8AB, то на отрезке AB есть точка, принадлежащая проекциям по крайней мере девяти кругов. Прямая, проходящая через эту точку и перпендикулярная диаметру AB, - искомая.
Задача 117. Вася думает, что если площадь первого прямоугольника больше площади второго, а также периметр первого больше периметра второго, то из первого можно вырезать второй. Прав ли он?
Решение:
Из прямоугольника 1×100 нельзя вырезать квадрат 2×2.
Ответ: нет, не прав.
Задача 118. В школе 500 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение:
Предположим, что это не так, т. е. в каждый день года родились не более одного ученика школы. Тогда, поскольку всего дней в году 366 (будем рассматривать максимально возможное число дней в году, т. е. високосный год), всего учеников в школе не более 366, что противоречит условию. Следовательно, наше предположение неверно и, значит, в школе есть хотя бы два ученика, которые родились в один день года. (В этой задаче роль кроликов играют ученики, а роль клеток — дни года).
Задача 119. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
Решение:
Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена). Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей. (23 «кролика» рассажены в двух «клетках»).
Задача 120.
Очень лёгкая задача на логику.
«У Лёвы кот перед дождём всегда чихает. Сегодня он чихнул. «Значит, будет дождь» - думает Лев. Прав ли он?
Ответ: Нет, не прав. Из необходимости условия вовсе не следует его достаточность.