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 клеток.