Question

На доске написано 20 нулей и 17 единиц. За один ход можно стереть любые два числа и вместо них записать их сумму. Ход называется важным, если полученное в результате этого хода число было больше, чем каждое из стертых. Сколько важных ходов будет сделано, прежде чем на доске останется единственное число?

Answer 1

Заметим, что ход будет важным тогда и только тогда, когда оба стираемых числа натуральные (не нули). Значит, в результате любого важного хода на доске останется на одно натуральное число меньше, чем было до этого. Таким образом, через 16 важных ходов на доске останется одно натуральное число и, возможно, несколько нулей. Каждый из последующих ходов будет неважным, а значит, всего будет сделано 16 важных ходов.

Answer 2

Давайте рассмотрим, как можно провести важные ходы. У нас есть 20 нулей и 17 единиц. Для удобства обозначим 0 как "O" и 1 как "X". Начальное состояние доски:

OOOOOOOOOOOOOOOOOOOO XXXXXXXXXXXXXXXXX

На каждом ходу мы можем стереть любые два числа и записать их сумму. Попробуем максимизировать сумму на каждом ходу.

Шаг 1: OOOOOOOOOOOOOOOOOO XX + XX = OOOOOOOOOOOOOOOOOOO XX

Шаг 2: OOOOOOOOOOOOOOOOOOO X + XXX = OOOOOOOOOOOOOOOOOOXX

Шаг 3: OOOOOOOOOOOOOOOOOO XX + XXXX = OOOOOOOOOOOOOOOOOXXX

Шаг 4: OOOOOOOOOOOOOOOOO XXX + XXXXX = OOOOOOOOOOOOOOOXXXX

Шаг 5: OOOOOOOOOOOOOOO XXXX + XXXXXX = OOOOOOOOOOOOOXXXXX

Шаг 6: OOOOOOOOOOOOO XXXXX + XXXXXXX = OOOOOOOOOOOXXXXXX

Шаг 7: OOOOOOOOOOO XXXXXX + XXXXXXXX = OOOOOOOOOXXXXXXX

Шаг 8: OOOOOOOOOO XXXXXXX + XXXXXXXXX = OOOOOOOXXXXXXXXX

Шаг 9: OOOOOOOOO XXXXXXXX + XXXXXXXXXX = OOOOOXXXXXXXXXX

Шаг 10: OOOOOOOO XXXXXXXXX + XXXXXXXXXXX = OOOOXXXXXXXXXXX

Шаг 11: OOOOOOO XXXXXXXXXX + XXXXXXXXXXXX = OOOXXXXXXXXXX

Шаг 12: OOOOOO XXXXXXXXXXX + XXXXXXXXXXXXX = OOXXXXXXXXXXX

Шаг 13: OOOOO XXXXXXXXXXXX + XXXXXXXXXXXXXX = OOXXXXXXXXX

Шаг 14: OOOO XXXXXXXXXXXXX + XXXXXXXXXXXXXXX = OXXXXXXXXXXX

Шаг 15: OOO XXXXXXXXXXXXXX + XXXXXXXXXXXXXXXX = OXXXXXXXXXX

Шаг 16: OO XXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXX = XXXXXXXXXXX

Шаг 17: O XXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXX = XXXXXXXXX

Шаг 18: XXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXX = XXXXXXX

Шаг 19: XXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXX = XXXXXX

Шаг 20: XXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXX = XXXXX

Шаг 21: XXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXX = XXXX

Шаг 22: XXXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXXX = XXX

Шаг 23: XXXXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXXXX = XX

Шаг 24: XXXXXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXXXXX = X

Шаг 25: XXXXXXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXXXXXX = 0

Теперь на доске осталось единственное число. Мы провели 25 важных ходов, прежде чем на доске осталось единственное число.