Maths Olympiad Prep

Library / /125 of 155

Number theory Difficulty 6.8 National olympiad Prove it Saudi Arabia

Let n4n \geq 4 be a positive integer and there exist nn positive integers that are arranged on a circle such that:
- The product of each pair of two non-adjacent numbers is divisible by 201520162015 \cdot 2016.
- The product of each pair of two adjacent numbers is not divisible by 201520162015 \cdot 2016.
Find the maximum value of nn.

Solutions — 2

Solution 1

See the solution in the test of level 4. \square

Solution 2

Denote vp(k)v_{p}(k) as the exponent of prime pp in the prime factorization of positive integer kk. It is easy to see that vp(ab)=vp(a)+vp(b)v_{p}(ab) = v_{p}(a) + v_{p}(b) for all positive integers a,ba, b.

We have 2015=513312015 = 5 \cdot 13 \cdot 31, 2016=253272016 = 2^{5} \cdot 3^{2} \cdot 7.
Denote M=20152016M = 2015 \cdot 2016 and
N={2,3,5,7,13,31} N = \{2, 3, 5, 7, 13, 31\}
Suppose there exist nn positive integers x1,x2,x3,,xnx_{1}, x_{2}, x_{3}, \ldots, x_{n} arranged on the circle satisfying the given condition and denote xn+1x1x_{n+1} \equiv x_{1} and xn+2x2x_{n+2} \equiv x_{2}.

Since xixi+1x_{i} x_{i+1} is not divisible by MM for i=1,,ni = 1, \ldots, n, then there exists a prime piNp_{i} \in N such that
vpi(xixi+1)<vpi(M)vpi(xi)+vpi(xi+1)<vpi(M)(*) v_{p_{i}}(x_{i} x_{i+1}) < v_{p_{i}}(M) \Leftrightarrow v_{p_{i}}(x_{i}) + v_{p_{i}}(x_{i+1}) < v_{p_{i}}(M) \tag{*}
These primes form a sequence p1,p2,,pnp_{1}, p_{2}, \ldots, p_{n} and the elements can be repeated. We will prove that pipjp_{i} \neq p_{j} with i,ji, j two non-adjacent indices.

Indeed, if there are some non-adjacent indices i,ji, j such that pi=pj=pp_{i} = p_{j} = p. Denote a=vp(M)a = v_{p}(M) and from (*), we have vp(xi)+vp(xi+1)<av_{p}(x_{i}) + v_{p}(x_{i+1}) < a and vp(xj)+vp(xj+1)<av_{p}(x_{j}) + v_{p}(x_{j+1}) < a.
Hence, we have
vp(xi)+vp(xi+1)+vp(xj)+vp(xj+1)<2a. v_{p}(x_{i}) + v_{p}(x_{i+1}) + v_{p}(x_{j}) + v_{p}(x_{j+1}) < 2a.
On the other hand, since (i,j),(i+1,j+1)(i, j), (i+1, j+1) are pairs of non-adjacent indices then
vp(xi)+vp(xj)a,vp(xi+1)+vp(xj+1)a. v_{p}(x_{i}) + v_{p}(x_{j}) \geq a, \quad v_{p}(x_{i+1}) + v_{p}(x_{j+1}) \geq a.
This implies that
vp(xi)+vp(xi+1)+vp(xj)+vp(xj+1)2a, v_{p}(x_{i}) + v_{p}(x_{i+1}) + v_{p}(x_{j}) + v_{p}(x_{j+1}) \geq 2a,
which is a contradiction.

Continue, suppose that there exists an index ii such that pi=pi+1=pp_{i} = p_{i+1} = p. If vp(M)=1v_{p}(M) = 1, because xixi+1x_{i} x_{i+1} and xi+1xi+2x_{i+1} x_{i+2} are not divisible by MM, we can conclude that xi,xi+1,xi+2x_{i}, x_{i+1}, x_{i+2} are not divisible by pp. Hence xixi+2x_{i} x_{i+2} is not divisible by MM, contradiction because xi,xi+2x_{i}, x_{i+2} are not adjacent.
So if pi=pi+1=pp_{i} = p_{i+1} = p, then we must have vp(M)2v_{p}(M) \geq 2.

Now we can conclude that the sequence p1,p2,,pnp_{1}, p_{2}, \ldots, p_{n} has the following properties:
- Each prime piNp_{i} \in N appears at most 2 times.
- If some prime piNp_{i} \in N appears 2 times, then pi2Mp_{i}^{2} \mid M.

Hence, we have
p1p2pnM. p_{1} p_{2} \ldots p_{n} \mid M.
Since M=2532571331M = 2^{5} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 13 \cdot 31, we can see that n8n \leq 8 (in the sequence (pi)(p_{i}), prime 22 appears 22 times, prime 33 appears 22 times and the rest appear 11 time). It is easy to check that if we choose 8 numbers as follows:
M25,M23,M32,M35,M57,M713,M1331,M312 \frac{M}{2^{5}}, \frac{M}{2 \cdot 3}, \frac{M}{3^{2}}, \frac{M}{3 \cdot 5}, \frac{M}{5 \cdot 7}, \frac{M}{7 \cdot 13}, \frac{M}{13 \cdot 31}, \frac{M}{31 \cdot 2}
and the corresponding sequence is
p1=2, p2=3, p3=3, p4=5, p5=7, p6=13, p7=31, p8=2. p_{1} = 2,\ p_{2} = 3,\ p_{3} = 3,\ p_{4} = 5,\ p_{5} = 7,\ p_{6} = 13,\ p_{7} = 31,\ p_{8} = 2.
Therefore, the maximum value of nn is 88. \square

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.