Задача: Вася и Петя играют в такую игру: Вася разрезает квадрат 9х9 на полоски толщиной в одну клетку (с любыми натуральными длинами). После этого Петя выбирает любое число k от 1 до 9 и удаляет все полоски длины k. Какое наибольшее число клеток Петя гарантированно может удалить независимо от действий Васи?
Решение: Вот пример разрезания на полоски, когда Пете не удастся удалить больше 12 клеток (разрезания по строкам): 9, 8+1, 7+2, 6+3, 6+3, 5+4, 5+4, 4+2+2+1, 3+3+2+1. Допустим, есть разрезание, где Пете не удастся удалить больше 11 клеток. Тогда в этом разрезании не больше, чем по одной полоске длины 9, 8, 7 и 6, не больше, чем по две полоски длины 5 и 4, не больше трех полосок длины 3, пяти полосок длины 2 и 11 полосок длины 1. Суммарная площадь этих полосок не больше 78, что меньше площади квадрата 9х9. Противоречие.
