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

Answer 2

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

1. Петя выбирает k = 1: Если Петя выбирает полоски длины 1 клетка, то он может удалить все клетки на одной из сторон квадрата. Независимо от действий Васи, это составляет 10 клеток.

2. Петя выбирает k = 2: Если Петя выбирает полоски длины 2 клетки, то он может удалить по 2 клетки с каждой стороны квадрата. Таким образом, он гарантированно удалит 2*10 = 20 клеток.

3. Петя выбирает k = 3: Если Петя выбирает полоски длины 3 клетки, то он может удалить по 3 клетки с каждой стороны квадрата, за исключением угловых клеток, где он сможет удалить только 2 клетки. Таким образом, он гарантированно удалит 28 + 32 = 22 клетки.

4. Петя выбирает k = 4: Если Петя выбирает полоски длины 4 клетки, то он может удалить по 4 клетки с каждой стороны квадрата, за исключением угловых клеток, где он сможет удалить только 3 клетки. Таким образом, он гарантированно удалит 38 + 42 = 28 клеток.

5. Петя выбирает k = 5: Если Петя выбирает полоски длины 5 клеток, то он может удалить по 5 клеток с каждой стороны квадрата, за исключением угловых клеток, где он сможет удалить только 4 клетки. Таким образом, он гарантированно удалит 48 + 52 = 36 клеток.

6. Петя выбирает k = 6, 7, 8, 9 или 10: В этих случаях Петя сможет удалить полоски только с одной стороны квадрата (по условию он не может выбирать полоски длиннее стороны квадрата). При любом из этих значений k он гарантированно удалит только 10 клеток.

Таким образом, наибольшее число клеток, которое Петя может гарантированно удалить, независимо от действий Васи, составляет 36 клеток. Это достигается, если Петя выбирает полоски длины 5 клеток и удаляет их с каждой стороны квадрата, за исключением угловых клеток, где он удаляет 4 клетки.