INMO 2018

Without loss of generality, we may assume that $a_{1}$ is the largest among $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}$. Consider the relation

This leads to

Observe that $a_{1} \geq a_{2}$ and $a_{3}>0$ together imply that the second factor on the left side is positive. Thus $a_{1}=a_{3}=\max \left\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\right\}$. Using this and the relation

we conclude that $a_{3}=a_{5}$ as above. Thus we have

Let us consider the other relations. Using

we get $a_{2}=a_{4}$ or $a_{2}+a_{4}=a_{3}=a_{1}$. Similarly, two more relations give either $a_{4}=a_{6}$ or $a_{4}+a_{6}=a_{5}=a_{1}$; and either $a_{6}=a_{2}$ or $a_{6}+a_{2}=a_{1}$. Let us give values to $a_{1}$ and count the number of six-tuples in each case.

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

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

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

(D) In the case $a_{1}=4$, we have $a_{3}=a_{5}=4$ and

Thus we get $1+2+9+10=22$ solutions. Since $\left(a_{1}, a_{3}, a_{5}\right)$ and $\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)$ and $(4,4,4,4,4,4)$. Hence the total number of six-tuples is $22+22-4=40$.

Let $D$ be the mid-point of $BC$; $M$ that of $HK$; and $T$ that of $OH$. Then $PM$ is perpendicular to $HK$ and $PT$ is perpendicular to $OH$. Since $Q$ is the reflection of $P$ in $HO$, we observe that $P, T, Q$ are collinear, and $PT = TQ$. Let $QL$, $TN$ and $OS$ be the perpendiculars drawn respectively from $Q$, $T$ and $O$ onto the altitude $AK$. (See the figure.)

We have $LN = NM$, since $T$ is the mid-point of $QP$; $HN = NS$, since $T$ is the mid-point of $OH$; and $HM = MK$, as $P$ is the circumcentre of $KHO$. We obtain

which gives $LH = SM$. We know that $AH = 2OD$. Thus

This shows that $L$ is the mid-point of $AK$ and hence lies on the line joining the mid-points of $AB$ and $AC$. We observe that the line joining the mid-points of $AB$ and $AC$ is also perpendicular to $AK$. Since $QL$ is perpendicular to $AK$, we conclude that $Q$ also lies on the line joining the mid-points of $AB$ and $AC$.

Remark: It may happen that $H$ is above $L$ as in the adjoining figure, but the result remains true here as well. We have $HN = NS$, $LN = NM$, and $HM = MK$ as earlier. Thus $HN = HL + LN$ and $NS = SM + NM$ give $HL = SM$. Now $AL = AH + HL = 2OD + SM = 2SK + SM = SK + (SK + SM) = SK + MK = SK + HM = SK + HL + LM = SK + SM + LM = LK$. The conclusion that $Q$ lies on the line joining the mid-points of $AB$ and $AC$ follows as earlier.

a. Consider $f(j)=a_{m+j}+(-1)^{j} a_{m-j}$, $0 \leq j \leq m$, where $m$ is a natural number. We observe that $f(0)=2 a_{m}$ is divisible by $2 a_{m}$. Similarly,

is also divisible by $2 a_{m}$. Assume that $2 a_{m}$ divides $f(j)$ for all $0 \leq j<l$, where $l \leq m$. We prove that $2 a_{m}$ divides $f(l)$. Observe

Thus we have

This gives

By induction hypothesis $2 a_{m}$ divides $f(l-1)$ and $f(l-2)$. Hence $2 a_{m}$ divides $f(l)$. We conclude that $2 a_{m}$ divides $f(j)$ for $0 \leq j \leq m$.

b. We see that $f(m)=a_{2 m}$. Hence $2 a_{m}$ divides $a_{2 m}$ for all natural numbers $m$. Let $n=2^{k} l$ for some $l \geq 1$. Taking $m=2^{k-1} l$, we see that $2 a_{m}$ divides $a_{n}$. Using an easy induction, we conclude that $2^{k} a_{l}$ divides $a_{n}$. In particular $2^{k}$ divides $a_{n}$.

Solution 1.

Suppose $n \in \mathbb{N}$ is faithful. Let $k \in \mathbb{N}$ and consider $k n$. Since $n = a + b + c$, with $a < b < c$, $a \mid b$ and $b \mid c$, we see that $k n = k a + k b + k c$ which shows that $k n$ is faithful.

Let $p > 5$ be a prime. Then $p$ is odd and $p = (p - 3) + 2 + 1$ shows that $p$ is faithful. If $n \in \mathbb{N}$ contains a prime factor $p > 5$, then the above observation shows that $n$ is faithful. This shows that a number which is not faithful must be of the form $2^{\alpha} 3^{\beta} 5^{\gamma}$. We also observe that $2^{4} = 16 = 12 + 3 + 1$, $3^{2} = 9 = 6 + 2 + 1$ and $5^{2} = 25 = 22 + 2 + 1$, so that $2^{4}$, $3^{2}$ and $5^{2}$ are faithful. Hence $n \in \mathbb{N}$ is also faithful if it contains a factor of the form $2^{\alpha}$ where $\alpha \geq 4$; a factor of the form $3^{\beta}$ where $\beta \geq 2$; or a factor of the form $5^{\gamma}$ where $\gamma \geq 2$. Thus the numbers which are not faithful are of the form $2^{\alpha} 3^{\beta} 5^{\gamma}$, where $\alpha \leq 3$, $\beta \leq 1$ and $\gamma \leq 1$. We may enumerate all such numbers:

Among these $120 = 112 + 7 + 1$, $60 = 48 + 8 + 4$, $40 = 36 + 3 + 1$, $30 = 18 + 9 + 3$, $20 = 12 + 6 + 2$, $15 = 12 + 2 + 1$, and $10 = 6 + 3 + 1$. It is easy to check that the other numbers cannot be written in the required form. Hence the only numbers which are not faithful are

Their sum is $65$.

Solution 2.

If $n = a + b + c$ with $a < b < c$ is faithful, we see that $a \geq 1$, $b \geq 2$ and $c \geq 4$. Hence $n \geq 7$. Thus $1, 2, 3, 4, 5, 6$ are not faithful. As observed earlier, $k n$ is faithful whenever $n$ is. We also notice that for odd $n \geq 7$, we can write $n = 1 + 2 + (n - 3)$ so that all odd $n \geq 7$ are faithful. Consider $2 n, 4 n, 8 n$, where $n \geq 7$ is odd. By observation, they are all faithful. Let us list a few of them:

We observe that $16 = 12 + 3 + 1$ and hence it is faithful. Thus all multiples of $16$ are also faithful. Thus we see that $16, 32, 48, 64, \ldots$ are faithful. Any even number which is not a multiple of $16$ must be either an odd multiple of $2$, or that of $4$, or that of $8$. Hence, the only numbers not covered by this process are $8, 10, 12, 20, 24, 40$. Of these, we see that

so that $10, 20, 40$ are faithful. Thus the only numbers which are not faithful are

Their sum is $65$.

Solution 1.

Suppose four distinct points $P, Q, R, S$ (in that order on the circle) among these five are such that $\widehat{P Q}=\widehat{R S}$. Then $P Q R S$ is an isosceles trapezium, with $P S \parallel Q R$. We use this in our argument.

• If four of the five points chosen are adjacent, then we are through as observed earlier. (In this case four points $A, B, C, D$ are such that $\widehat{A B}=\widehat{B C}=\widehat{C D}$.) See Fig 1.

Fig 1. Fig 2. Fig 3.

• Suppose only three of the vertices are adjacent, say $A, B, C$ (see Fig 2.) Then the remaining two must be among $E, F, G, H$. If these two are adjacent vertices, we can pair them with $A, B$ or $B, C$ to get equal arcs. If they are not adjacent, then they must be either $E, G$ or $F, H$ or $E, H$. In the first two cases, we can pair them with $A, C$ to get equal arcs. In the last case, we observe that $\widehat{H A}=\widehat{C E}$ and $A H E C$ is an isosceles trapezium.

• Suppose only two among the five are adjacent, say $A, B$. Then the remaining three are among $D, E, F, G, H$. (See Fig 3.) If any two of these are adjacent, we can combine them with $A, B$ to get equal arcs. If no two among these three vertices are adjacent, then they must be $D, F, H$. In this case $\widehat{H A}=\widehat{B D}$ and $A H D B$ is an isosceles trapezium.

Finally, if we choose 5 among the 9 vertices of a regular nine-sided polygon, then some two must be adjacent. Thus any choice of 5 among 9 must fall into one of the above three possibilities.

Solution 2.

Here is another solution used by many students. Suppose you join the vertices of the nine-sided regular polygon. You get $\binom{9}{2}=36$ line segments. All these fall into 9 sets of parallel lines. Now using any 5 points, you get $\binom{5}{2}=10$ line segments. By pigeon-hole principle, two of these must be parallel. But, these parallel lines determine a trapezium.

Let $O$ be the centre of the circle in which $ABCD$ is inscribed and let $R$ be its radius. Using cosine rule in triangle $AOB$, we have

Hence $R=1$.

Consider quadrilateral $ABCD$ as in the second figure above. Join $AC$. For $[ADC]$ to be maximum, it is clear that $D$ should be the mid-point of the arc $AC$ so that its distance from the segment $AC$ is maximum. Hence $AD = DC$ for $[ABCD]$ to be maximum. Similarly, we conclude that $BC = CD$. Thus $BC = CD = DA$ which fixes the quadrilateral $ABCD$. Therefore each of the sides $BC, CD, DA$ subtends equal angles at the centre $O$.

Let $\angle BOC = \alpha$, $\angle COD = \beta$ and $\angle DOA = \gamma$. Observe that

Now $[ABCD]$ has maximum area if and only if $\alpha = \beta = \gamma = \left(360^{\circ} - 135^{\circ}\right)/3 = 75^{\circ}$. Thus

Alternatively, we can use Jensen’s inequality. Observe that $\alpha, \beta, \gamma$ are all less than $180^{\circ}$. Since $\sin x$ is concave on $(0, \pi)$, Jensen’s inequality gives

Hence

with equality if and only if $\alpha = \beta = \gamma = 75^{\circ}$.