0
$\begingroup$

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?

2 Answers 2

3

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.

  • 0
    "...doing the algebra one can verify that a fourth number satisfies..." Could you demonstrate this algebra? I am curious... perhaps Aria will understand.2012-09-30
  • 0
    @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$.2012-09-30
  • 0
    @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?2012-09-30
  • 0
    @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?2012-09-30
  • 0
    @Aria Fitzpatrick: I now have eliminated the word "Lagrange" from my post.2012-10-01
  • 0
    @ChristianBlatter I was not referring to the word "LaGrange" as much as I was to you not justifying certain things. For instance, from where does the information regarding the first and second differences needing to be equal if they are produced by a linear/quadratic polynomial come from? Could you justify the logic of that further?2012-10-01
  • 0
    @Aria Fitzpatrick: No. Think about it, and you will have learnt something.2012-10-01
  • 0
    @ChristianBlatter is $a_44$ the same as what otherwise would have been $x_44$? Or am I missing something?2012-10-04
  • 0
    @Aria Fitzpatrick: See my edit. Hope, it's clearer now.2012-10-04
  • 0
    @ Thanks, Christian!2012-10-04
  • 0
    @ChristianBlatter Are we using the conditions of the linear polynomial at all when doing our proof?2012-10-19
  • 0
    @Danielle Huang: No; I just referred to the "linear" case for didactical reasons. It made the "quadratic" case more believable for a newcomer.2012-10-20
  • 0
    @ChristianBlatter I am not entirely sure of the logic of this step either. Would you be able to explain?: $3(3 a_{33}-3a_{23}+a_{13})-3(3 a_{32}-3a_{22}+a_{12})+(3 a_{31}-3a_{21}+a_{11}) =3(3a_{33}-3a_{32}+a_{31})-3(3a_{23}-3a_{22}+a_{21})+(3a_{13}-3a_{12}+a_{11})$.2012-10-21
  • 0
    @ChristianBlatter As far as I can see, you have reversed all the subscripts of $a$ in the step. I do not understand, however, why the step is true.2012-10-22
  • 0
    @Danielle Huang: The occurring terms have been grouped in a different way. There is no reversing of indices here.2012-10-22
2

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

  • 0
    a,b,c don't have to be integers.Also, could you edit your latex a little?2012-09-20
  • 0
    @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.2012-09-20
  • 0
    @AriaFitzpatrick I have modified in my answer that a,b,c are real numbers and suggest that you also change it in the question.2012-09-20
  • 0
    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. :)2012-09-20
  • 0
    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.2012-09-20
  • 0
    I'm not sure what you mean by that- any 2$\alpha_i$? Again, could you further explain the whole "all $b_i$/$c_i$/etc concept? Is it overlapping quadruples?2012-09-20
  • 0
    We already have 4 rows of ordered quadruples each with $c_i$ different. Now, we know that 3 columns are ordered quadruples. This means for any 2 of them in the same column, the constant term i.e $c_i$ must be the same (else they will not be an ordered tuple). For this assumption of 3 columns to be ordered quadruples, all $c_i$ must be the same.2012-09-20
  • 0
    Similarly, for $b_i$, lets compare the 1st two $\alpha_i$ in the first column. We have $\alpha_11$ = a11 + b11 + c1. $\alpha_12$ = a12 + b12 + c12. For both these to be part of the *same* quadruple (given that the 1st column is a quadruple), $a_12$ = 4$a_11$, $b_12$ = 2$b_11$ (as m = 2)2012-09-20