Each cell of an 8×8 chessboard has a number written in it. Joonmin is allowed to switch numbers in two adjacent squares and Joonmin is allowed to change numbers in two adjacent squares to the average of these two numbers. Prove that after finitely many such operations Joonmin can always make the numbers in all of the squares to be the same.

I am not sure where to start here, and using algebra doesn't seem to be effective because there are many numbers to be considered.

  • $\begingroup$ What is "adjacent"? Is it diagonal, horizontal, vertical or all of them? $\endgroup$ – user061703 Mar 10 '18 at 3:38
  • 4
    $\begingroup$ I don't know the answer, but I'd start by analyzing the 2x2 case. $\endgroup$ – Josh B. Mar 10 '18 at 3:52
  • 1
    $\begingroup$ @JoshB. this comment got me to a solution pretty quickly for $2^n$ by $2^n$. This is a good suggestion. $\endgroup$ – Callus - Reinstate Monica Mar 10 '18 at 4:01

In the 2×2 case, suppose we have numbers $$\begin{bmatrix}a&b\\c&d\end{bmatrix}$$ We can average $a$ and $b$ to get $e$, and $c$ and $d$ to $f$: $$\begin{bmatrix}e&e\\f&f\end{bmatrix}$$ Then we can average the elements in both columns, leaving all squares equal. I will call this process smoothing.

In the 4×4 case, smooth each 2×2 block: $$\begin{bmatrix}a&a&b&b\\ a&a&b&b\\ c&c&d&d\\ c&c&d&d\end{bmatrix}$$ Swap elements so that those same 2×2 blocks have one each of the four distinct numbers that result: $$\begin{bmatrix}a&b&a&b\\ c&d&c&d\\ a&b&a&b\\ c&d&c&d\end{bmatrix}\tag1$$ Smoothing each 2×2 block now will produce a board with all squares the same number.

Similarly, we can use the 4×4 smoothing to smooth the full 8×8 board:

  • Smooth each 4×4 block
  • Swap elements to achieve the same pattern as in $(1)$, only with $a,b,c,d$ being 2×2 blocks rather than single elements
  • Smooth each 4×4 block

This shows that only finitely many operations are needed to smooth the whole board, as desired.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.