Question

Вася и Петя играют в такую игру: Вася разрезает квадрат 1010 на полоски толщиной в одну
клетку (с любыми натуральными длинами). После этого Петя выбирает любое число k,
1 ≤ k ≤ 10, и удаляет все полоски длины k. Какое наибольшее число клеток Петя
гарантированно может удалить независимо от действий Васи?
С ОБЯСНЕНИЕМ

Answer 1

Докажем, что 12 клеток Петя сможет удалить всегда. Пусть это не так. Тогда полоски каждого размера суммарно не длиннее 11 клеток. Значит, их общая длина не более:

10 * 1 + 9 * 1 + 8 * 1 + 7 * 1 + 6 * 1 + 5 * 2 + 4 * 2 + 3 * 3 + 2 * 5 + 1 * 11 = 88 < 100.

Противоречие. Значит, Петя всегда сможет удалить хотя бы 12 клеток.

На картинке приведено разбиение, при котором Петя не сможет удалить более 12 клеток.

Ответ: 12 клеток.