Maths Olympiad Prep

Library / /1221 of 1394

, 2024

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

Nine distinct positive integers summing to 7474 are put into a 3×33 \times 3 grid. Simultaneously, the number in each cell is replaced with the sum of the numbers in its adjacent cells. (Two cells are adjacent if they share an edge.) After this, exactly four of the numbers in the grid are 2323. Determine, with proof, all possible numbers that could have been originally in the center of the grid.

Solution

Solution:

Suppose the initial grid is of the format shown below:
[abcdefghi] \left[\begin{array}{lll} a & b & c \\ d & e & f \\ g & h & i \end{array}\right]
After the transformation, we end with
[anbncndnenfngnhnin]=[b+da+c+eb+fa+e+gb+d+f+hc+e+id+hg+e+if+h] \left[\begin{array}{lll} a_{n} & b_{n} & c_{n} \\ d_{n} & e_{n} & f_{n} \\ g_{n} & h_{n} & i_{n} \end{array}\right]=\left[\begin{array}{ccc} b+d & a+c+e & b+f \\ a+e+g & b+d+f+h & c+e+i \\ d+h & g+e+i & f+h \end{array}\right]
Since dfd \neq f, an=b+db+f=cna_{n}=b+d \neq b+f=c_{n}. By symmetry, no two corners on the same side of the grid may both be 2323 after the transformation.
Since cgc \neq g, bn=a+c+ea+e+g=dnb_{n}=a+c+e \neq a+e+g=d_{n}. By symmetry, no two central-edge squares sharing a corner may both be 2323 after the transformation.
Assume for the sake of contradiction that en=23e_{n}=23. Because an,cn,gn,in<ena_{n}, c_{n}, g_{n}, i_{n}<e_{n}, none of an,cn,gn,ina_{n}, c_{n}, g_{n}, i_{n} can be equal to 2323. Thus, 33 of bn,dn,fn,hnb_{n}, d_{n}, f_{n}, h_{n} must be 2323. WLOG assume bn=dn=fn=23b_{n}=d_{n}=f_{n}=23. This is a contradiction however, as bndnb_{n} \neq d_{n}. Thus, en23e_{n} \neq 23.
This leaves the case with two corners diametrically opposite and two central edge squares diametrically opposite being 2323. WLOG assume an=bn=hn=in=23a_{n}=b_{n}=h_{n}=i_{n}=23.
Thus, 92=423=an+bn+hn+in=(b+d)+(a+c+e)+(e+g+i)+(f+h)=(a+b+c+d+e+f+g+h+i)+e92=4 \cdot 23=a_{n}+b_{n}+h_{n}+i_{n}=(b+d)+(a+c+e)+(e+g+i)+(f+h)=(a+b+c+d+e+f+g+h+i)+e. Since a+b+c+d+e+f+g+h+i=74a+b+c+d+e+f+g+h+i=74, this means that e=9274=18e=92-74=18.
One possible example of 1818 working is [416261871173]\left[\begin{array}{lll}4 & 16 & 2 \\ 6 & 18 & 7 \\ 1 & 17 & 3\end{array}\right]. Thus the only possible value for the center is 1818.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.