Олимпиадная задача по теории алгоритмов для 9-11 классов от Женодарова Р. Г.
Задача
В ряд стоят 23 коробочки с шариками, причём для каждого числа n от 1 до 23 есть коробочка, в которой ровно n шариков. За одну операцию можно переложить в любую коробочку еще столько же шариков, сколько в ней уже есть, из какой-нибудь другой коробочки, в которой шариков больше. Всегда ли можно такими операциями добиться, чтобы в первой коробочке оказался 1 шарик, во второй – 2 шарика, ..., в 23-й – 23 шарика?
Решение
Из расположения (k, k – 1, k – 2, ... , 3, 2, 1) легко получить расположение (1, k, k – 1, ..., 3, 2) (для этого надо переложить шарики из первой коробочки во вторую, потом из второй – в третью и т.д.). Таким образом, фактически можно производить циклическую перестановку указанных коробочек.
Теперь покажем, как из исходного расположения получить произвольное:
1) переставим по циклу нужное число раз (может быть, ни одного) все коробочки так, чтобы коробочка с 23 шариками оказалась на нужном месте;
2) не трогая больше эту коробочку, переставляем остальные так, чтобы коробочка с 22 шариками оказалась на нужном месте;
... и так далее.
Ответ
Всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь