- #1
caffeinemachine
Gold Member
MHB
- 816
- 15
The numbers $1,2,\ldots,100$ are arranged in the squares of a $10\times 10$ table in the following way:
The numbers $1,2,\ldots,10$ are in the bottom row in increasing order. The numbers $11,12,\ldots,20$ are in the second last row in increasing order, and so on. One can choose any number and two of its neighbors in the opposite directions (horizontal, vertical, or diagonal). Then either the number is increased by $2$ and its neighbors are decreased by $1$ or the number is increased by $2$ and the neighbors are increased by $1$. After several such operations the table again contains the numbers $1,2,\ldots,100$. Prove that they are in the original order.Unable to solve this I finally looked at the solution given. It begins as follows:
Let the original entries of the table be represented by ${_0}a_{ij}$. Let the entries after $k$ operations be represented by ${_k}a_{ij}$. Then observe that $P:=\displaystyle{\sum_{i=1}^{10}} \displaystyle{\sum_{j=1}^{10}}({_0}a_{ij})({_k}a_{ij})$ is an invariant with respect to $k$. Then after one more firecracker (namely the rearrangement inequality) the proof is complete.
This idea of solution was very foreign to me. What I observed was that the order in which the operations are performed is immaterial. But I could not exploit this to produce a proof. Is anybody able to see a solution which does not use an invariant?
The numbers $1,2,\ldots,10$ are in the bottom row in increasing order. The numbers $11,12,\ldots,20$ are in the second last row in increasing order, and so on. One can choose any number and two of its neighbors in the opposite directions (horizontal, vertical, or diagonal). Then either the number is increased by $2$ and its neighbors are decreased by $1$ or the number is increased by $2$ and the neighbors are increased by $1$. After several such operations the table again contains the numbers $1,2,\ldots,100$. Prove that they are in the original order.Unable to solve this I finally looked at the solution given. It begins as follows:
Let the original entries of the table be represented by ${_0}a_{ij}$. Let the entries after $k$ operations be represented by ${_k}a_{ij}$. Then observe that $P:=\displaystyle{\sum_{i=1}^{10}} \displaystyle{\sum_{j=1}^{10}}({_0}a_{ij})({_k}a_{ij})$ is an invariant with respect to $k$. Then after one more firecracker (namely the rearrangement inequality) the proof is complete.
This idea of solution was very foreign to me. What I observed was that the order in which the operations are performed is immaterial. But I could not exploit this to produce a proof. Is anybody able to see a solution which does not use an invariant?