В кубическом сундуке со стороной 2n дм хранится 8n различных пряностей: в него упакованы восемь закрытых кубических коробок со стороной 2n−1 дм, в каждую из них — восемь закрытых кубических коробок со стороной 2n−2 дм, и так далее вплоть до коробок со стороной 1 дм, в каждой из которых лежит своя пряность.
В одной из маленьких коробок оказалась мышь, которая хочет отведать всех пряностей, посетив каждую коробку ровно по одному разу и вернувшись в конце пути в родную коробку. Прогрызая стенки, мышь может попадать из данной маленькой коробки в любую граничащую с ней по грани (но не может в граничащие лишь по ребру или вершине). Какое минимальное число отверстий в стенках коробок (всех размеров) ей предстоит прогрызть для осуществления своей мечты?
Опишите какой-нибудь путь мыши с минимальным числом отверстий в стенках и вычислите, у скольких маленьких коробок при этом окажутся прогрызены две противоположные стенки.
Замечание. Для разных путей, дающих верный ответ в этой задаче, может получиться разное число коробок с прогрызенными противоположными стенками. Участникам, у которых число таких коробок окажется наибольшим, будут вручены памятные призы. (Это достижение не влияет на оценку работы и присвоение званий победителя и призера олимпиады.)
Условия задачи требуют, чтобы мышь прогрызла каждую коробку как минимум в двух местах: чтобы попасть в нее и чтобы покинуть её. Таким образом, число отверстий не меньше удвоенного числа коробок, то есть 2 · (8n+1 − 1) / 7. Построим путь мыши с таким числом отверстий, причем вовсе без коробок с прогрызенными противоположными стенками. Мы будем составлять его из следующих кусочков:
Данный рисунок изображает способ посетить все коробки размера 1 дм внутри одной коробки размера 2 дм, прогрызя заштрихованные места. Заметим, что каждая из задействованных коробок прогрызается ровно в двух местах, и ни у одной не прогрызены противоположные стенки. Если теперь мы обойдём все коробки размера 2 дм в данной коробке размера 4 дм в том же порядке и с отверстиями в тех же местах, как показано на рисунке, обходя при этом каждую коробку размера 2 дм описанным способом, то получим обход коробки размера 4 дм, при котором каждая из задействованных коробок прогрызается ровно в двух местах, и ни у одной не прогрызены противоположные стенки. И так далее: если обойти все коробки размера 2k дм в данной коробке размера 2k+1 дм в том же порядке и с отверстиями в тех же местах, как показано на рисунке, обходя при этом каждую коробку размера 2k дм описанным способом, то получим обход коробки размера 2k+1 дм, при котором каждая из задействованных коробок прогрызается ровно в двух местах, и ни у одной не прогрызены противоположные стенки. Чтобы в результате получить замкнутый путь внутри сундука, коробки размера 2n−1 можно обойти по следующей схеме:
Теперь, в какой бы коробке этого замкнутого пути ни завелась мышь, она сможет проследовать по этому пути, побывав ровно один раз в каждой коробке, вернувшись в изначальную, и сделав ровно по одному отверстию в двух соседних стенках каждой коробки.
Ответ: 2 · (8n+1 − 1) / 7.