A grid arrangement problem

(David here.) I'm back with another interesting problem - this time, it's about arranging numbers in a grid.

(Moscow 2015, 11.5) Can we write the numbers 1 to 64 into an $8\times 8$ grid such that for each $2 \times 2$ square, the product of the opposite corners differ by 1?

Once again, my strategy of looking for problems with few solves led me to something interesting. (In this case, no solves - the highest score was -+, which is like a 2/7.)

Spoilers below!

.

.

.

.

.

Pre-attempts

Actually, the original problem also tells you that it's not possible - sorry if you spent a long time trying to do it!

I also gave this problem at my work, and some colleagues ended up just brute forcing it with a program - turns out an 8 x 8 grid is small enough that you can either fill the numbers one by one and backtrack or go for a "valid 2 x 2 squares" approach.

My attempt

We start with the $2 \times 2$ analogue, which is to stuff the numbers 1 to 4 into the grid to have the property. One immediate realization is that 2 and 4 cannot be next to each other, otherwise both products are even (so they can't differ by 1).

This reasoning holds true in general: even numbers cannot be next to each other. Hence, on an even-sized grid they have to occupy the positions of exactly one of the colors of a checkerboard.

At this point I tried to think more generally about the modular structure - if mod 2 told us something productive, what about mod 4 or mod 8? We know our matrices look like $$ \begin{pmatrix} \text{even} & \text{odd} \\ \text{odd} & \text{even} \end{pmatrix} $$ so the even product is actually 0 mod 4, but this doesn't restrict the odd numbers. Going to mod 8 helps slightly - we have the following possibilities (taken mod 8): $$ \begin{pmatrix} \pm 1 & \pm 2 \\ \pm 2 & \pm 3 \end{pmatrix}, \begin{pmatrix} \pm 1 & \pm 2 \\ 4 & \pm 1 \end{pmatrix}, \begin{pmatrix} \pm 1 & 4 \\ 4 & \pm 1 \end{pmatrix}, $$

We don't have everything here, but if one product is 0 mod 8 then the other diagonal must be both $\pm 1$ mod 8 or $\pm 3$ mod 8. This means that around every "connected component" of 4 mod 8s, we have some region of odd numbers that are either all $\pm 1$ mod 8 or $\pm 3$ mod 8. Because we have an equal number of each (and also an equal number of 4 and $\pm 2$ mod 8's), this kind of forces the following pattern (on a $4 \times 4$ subgrid): $\newcommand{\clr}{\textcolor{red}}\newcommand{\clb}{\textcolor{blue}}$

$$ \begin{pmatrix} \clr{\pm 1} & 4 & \clr{\pm 1} & \pm 2 \\ 4 & \clr{\pm 1} & \pm 2 & \clb{\pm 3} \\ \clr{\pm 1} & \pm 2 & \clb{\pm 3} & 4\\ \pm 2 & \clb{\pm 3} & 4 & \clb{\pm 3} \\ \end{pmatrix} $$

But this pattern exists, so that doesn't help us show that it's impossible.

I briefly thought about other moduli (multiples of 3?) but didn't really have any productive ideas.

Reflecting on the overall approach, we've tried to go for something global (i.e. something that restricts the positions of all the numbers at once), but maybe the answer lies with single numbers that are hard to slot? I didn't find anything along these lines.

Maybe we can think about what near constructions look like? Admittedly, I had some spoilers from the computer brute force attempt, but essentially there are "good" matrices that look something like: $$ \begin{pmatrix} 1 & 4 \\ 2 & 7 \\ 3 & 10 \end{pmatrix} $$

Do you see a pattern here? This comes from interpreting the difference of products as an area - in particular, the area of the triangle formed by $(0,0), (1,4), (2,7)$ must be 1/2. So naturally, it makes sense that we can extend to the next lattice point along the line connecting $(1,4)$ and $(2,7)$ to get another triangle with area 1/2. Another possible point is $(3,11)$, but it violates the odd-even arrangement. (Coincidentally, this means that filling in the first row and column determines the entire grid!)

Ultimately, this doesn't help much, and I was starting to "tunnel" with these existing approaches. It's hard to get out of these existing lines of thought. It took me giving up momentarily and to go about with life for a while, but as I was taking the subway I found the new idea I needed. What do you think it was?

.

.

.

.

.

Turns out that the odd-even structure tells us much more: the product of the even numbers in 1 to 64 is systematically larger than the product of the odd numbers. In fact, we can think of their ratio as $$\left(1 + \frac{1}{1}\right) \cdot \left(1 + \frac{1}{3}\right) \cdot \left(1 + \frac{1}{5}\right) \cdots \left(1 + \frac{1}{63}\right)$$

But also, we can partition the grid into $2 \times 2$ squares (16 of them), and within each square the even product is not much larger than the odd product - if we let the odd pairs be $(o_1, o_2), (o_3, o_4), \ldots, (o_{15}, o_{16})$, then the ratio of the overall even product to the overall odd product is $$\left(1 + \frac{1}{o_1o_2}\right) \cdot \left(1 + \frac{1}{o_3o_4}\right) \cdot \left(1 + \frac{1}{o_5o_6}\right) \cdots \left(1 + \frac{1}{o_{15}o_{16}}\right)$$

Clearly, this has to be smaller than the above, so we're done!

Commentary

In retrospect this should have been a really easy problem, so why were there 0 solves? I suspect that the well-hidden global condition is difficult to spot, and probably most contestants spent a lot of effort trying out more local approaches. (Some retired folks may remember how ISL 2017 C1 went down during NTST 2018.)

The computer searches that my colleagues ran suggest that the problem is also true for odd sized grids, but this method doesn't imply that - wonder if anyone can find a proof for those cases?

I'm also reminded of this other problem:

(USA TST 2019/4) We say that a function $f: \mathbb{Z}_{\ge 0} \times \mathbb{Z}_{\ge 0} \to \mathbb{Z}$ is great if for any nonnegative integers $m$ and $n$, $$f(m + 1, n + 1) f(m, n) - f(m + 1, n) f(m, n + 1) = 1.$$ If $A = (a_0, a_1, \dots)$ and $B = (b_0, b_1, \dots)$ are two sequences of integers, we write $A \sim B$ if there exists a great function $f$ satisfying $f(n, 0) = a_n$ and $f(0, n) = b_n$ for every nonnegative integer $n$ (in particular, $a_0 = b_0$).

Prove that if $A$, $B$, $C$, and $D$ are four sequences of integers satisfying $A \sim B$, $B \sim C$, and $C \sim D$, then $D \sim A$.