Consider a $ 7\times 7$ numbers table $ a_{ij} = (i^2 + j)(i + j^2), 1\le i,j\le 7.$ When we add arbitrarily each term of an arithmetical progression consisting of $ 7$ integers to corresponding to term of certain row (or column) in turn, call it an operation. Determine whether such that each row of numbers table is an arithmetical progression, after a finite number of operations.
Problem
Source: Chinese TST 2007 6th quiz P3
Tags: invariant, algebra, polynomial, calculus, function, arithmetic sequence, China
jdai_ming
12.12.2009 11:28
I don't understand the problem enough. Can anyone give me an example or something about this "operation".
kevinatcausa
12.12.2009 22:15
So we can for example add $ 1, 1, 1, 1, 1, 1, 1$ or $ 1, 2, 3, 4, 5, 6, 7,$ or $ 11, 9, 7, 5, 3, 1, -1$ to any row or column.
kevinatcausa
15.12.2009 23:00
An unmotivated proof:
Consider the expression $ a_{22}-2a_{23}+a_{24}-2a_{32}+4a_{33}-2a_{34}+a_{42}-2a_{43}+a_{44}$. It can be directly verified that
(1) This expression remains invariant when an arithmetic progression is added to any row or column.
(2) If each row of numbers in the table is an arithmetic progression, the expression is 0.
(3) The expression is 4 for the initial table.
What's really going on (and where the above expression came from):
The polynomial in question has an $ x^2 y^2$ term, so has a nonzero fourth partial derivative $ f_{xxyy}$. But arithmetic progressions are linear functions, so their second derivative vanishes. Taking a $ f_{xxyy}$ derivative cancels both the row progressions and the column progressions, so the fourth derivative never changes. The strange looking invariant above is just the discrete analogue of this derivative.
Alternatively, you can arrive at the expression by realizing that if you want to do an invariant argument, you want something that adds to 0 for arithmetic progressions. For one-dimensional progressions, you have $ a_{i-1}+a_{i+1}=2a_i$, and the question is just what the proper 2-dimensional analogue of this is.
P-H-David-Clarence
30.10.2016 11:48
I think this one is the simplest among the problems that year!