Question

Фрекен Бок расставила на столе в ряд 14 тарелок, на первую положила 1 блинчик, на вторую - 2,..., на 14-ую - 14 блинчиков. Когда Фрекен Бок отворачивается, в окно влетает Карлсон и съедает с некоторых тарелок по произвольному одинаковому числу блинчиков. Какое минимальное количество раз нужно отвернуться Фрекен Бок, чтобы у Карлсона была возможность съесть все блинчики?

Answer 1

Ответ: 4 раза.

Пример:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (15 стопок, в одной из них 0 блинчиков)

0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 (съели по 7 блинчиков, где это возможно)

0 1 2 3 0 1 2 0 1 2 3 0 1 2 3 (съели по 4 блинчика, где это возможно)

0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 (съели по 2 блинчика, где это возможно)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (съели оставшееся)

Оценка:

У нас 15 стопок (в одной 0 блинчиков)

Нам нужно их сделать равными (равными стопке с 0 блинчиками)

Т. к. мы съедаем одинаковое число блинчиков из каждой стопки, то у нас первым ходом может получиться максимум 2 одинаковые стопки (пар одинаковых стопок может быть много)

Вторым ходом могут получиться максимум 4 одинаковые стопки (2 пары одинаковых стопок стали равными), т. к. если бы их было больше, например 5, то до этого должны были существовать хотя бы 3 одинаковые стопки.

Аналогично на третьем ходу могло оказаться максимум 8 одинаковых стопок (2 четверки стали равными), поэтому меньше 4 ходов не может быть (нужно сделать 15 стопок равными).





Если продолжить рассуждения, то решение позволяет также решить более общую задачу, что из
${2}^{n} < x \leqslant {2}^{n + 1}$
стопок (включая нулевую) можно съесть все блинчики за n+1 ход минимум. Пример легко привести.

Answer 2

Для того чтобы Карлсон смог съесть все блинчики, он должен съесть 1 + 2 + 3 + ... + 14 блинчиков, что в сумме составляет сумму арифметической прогрессии.

Сумма арифметической прогрессии вычисляется по формуле: S = (n * (a1 + an)) / 2,

где S - сумма прогрессии, n - количество членов прогрессии, a1 - первый член прогрессии, an - последний член прогрессии.

В данном случае: n = 14 (количество тарелок и блинчиков), a1 = 1 (первый член прогрессии), an = 14 (последний член прогрессии).

S = (14 * (1 + 14)) / 2 = 15 * 14 / 2 = 210.

Таким образом, чтобы Карлсон смог съесть все блинчики, ему нужно съесть 210 блинчиков.

Теперь рассмотрим, как Карлсон может съесть блинчики:

• Он может съесть 1 блинчик за первый раз, оставив 209 блинчиков.
• После этого он может съесть 2 блинчика за второй раз, оставив 207 блинчиков.
• Затем он может съесть 3 блинчика за третий раз, оставив 204 блинчика.
• И так далее, пока не съест 14 блинчиков за четырнадцатый раз, оставив 196 блинчиков.

На этом этапе у Карлсона осталось 196 блинчиков, что не позволяет ему съесть оставшиеся 14 блинчиков (так как они находятся на 14-ой тарелке). Он должен оторваться и вернуться, чтобы продолжить есть блинчики, начиная с 1-ого блинчика снова.

Таким образом, Карлсону понадобится минимальное количество раз, равное количеству тарелок (14 раз), чтобы съесть все блинчики.