Find all permutations $a_1, a_2, \ldots, a_9$ of $1, 2, \ldots, 9$ such that \[ a_1+a_2+a_3+a_4=a_4+a_5+a_6+a_7= a_7+a_8+a_9+a_1 \] and \[ a_1^2+a_2^2+a_3^2+a_4^2=a_4^2+a_5^2+a_6^2+a_7^2= a_7^2+a_8^2+a_9^2+a_1^2 \]
Problem
Source: APMO 2000
Tags: combinatorics unsolved, combinatorics
frejer
02.04.2006 07:40
lemma 1: if we have x1,x2,x3,x4 are integer numbers and: x1+x2=x3+x4 (mod 3) x1x2= x3x4 (mod 3) then we have {x1,x2}={x3,x4} ( mod 3) lemma 2: (a1,a2,...,a9) is a root of this equation. Then all permutations of that set that a1,a4,a7 or a2,a3 or a5,a6 or a8,a9 are permuted are all also roots of this equation. We can say that a1,a4,a7 are same rolls. a2,a3 are same rolls. a5,a6 are same rolls. a8,a9 are same rolls. We easily have that: a1+a4+a7 mod 3= 0 (a1)^2+(a4)^2+(a7)^2 mod 3 =0 hence, there are always at least 2 of these 3 numbers are the same in mod 3. Using lemma 2 ,we can suppose a1=a7=a; a4= b (certainly in mod 3) if a+ba1+a2+a3+a4=a4+a5+a6+a7 and (a1)^2+(a2)^2+(a3)^2+(a4)^2= (a4)^2+(a5)^2+(a6)^2+(a7)^2 show that: a2+a3=a5+a6 (mod 3) and a2a3=a5a6 (mod 3) hence, {a2,a3}={a5,a6} => {a2,a3}={b,c} So, {a8,a9}={a,c} => b=c (contradic) So, a=b We can easily do the next step since we have a1=a4=a7 (mod 3)
max1546
08.01.2007 10:18
I was wondering is there any other way to solving this? For example how they did for the official APMO solution. But I think the official solution was slightly unclear...at least to me. could anyone try and explain the question or provide a similar one which is simple please? or if better how to solve all these kinds of problems in general.
cpma213
16.08.2016 00:48
Could anyone make suggestions/point out errors in this solution?
WLOG, let $a_1 < a_4 < a_7$. Also, WLOG let $a_{3i-1} < a_{3i}$ for $i = 1, 2, 3$.
Adding the three expressions in the 1st equality yields $2a_1 + a_2 + a_3 + 2a_4 + a_5 + a_6 + 2a_7 + a_8 + a_9 = 45 + a_1 + a_4 + a_7$.
Thus, since the three expressions were equal, their sum is divisible by 3. Thus, $45 + a_1 + a_4 + a_7$ is divisible by 3.
This implies that $3\mid a_1 + a_4 + a_7$. Doing the same for the 2nd equality yields $3\mid 285 + a_1^2 + a_4^2 + a_7^2$, or $3\mid a_1^2 + a_4^2 + a_7^2.$
The only solutions to these equations are $a_1 \equiv a_4 \equiv a_7 (mod 3)$. We now have three cases:
Case 1: The common modular residue is 1.
From the WLOG, $a_1 = 1$, $a_4 = 4$, and $a_7 = 7$. Then, $a_1^2 + a_2^2 + a_3^2 + a_4^2 = (285 + a_1^2 + a_4^2 + a_7^2)/3 = (285+66)/3 = 117$.
Thus, $a_2^2 + a_3^2 = 117 - a_1^2 - a_4^2 \implies a_2^2 + a_3^2 = 100$, which only has the solution $a_2 = 6$, and $a_3 = 8$. But then, $a_5^2 + a_6^2 = 52$, and $a_8^2 + a_9^2 = 67$. Since $81>67, 81>52$, each of $a_5, a_6, a_8, a_9$ is less than 9. But this is contradiction, since one of these must be 9(9 has not appeared in the permutation yet). Thus, this case is impossible.
Case 2: The common modular residue is 2.
Following a similar procedure to case 1, $a_1 = 2$, $a_4 = 5$, $a_7 = 8$, and $a_1^2 + a_2^2 + a_3^2 + a_4^2 = 126$. This yields that $a_2^2 + a_3^2 = 97 \implies a_2 = 4, a_3 = 9$. Similarly, $a_5^2 + a_6^2 = 37 \implies a_5 = 1, a_6 = 6$, and $a_8^2 + a_9^2 = 58 \implies a_8 = 3, a_9 = 7$.
Since $2 + 4 + 9 + 5 = 5 + 1 + 6 + 8 = 8 + 3 + 7 + 2 = 20$, this permutation does indeed satisfy the conditions. However, removing the WLOG restriction, swapping $a_{3i}$ and $a_{3i-1}$ keeps the validity of the permutation, for $i = 1,2,3$. Permuting around the sets $ \{a_1, a_2, a_3, a_4\}$, $\{a_4, a_5, a_6, a_7\}$, $\{a_7, a_8, a_9, a_1\}$ (for instance, permuting $\{a_1, a_2, a_3, a_4\}$, $\{a_4, a_5, a_6, a_7\}$, $\{a_7, a_8, a_9, a_1\}$ from {2, 4, 9, 5}, {5, 1, 6, 8}, {8, 3, 7, 2} to {8, 3, 7, 2}, {5, 1, 6, 8}, {2, 4, 9, 5}.)
Case 3: The common modular residue is 3.
Following the same procedure yields $a_2^2 + a_3^2 = 137 - 45 = 92$. However, this has no integer solutions. Thus, this case has no solutions.
Thus, the permutations that satisfy the given equalities are found from $(2, 9, 4, 5, 1, 6, 8, 3, 7)$, and others found by swapping $a_{3i}$ and $a_{3i-1}$ for $i = 1,2,3$, or by permuting the sets $ \{a_1, a_2, a_3, a_4\}$, $\{a_4, a_5, a_6, a_7\}$, $\{a_7, a_8, a_9, a_1\}$ as described above in case 2.
MADharm
12.10.2018 16:56
@cpma213 can you more explain why does 45+a_1+a_2+a_3 is dibisible by 3?thanks
cpma213
17.10.2018 05:13
$45 + a_1 + a_4 + a_7 = (a_1+a_2+\ldots+a_9) + a_1 + a_4 + a_7$, since $a_1, a_2, \ldots, a_9$ form a permutation of the numbers $1, 2, \ldots 9$. This in turn is $a_1 + a_2 + a_3 + a_4 + a_4 + a_5 + a_6 + a_7 + a_7 + a_8 + a_9 + a_1 = 3(a_1 + a_2 + a_3 + a_4)$, by the given condition.
palisade
01.08.2019 05:31
There are 4 even integers to use. Any of them can be counted in one or two of the three equal expressions, and each of the expressions must have the same number of even integers (consider the squares mod 4). The total number of times even integers will appear in the three sums is between 4 and 8, but must be divisible by three, so each each sum has exactly two even integers, and two of the four even integers are counted twice, so they are among $a_1, a_4, a_7$. Now note: $$3(a_1+a_2+a_3+a_4) = (a_1+a_2+a_3+a_4) + (a_4+a_5+a_6+a_7) + (a_7+a_8+a_9+a_1)= 45 + a_1 + a_4 + a_7$$ Thus $3|(a_1+a_4+a_7)$ so either all are congruent mod 3 or all are distinct. The latter cannot be true because all of the sums must have the same number of multiples of three (consider the squares mod 3). Thus the only option is $2,5,8$ since two of these must be even. Now the sum of all three sums is $45+2+5+8=60$ so each sum is $20$. Whichever sum has $2,5$ in it must have either $9,4$ or $7,6$ as the other two. We can check each of these, filling in the rest with the fact that each side has one multiple of three and two even numbers, to find that $$\{2,9,4,5\} \{5,1,6,8\} \{8,3,7,2\}$$ and its associated permutations are the only solutions.
Chimphechunu
01.08.2019 05:42
very hard problem!
TFIRSTMGMEDALIST
16.02.2022 01:14
it can be easily done by cases on congruence of x1 x4 x7 MOD 3
huashiliao2020
16.08.2023 00:08
Notice $45 + a_1 + a_4 + a_7 =2a_1 + a_2 + a_3 + 2a_4 + a_5 + a_6 + 2a_7 + a_8 + a_9 = 3(a_1 + a_2 + a_3 + a_4)$; in particular, a_1,a_4,a_7 are either all congruent or all distinct mod 3. In the same way we get 285+a_1^2+a_4^2+a_7^2=3(a_1^2+a_2^2+a_3^2+a_4^2); in particular, if they're distinct mod 3 the RHS is 0 mod 3 but LHS is not 0 mod 3. Case 1. a_1,a_4,a_7=1,4,7. Then a_2+a_3=6+a_5+a_6, a_7+a_8=3+a_5+a_6, so it follows by adding them onto a_5+a_6 that a_5+a_6=8, so a_5,a_6=2,6 or 3,5; keep caseworking like this until the end (im lazy to type this up but its easy casework) Case 2 and 3 do the same thing solutions are (2,9,4,5,1,6,8,3,7) and permutations by cyclically switching them by 3 spots.