Математическая регата (12)
У Васи есть незамкнутая цепочка из 23 звеньев. Вася разомкнул в ней несколько звеньев так, что теперь он может подарить Маше любое количество звеньев от 1 до 23. Какое количество звеньев разомкнул Вася, если известно, что оно наименьшее из возможных? (Размыкание одного звена может разделить цепочку на три части, одна из которых — разомкнутое звено.)
Докажем сначала, что одним размыканием обойтись нельзя. После любого размыкания у нас окажется не более трех кусков цепочки. Если составлять из этих кусков различные комбинации, то можно получить не более чем 2 3 = 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 × ( n + 1) =
= n + ( n + 1)(1 + 2 + 4 + . + 2 n ) = n + ( n + 1)(2 n +1 – 1) =
= ( n + 1) × 2 n +1 – 1.
Несложно убедиться, что M = 23 при n = 2.
На каждом шаге выбирать еще больший кусок мы не сможем, так как образуются “пробелы”, а если выбирать куски меньшие, чем указанные, то количество звеньев в цепочке будет уменьшаться.
Источник