Maths Olympiad Prep

Library / /105 of 121

Combinatorics Difficulty 6.9 National Olympiad Prove it India

Problem:

How many 6-tuples (a1,a2,a3,a4,a5,a6)\left(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\right) are there such that each of a1,a2,a3,a4,a5,a6a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6} is from the set {1,2,3,4}\{1,2,3,4\} and the six expressions
aj2ajaj+1+aj+12 a_{j}^{2}-a_{j} a_{j+1}+a_{j+1}^{2}
for j=1,2,3,4,5,6j=1,2,3,4,5,6 (where a7a_{7} is to be taken as a1a_{1}) are all equal to one another?

Solution

Solution:

Without loss of generality, we may assume that a1a_{1} is the largest among a1,a2,a3,a4,a5,a6a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}. Consider the relation
a12a1a2+a22=a22a2a3+a32 a_{1}^{2}-a_{1} a_{2}+a_{2}^{2}=a_{2}^{2}-a_{2} a_{3}+a_{3}^{2}
This leads to
(a1a3)(a1+a3a2)=0 \left(a_{1}-a_{3}\right)\left(a_{1}+a_{3}-a_{2}\right)=0
Observe that a1a2a_{1} \geq a_{2} and a3>0a_{3}>0 together imply that the second factor on the left side is positive. Thus a1=a3=max{a1,a2,a3,a4,a5,a6}a_{1}=a_{3}=\max \left\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\right\}. Using this and the relation
a32a3a4+a42=a42a4a5+a52 a_{3}^{2}-a_{3} a_{4}+a_{4}^{2}=a_{4}^{2}-a_{4} a_{5}+a_{5}^{2}
we conclude that a3=a5a_{3}=a_{5} as above. Thus we have
a1=a3=a5=max{a1,a2,a3,a4,a5,a6} a_{1}=a_{3}=a_{5}=\max \left\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\right\}
Let us consider the other relations. Using
a22a2a3+a32=a32a3a4+a42 a_{2}^{2}-a_{2} a_{3}+a_{3}^{2}=a_{3}^{2}-a_{3} a_{4}+a_{4}^{2}
we get a2=a4a_{2}=a_{4} or a2+a4=a3=a1a_{2}+a_{4}=a_{3}=a_{1}. Similarly, two more relations give either a4=a6a_{4}=a_{6} or a4+a6=a5=a1a_{4}+a_{6}=a_{5}=a_{1}; and either a6=a2a_{6}=a_{2} or a6+a2=a1a_{6}+a_{2}=a_{1}. Let us give values to a1a_{1} and count the number of six-tuples in each case.

(A) Suppose a1=1a_{1}=1. In this case all aja_{j}'s are equal and we get only one six-tuple (1,1,1,1,1,1)(1,1,1,1,1,1).

(B) If a1=2a_{1}=2, we have a3=a5=2a_{3}=a_{5}=2. We observe that a2=a4=a6=1a_{2}=a_{4}=a_{6}=1 or a2=a4=a6=2a_{2}=a_{4}=a_{6}=2. We get two more six-tuples: (2,1,2,1,2,1),(2,2,2,2,2,2)(2,1,2,1,2,1), (2,2,2,2,2,2).

(C) Taking a1=3a_{1}=3, we see that a3=a5=3a_{3}=a_{5}=3. In this case we get nine possibilities for (a2,a4,a6)\left(a_{2}, a_{4}, a_{6}\right)
(1,1,1),(2,2,2),(3,3,3),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1) (1,1,1), (2,2,2), (3,3,3), (1,1,2), (1,2,1), (2,1,1), (1,2,2), (2,1,2), (2,2,1)

(D) In the case a1=4a_{1}=4, we have a3=a5=4a_{3}=a_{5}=4 and
(a2,a4,a6)=(2,2,2),(4,4,4),(1,1,1),(3,3,3),(1,1,3),(1,3,1),(3,1,1),(1,3,3),(3,1,3),(3,3,1) \begin{aligned} \left(a_{2}, a_{4}, a_{6}\right)=(2,2,2), (4,4,4), (1,1,1), (3,3,3), \\ (1,1,3), (1,3,1), (3,1,1), (1,3,3), (3,1,3), (3,3,1) \end{aligned}
Thus we get 1+2+9+10=221+2+9+10=22 solutions. Since (a1,a3,a5)\left(a_{1}, a_{3}, a_{5}\right) and (a2,a4,a6)\left(a_{2}, a_{4}, a_{6}\right) may be interchanged, we get 22 more six-tuples. However there are 4 common among these, namely, (1,1,1,1,1,1),(2,2,2,2,2,2),(3,3,3,3,3,3)(1,1,1,1,1,1), (2,2,2,2,2,2), (3,3,3,3,3,3) and (4,4,4,4,4,4)(4,4,4,4,4,4). Hence the total number of six-tuples is 22+224=4022+22-4=40.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.