# Ordered quadruples in a grid

Moderator Note: This question is from a contest which ended on 22 Oct 2012.

Consider $(\alpha_1, \alpha_2, \alpha_3, \alpha_4)$ such that the ordered quadruple satisfies the following:

$\alpha_m= am^2 +bm +c$ for $m=1,2,3,4$ for some real numbers $a,b,c.$

Suppose we consider a square grid that measured four on each side, and fill it such that the ordered quadruples making up all the rows as well as the ordered quadruples making up the first three columns satisfied the above condition. How can we prove that the fourth column will also contain an ordered quadruple satisfying the condition?

-
also mention that the question is a homework problem and tag it as such. – rrampage Sep 20 '12 at 1:19
The problem is not homework- it is part of a problem writing session that myself and some friends had. Someone proposed the problem after tinkering with it, but none of us have been able to find a proof. – Aria Fitzpatrick Sep 30 '12 at 18:35

A sequence $(x_k)_{k\geq 1}$ of numbers can be produced by a linear polynomial in the form $$x_k= bk + c\qquad(k\geq 1)$$ with suitable coefficients $b$, $c$ iff the first differences $x_{k+1}-x_k$ are all equal. Similarly, the $x_k$ can be produced by a quadratic polynomial in the form $$x_k=a k^2 + bk + c\qquad(k\geq1)$$ with suitable coefficients $a$, $b$, $c$ iff their second differences $(x_{k+2}-x_{k+1})-(x_{k+1}-x_k)$ are all equal.

In our case of just four numbers $x_1$, $x_2$, $x_3$, $x_4$ this amounts to the single condition $$(x_4-x_3)-(x_3-x_2)=(x_3-x_2)-(x_2-x_1)\ ,$$ which is the same as $$x_4=3x_3-3x_2+x_1\ .\qquad(*)$$ Using this for the rows of your$4\times4$ matrix (not "grid") $A=\bigl[a_{ik}\bigr]$ we see that it is of the form $$\bigl[a_{ik}\bigr]=\left[\matrix{ a_{11}&a_{12}&a_{13}& (3a_{13}-3a_{12}+a_{11}) \cr a_{21}&a_{22}&a_{23}& (3a_{23}-3a_{22}+a_{21}) \cr a_{31}&a_{32}&a_{33}& (3a_{33}-3a_{32}+a_{31}) \cr a_{41}&a_{42}&a_{43}& (3a_{43}-3a_{42}+a_{41}) \cr}\right]\ .$$ Since the first three columns of $A$ should also fall into this pattern we necessarily have $$a_{41}=3 a_{31}-3a_{21}+a_{11}\ ,\quad a_{42}=3 a_{32}-3a_{22}+a_{12}\ , \quad a_{43}=3 a_{33}-3a_{23}+a_{13}\ .$$ This implies \eqalign{a_{44}&= 3a_{43}-3a_{42}+a_{41}\cr &=3(3 a_{33}-3a_{23}+a_{13})-3(3 a_{32}-3a_{22}+a_{12})+(3 a_{31}-3a_{21}+a_{11})\cr & =3(3a_{33}-3a_{32}+a_{31})-3(3a_{23}-3a_{22}+a_{21})+(3a_{13}-3a_{12}+a_{11})\cr &=3a_{34}-3 a_{24}+a_{14}\ .\cr} This shows that the fourth column of $A$ fulfills condition $(*)$ automatically.

-
"...doing the algebra one can verify that a fourth number satisfies..." Could you demonstrate this algebra? I am curious... perhaps Aria will understand. – Xuan Huang Sep 30 '12 at 19:46
@Danielle Huang: See my edit. You get $p$ by setting up $p$ with undetermined coefficients $a$, $b$, $c$ and solving the linear system $p(k)=x_k$ $\ (1\leq k\leq3)$ for $a$, $b$, $c$. – Christian Blatter Sep 30 '12 at 19:56
@ChristianBlatter I tried to understand this as well... could you either explain the solution without the LaGrange polynomial or justify the LaGrange polynomial entirely- and its algebra- in the context of the problem? – Aria Fitzpatrick Sep 30 '12 at 22:50
@ChristianBlatter I have tried to understand the intuition behind the polynomial as well as the algebra... could you either re-explain the solution without the Langrange polynomial or fully explain/expand upon the solution-and the algebra- in the context of the LaGrange polynomial? – Aria Fitzpatrick Sep 30 '12 at 23:08
@Aria Fitzpatrick: I now have eliminated the word "Lagrange" from my post. – Christian Blatter Oct 1 '12 at 8:29

As $(\alpha_1, \alpha_2, \alpha_3, \alpha_4)$ satisfy the following:

$\alpha_m= am^2 +bm +c$ for $m=1,2,3,4$ for some real numbers $a,b,c.$

When we consider a 4 x 4 square grid and fill it such that the ordered quadruples making up all 4 rows as well as the ordered quadruples making up the first 3 columns.

In order to satisfy the above condition, lets see the relations between the $\alpha_i$ of each column given that we have 4 ordered quadruples in each row.

The $c_i$ must be equal for all the $\alpha_i$ in the grid else the constraint will immediately be violated.

The $b_i$ must have the ratio 1:2:3:4 for each column assuming The $b_i$ must have the ratio 1:2:3:4 for each column. (Substitute and try it out to get the feel)

The $a_i$ must have the ratio 1:4:9:16 for each column so that all the columns satisfy the condition of fitting in the grid. ($a_i$ is the quadratic coefficient, hence the ratio for $b_i$ will be squared)

Finally, lets consider the last column:

we have (16$a_1$ + 4$b_1$ + $c_1$, 16$a_2$ + 4$b_2$ + $c_2$, 16$a_3$ + 4$b_3$ + $c_3$, 16$a_4$ + 4$b_4$ + $c_4$)

As all the $c_i$ are equal, substituting the ratios from earlier, we get:

16$a_1$ + 4$b_1$ + $c_1$, 64$a_1$ + 8$b_1$ + $c_1$, 144$a_1$ + 12$b_1$ + $c_1$, 256$a_1$ + 16$b_1$ + $c_1$

which follow the ordered quadruple $\alpha_m= 16a_1m^2 +4b_1m +c_1$ for $m=1,2,3,4$

QED

-
a,b,c don't have to be integers.Also, could you edit your latex a little? – Aria Fitzpatrick Sep 20 '12 at 0:43
@AriaFitzpatrick it was mentioned in your question that a,b,c are integers. Hence I added it. Also, this answer is valid regardless of whether a,b,c are integers. – rrampage Sep 20 '12 at 0:47
@AriaFitzpatrick I have modified in my answer that a,b,c are real numbers and suggest that you also change it in the question. – rrampage Sep 20 '12 at 1:08
I am not entirely certain as to what you are saying when you say: four quadruples in each row. And what do you mean by "the $c_i$" or "the $a_i$"? Why would the constraint be immediately violated if $c_i$ matched $a_i$ in the grid? Could you please explain your solution further on all counts? Thanks. :) – Aria Fitzpatrick Sep 20 '12 at 3:06
Say c1 != c2. This means that for any 2 $\alpha_i$ in a column, the numbers will not be part of an ordered quadruple. Since we are comparing $c_i$ in two different rows, they must be all be equal. – rrampage Sep 20 '12 at 3:18