Problem 9-6. In a cubic chest with a side of $2^{n}$ dm, there are $8^{n}$ different spices: it contains eight closed cubic boxes with a side of $2^{n-1}$ dm, each of which contains eight closed cubic boxes with a side of $2^{n-2}$ dm, and so on down to boxes with a side of 1 dm, each containing its own spice.

In one of the small boxes, there is a mouse that wants to taste all the spices, visiting each box exactly once and returning to its home box at the end of the journey. By gnawing through the walls, the mouse can move from a given small box to any adjacent one by a face (but not to those adjacent only by an edge or a vertex). What is the minimum number of holes in the walls of the boxes (of all sizes) that it will have to gnaw through to fulfill its dream?

Describe any path of the mouse with the minimum number of holes in the walls and calculate how many small boxes will have two opposite walls gnawed through in this case.

Note. For different paths that give the correct answer in this problem, the number of boxes with gnawed opposite walls may be different. Participants whose number of such boxes is the largest will be awarded commemorative prizes. (This achievement does not affect the evaluation of the work and the awarding of titles of winners and prize winners of the Olympiad.)

Answer: $2 \cdot\left(8^{n+1}-1\right) / 7$.
Solution. The conditions of the problem require that the mouse gnaws through each box in at least two places: to enter it and to leave it. Thus, the number of holes is no less than twice the number of boxes, that is, \(2 \cdot \left(8^{n+1}-1\right) / 7\). We will construct a path for the mouse with this number of holes, and without any boxes having opposite walls gnawed through. We will construct it from the following segments:
![](https://cdn.mathpix.com/cropped/2024_05_06_625a98ab8afc57dd353ag-7.jpg?height=354&width=568&top_left_y=453&top_left_x=754)

This diagram illustrates a way to visit all boxes of size 1 dm inside one box of size 2 dm, gnawing through the shaded areas. Note that each of the involved boxes is gnawed through exactly in two places, and no box has opposite walls gnawed through. If we now traverse all boxes of size 2 dm in the given box of size 4 dm in the same order and with holes in the same places as shown in the diagram, traversing each box of size 2 dm in the described manner, we will obtain a traversal of the box of size 4 dm, in which each of the involved boxes is gnawed through exactly in two places, and no box has opposite walls gnawed through. And so on: if we traverse all boxes of size \(2^k\) dm in the given box of size \(2^{k+1}\) dm in the same order and with holes in the same places as shown in the diagram, traversing each box of size \(2^k\) dm in the described manner, we will obtain a traversal of the box of size \(2^{k+1}\) dm, in which each of the involved boxes is gnawed through exactly in two places, and no box has opposite walls gnawed through. To obtain a closed path inside the chest in the end, the boxes of size \(2^{n-1}\) can be traversed according to the following scheme:
![](https://cdn.mathpix.com/cropped/2024_05_06_625a98ab8afc57dd353ag-7.jpg?height=354&width=570&top_left_y=1823&top_left_x=754)

Now, no matter which box of this closed path the mouse starts in, it will be able to follow this path, visiting each box exactly once, returning to the initial one, and making exactly one hole in two adjacent walls of each box.

| Evaluation | Score | Content of the criterion |
| :---: | :---: | :--- |
| + | 20 | Complete solution |
| $+/-$ | 16 | Correct solution with loose reasoning |
| $-/+$ | 10 | Correct estimate and idea of inductive transition, no proof |
| .- | 6 | Correct estimate, no further progress |
| - | 0 | Solution is completely incorrect/only answer |