The integers from 1 to 64 are placed in some order into an 8×8 grid of cells with one number in each cell. Let ai,j be the number placed in the cell in row i and column j, and let M be the sum of the absolute differences between adjacent cells. That is, M=i=1∑8j=1∑7(∣ai,j+1−ai,j∣+∣aj+1,i−aj,i∣). Find the remainder when the maximum possible value of M is divided by 1000.
Consider the following arrangement: M=i=1∑8j=1∑7(∣ai,j+1−ai,j∣+∣aj+1,i−aj,i∣)=(64+63+⋯+47)×4+(46+45+⋯+35)×3+(34+33)×2−(1+2+3+⋯+18)×4−(19+20+⋯+30)×3−(31+32)×2=4(64−18)18+3(46−30)12+2(2)(2)=3896⟹Ans≥3896 Now try to prove Ans≤3896
Connect the centers of each two adjacent cells that share a common side.
Let L(S) be the number of grid edges having exactly one endpoint in S.
Let Sk denotes the cells containing 1,2,…,k.
Let's prove M=k=1∑63L(Sk) WLOG assume x<y.
We count the edge between x and y in Sx,Sx+1,Sx+2,…,Sy−1.
(From Sy this edge has two endpoints in the set and we shouldn't count it)
We count this edge y−x times ⟹M=k=1∑63L(Sk)
Define bm=max{L(S)} for all sets S of m cells.
By Hint 4 M=k=1∑63L(Sk)≤b1+b2+b3+⋯+b63 Find upper bounds for b1,…,b63
b1≤4 since each cell has at most 4 adjacent cells
Similarly b2≤4×2,b3≤4×3,…,b18≤4×18bs≤4s1≤s≤18
Let the good edges be the edges that have exactly one endpoint in S.
Now let's find upper bound for bs where 19≤s≤30
By the figure at most 18 cells have 4 good edges.
(Shown in the figure from each 1×2 at most one of them has 4 good edges otherwise if we consider both the edge between them isn't good)
For more than 18 each extra cell has at most 3 good edges 19≤s≤30:bs≤18×4+(s−18)3=3s+18
Now let's focus on b31
Let's prove b31≤110
Split the table into 32 1×2
At least there is a 1×2 that no two cells of that are not selected (like a,b) so the edge between them is not good. ⟹b31≤111 If b31=111 all the other edges must be good.
Consider 2 adjacent cells on top of them or below them (like c and d)
edge a↔c is good ⟹c is selected
edge b↔d is good ⟹d is selected
edge c↔d is bad ⟹b31=111 ⟹b31≤110
b32≤112 Since the total number of edges in the table is 8×7×2=112
For b33,b34,…,b63 bs=b64−s If bs=+ ∃S:L(S)=+ The number of good edges of S=+
⟹ The number of edges between S and Sc=+ ⟹L(Sc)=+⟹b64−s≥+⟹bs≤b64−s(1) Similarly b64−s≤b64−(64−s)=bs(2)(1),(2)⟹b64−s=bs
By Hints 5,6,7,8,9,10 M=k=1∑63L(Sk)≤b1+b2+b3+⋯+b63≤2(s=1∑18bs+s=19∑30bs+b31)+b32≤2(s=1∑184s+s=19∑30(3s+18)+110)+112=2(24×18×19+2(3×19+18+3×30+18)(30−19+1)+110)+112=2(2×18×19+183×6+110)+112=3896Final Answer 3896
