Задача 8.
На полке в камере хранения стоят 10 чемоданов, занумерованных в некотором порядке числами от 1 до 10. Чемоданы имеют разную ширину и стоят необязательно вплотную друг к другу и к краям полки. Кладовщик снимает с полки чемодан № 1, а затем ставит его обратно на полку в самое левое из возможных положений, не сдвигая другие чемоданы. Затем он берет чемодан № 2 и ставит его в самое левое возможное положение, и т. д. После перестановки чемодана № 10 кладовщик снова переходит к чемодану № 1, и т. д. Докажите, что после 100 операций кладовщик будет ставить каждый чемодан на то место, откуда его только что взял. (Если очередной чемодан пришлось поставить на место, откуда его взяли, это всё равно засчитывается как выполненная операция.)
Ответ на Задачу 8.
В течение первых 10 операций заведомо исчезнет зазор между левой стенкой и ближайшим к ней левым чемоданом. Действительно, либо этот «левый чемодан» будет в свой ход придвинут к стенке, либо, если в зазоре мог поместиться чемодан с меньшим номером, самый первый из таких чемоданов и будет поставлен вплотную к стенке. В результате один из чемоданов — назовём его 𝐴 — окажется стоящим вплотную к стенке и при последующих действиях кладовщика больше не будет двигаться. В течение следующих 10 операций заведомо исчезнет зазор между чемоданом 𝐴 и чемоданом, ближайшим к нему справа. Действительно, либо этот «ближайший справа чемодан» будет в свой ход придвинут к чемодану 𝐴, либо, если в зазоре мог поместиться чемодан с меньшим номером (кроме чемодана 𝐴), самый первый из таких чемоданов и будет поставлен вплотную к чемодану 𝐴. В результате чемодан 𝐴 стоит вплотную к стенке, а вплотную к нему расположен ещё один чемодан — назовём его 𝐵, — причём при последующих действиях кладовщика оба чемодана больше не будут двигаться. Продолжая эти рассуждения, мы получим, что после 30 операций у левого края стенки будут вплотную стоять уже три чемодана, после 40 операций — 4 чемодана и т. д. Наконец, после 100 операций все 10 чемоданов будут стоять слева на полке без зазоров. Перемещение чемоданов на этом завершится.
