Математическая регата (12)

Ответ: два звена.

Докажем сначала, что одним размыканием обойтись нельзя. После любого размыкания у нас окажется не более трех кусков цепочки. Если составлять из этих кусков различные комбинации, то можно получить не более чем 2³ = 8 различных вариантов, а этого недостаточно.

Приведем пример размыкания двух звеньев, удовлетворяющий условию. Разомкнем четвертое и одиннадцатое звено. При этом получатся куски, содержащие 1, 1, 3, 6 и 12 звеньев. Непосредственной проверкой несложно убедиться, что, используя эти слагаемые, можно получить любое число от 1 до 23.

Замечание. Решим общую задачу: при каком наибольшем количестве M звеньев в цепочке можно, разомкнув не более чем n звеньев, иметь возможность отдать любое количество звеньев, от 1 до M?

После размыкания n звеньев, у нас образуется возможность отдать любое количество звеньев от 1 до n. Поэтому меньший из оставшихся кусков должен содержать не менее (n + 1) звена. Имея кусок из (n + 1) звена можно отдать любое количество звеньев от 1 до 2 × (n + 1) – 1. Аналогично, следующий кусок должен содержать не менее 2 × (n + 1) звеньев, и так далее. Таким образом,

M £ n + (n + 1) + 2 × (n + 1) + 4 × (n + 1) + ... + 2ⁿ × (n + 1) =
= n + (n + 1)(1 + 2 + 4 + ... + 2ⁿ) = n + (n + 1)(2ⁿ+1 – 1) =
= (n + 1) × 2ⁿ+1 – 1.

Несложно убедиться, что M = 23 при n = 2.

На каждом шаге выбирать еще больший кусок мы не сможем, так как образуются “пробелы”, а если выбирать куски меньшие, чем указанные, то количество звеньев в цепочке будет уменьшаться.