Maths Olympiad Prep

Library / /37 of 42

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Ireland

For n3n \ge 3, a special n-triangle is a triangle with nn distinct numbers on each side such that the sum of the numbers on a side is the same for all sides. For instance, because 41+23+43=43+17+47=47+19+4141 + 23 + 43 = 43 + 17 + 47 = 47 + 19 + 41, the following is a special 3-triangle:
412319431747 \begin{array}{c c c} & 41 & \\ 23 & 19 & \\ 43 & 17 & 47 \end{array}
Note that a special nn-triangle contains 3(n1)3(n-1) numbers.
An infinite set AA of positive integers is a special set if, for each n3n \ge 3, the smallest 3(n1)3(n-1) numbers of AA can be used to form a special nn-triangle.
Show that the set of positive integers that are not multiples of 2023 is a special set.

Solution

For each N>1N > 1, let ANA_N denote the set of all positive integers that are not multiples of NN, and let aN,1<aN,2<aN,3<a_{N,1} < a_{N,2} < a_{N,3} < \dots be the elements of ANA_N in increasing order. The set ANA_N consists of blocks of N1N-1 consecutive integers followed by a skipped integer. If N1(mod3)N \equiv 1 \pmod 3 the length of each of these blocks is a multiple of 3 and so aN,ia_{N,i} can only be the last element of a block if ii is divisible by 3. In other words:
If N1(mod3) and i0(mod3), then aN,i+1=aN,i+1.(1) \text{If } N \equiv 1 \pmod 3 \text{ and } i \neq 0 \pmod 3, \text{ then } a_{N,i+1} = a_{N,i} + 1. \quad (1)
For each N>1N > 1 that satisfies N1(mod3)N \equiv 1 \pmod 3, we will show that ANA_N is a special set. Since 20231(mod3)2023 \equiv 1 \pmod 3, the desired result follows.
We now fix N>1N > 1 satisfying N1(mod3)N \equiv 1 \pmod 3. For simplicity, from now on we suppress the NN index in aN,ia_{N,i}. We will use induction to show that for each n3n \ge 3, the numbers a1,a2,a3,,a3n3a_1, a_2, a_3, \dots, a_{3n-3} can be used to form a special nn-triangle.
The base case consists in showing that there are special 3- and 4-triangles.
a1a1a6a5a6a9a2a4a3a7a5a3a4a8a2 \begin{array}{ccccccc} & a_1 & & a_1 & & \\ & a_6 & a_5 & & a_6 & a_9 & \\ a_2 & a_4 & a_3 & a_7 & & a_5 & \\ & & & a_3 & a_4 & a_8 & a_2 \end{array}

When N10N \ge 10, ai=ia_i = i for 1i91 \le i \le 9, and it is easily checked that these triangles are special. For N=4N = 4 the above turns into
Figure 1
and when N=7N = 7 we get
Figure 2
and these are indeed special triangles.
For the inductive step, we show how to obtain a special nn-triangle for ANA_N from a special (n2)(n-2)-triangle for ANA_N. Any special (n2)(n-2)-triangle contains the numbers a1,a2,,a3n9a_1, a_2, \dots, a_{3n-9}. We group the next six numbers of ANA_N into two sets, S1={a3n8,a3n7,a3n6}S_1 = \{a_{3n-8}, a_{3n-7}, a_{3n-6}\} and S2={a3n5,a3n4,a3n3}S_2 = \{a_{3n-5}, a_{3n-4}, a_{3n-3}\}. By virtue of statement (1), both sets consist of three consecutive integers. Hence,
a3n3+a3n8=a3n4+a3n7=a3n5+a3n6. a_{3n-3} + a_{3n-8} = a_{3n-4} + a_{3n-7} = a_{3n-5} + a_{3n-6}.
It is now clear that we obtain a special nn-triangle when we add a3n3a_{3n-3} and a3n8a_{3n-8} to one side, a3n4a_{3n-4} and a3n7a_{3n-7} to another, and a3n5a_{3n-5} and a3n6a_{3n-6} to the final side in any given special (n2)(n-2)-triangle.

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 and solution reproduced as published; topic and difficulty added by this site.