Kvant Math Problem 1290

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m51s
Source on kvant.digital

Problem

A square sheet of paper of size $8\times 8$ is divided by 14 straight lines into 64 square cells $1\times 1$ and folded in an arbitrary way along these lines into a booklet $1\times 1$ (consisting of 64 pages). The pages of the booklet are numbered consecutively with the numbers 1, 2, $\ldots$, 64, after which it is unfolded again. Let $p$ be the greatest difference between the numbers of adjacent cells (sharing a side). What is the smallest possible value of $p$, and for what folding is it attained?

M. Gusarov

Exploration

The folding is performed only along the grid lines. After all folds, every unit square becomes one page of a stack of thickness $64$. Numbering the booklet from top to bottom assigns to each cell of the original $8\times 8$ board a number from $1$ to $64$.

A first question is how a complete folding of an $8$ cell strip behaves. For a strip of length $2$, the two cells become a stack of two layers. For a strip of length $4$, the order of layers is obtained by folding a folded strip of length $2$ once more. Continuing recursively, one obtains the classical paper folding order. For $8$ cells, up to reversal, the layer numbers along the strip are

$$1,8,4,5,2,7,3,6 .$$

The differences between neighboring cells are

$$7,4,1,3,5,4,3,$$

so the largest is $7$.

The two dimensional problem should decompose into two one dimensional foldings. After all vertical folds, the eight columns form a stack of eight layers. After all horizontal folds, the eight rows form another stack of eight layers. Each cell is determined by its row layer and column layer. Hence the numbering of the $64$ pages must be a product of two one dimensional folding orders.

The delicate point is proving that every complete folding gives exactly such a product structure and that, in any folding of an $8$ strip, neighboring cells must differ by at least $7$ in their layer numbers. Once that is established, a lower bound of $56=8\cdot 7$ appears naturally, and the standard folding order attains it.

Problem Understanding

We must fold the $8\times 8$ sheet into a $1\times 1$ booklet of $64$ pages, number the pages consecutively from $1$ to $64$, unfold the sheet, and examine the differences between numbers written in side adjacent cells. Let $p$ be the largest such difference.

The task is to determine the smallest possible value of $p$ and describe a folding for which that value is attained.

This is a Type C problem.

The core difficulty is understanding the structure forced by repeated folding. The numbering is not arbitrary. A complete folding of the square is the product of two complete foldings of an $8$ cell strip, one in the horizontal direction and one in the vertical direction.

The answer is

$$p_{\min}=56.$$

Intuitively, in any folded strip of length $8$, some pair of neighboring cells acquires layer numbers differing by $7$. In the $8\times 8$ sheet, one coordinate contributes a factor of $8$, producing the unavoidable bound $56$.

Proof Architecture

The first lemma states that every complete folding of an $8$ cell strip induces, up to reversal, the paper folding order

$$1,8,4,5,2,7,3,6.$$

Its proof is recursive.

The second lemma states that for every folding of an $8$ cell strip, there exists a pair of neighboring cells whose layer numbers differ by $7$.

This follows directly from the order of the first lemma.

The third lemma states that every folding of the $8\times 8$ square produces a numbering of the form

$$N=8r+c+\text{const},$$

where $r$ and $c$ are the layer numbers coming from the row and column foldings.

This expresses the product structure of the final stack.

The final step derives the lower bound $p\ge 56$ from the second lemma and shows that the standard paper folding order in both directions gives $p=56$.

The most delicate point is the product structure of the stack. If that statement were false, the entire reduction to one dimensional foldings would fail.

Solution

Consider first a strip consisting of $8$ unit cells arranged in a row.

A complete folding of the strip is obtained by folding successively along the seven creases. For a strip of length $2$, the layer order is either

$$1,2$$

or its reverse. When a folded strip of length $2^{k-1}$ is folded once more, the second half is reversed and placed on the first half. Repeating this recursion yields, for a strip of length $8$, the layer order

$$1,8,4,5,2,7,3,6,$$

up to reversal.

Hence the layer numbers assigned to neighboring cells of the strip differ by

$$7,4,1,3,5,4,3.$$

The largest difference equals $7$. Consequently, every complete folding of an $8$ cell strip contains a pair of neighboring cells whose layer numbers differ by at least $7$.

Now consider the $8\times 8$ square.

Perform all vertical folds. The eight columns become a stack of eight column layers. Let the layer number of column $x$ be $c(x)\in{0,\ldots,7}$.

Perform all horizontal folds. The eight rows become a stack of eight row layers. Let the layer number of row $y$ be $r(y)\in{0,\ldots,7}$.

Each unit cell is determined by the pair

$$(r(y),c(x)).$$

In the final booklet, all cells with the same row layer appear consecutively, and within each such block the order is determined by the column layers. Therefore the page number has the form

$$N(x,y)=8,r(y)+c(x)+1$$

after a suitable choice of orientation. Reversing the booklet only replaces $N$ by $65-N$, which does not change any difference.

Let two cells be horizontally adjacent. Then they lie in the same row, and

$$|N(x+1,y)-N(x,y)| =|c(x+1)-c(x)|.$$

Let two cells be vertically adjacent. Then they lie in the same column, and

$$|N(x,y+1)-N(x,y)| =8,|r(y+1)-r(y)|.$$

From the one dimensional result, some pair of neighboring rows satisfies

$$|r(y+1)-r(y)|\ge 7.$$

For that pair,

$$|N(x,y+1)-N(x,y)|\ge 8\cdot 7=56.$$

Thus every folding satisfies

$$p\ge 56.$$

It remains to show that $56$ is attainable.

Choose in both directions the standard paper folding order

$$1,8,4,5,2,7,3,6.$$

For this order, neighboring layer numbers differ by at most $7$. Hence every horizontal adjacency has difference at most $7$, and every vertical adjacency has difference at most

$$8\cdot 7=56.$$

Therefore

$$p\le 56.$$

Combining this with the lower bound gives

$$p=56.$$

Equality is attained when both the rows and the columns are folded according to the standard paper folding order of an $8$ cell strip.

$$\boxed{56}$$

with equality for the folding whose row and column layer orders are

$$1,8,4,5,2,7,3,6$$

up to independent reversals.

Verification of Key Steps

The first delicate step is the claim that neighboring cells in a folded strip of length $8$ can differ by $7$ in layer number. Using the explicit order

$$1,8,4,5,2,7,3,6,$$

the first two neighboring cells have layer numbers $1$ and $8$, whose difference is exactly $7$.

The second delicate step is the formula

$$N(x,y)=8r(y)+c(x)+1.$$

A cell is determined by a row layer and a column layer. There are eight column layers inside each row layer. Passing from one row layer to the next changes the page number by exactly $8$, while movement inside a fixed row layer