Maths Olympiad Prep

Library / /43 of 120

Number theory Difficulty 5.3 AIME, harder Prove it Croatia

Let mm, nn and kk be positive integers and let p1,p2,,pnp_1, p_2, \dots, p_n be the integers 1,2,,n1, 2, \dots, n given in some order. If
k(m+pii), k \mid (m + p_i - i),
holds for all i{1,2,,n}i \in \{1, 2, \dots, n\}, prove that one of the numbers mm and nn is divisible by kk.

Solution

Let us assume that kk does not divide nn and that n=kq+rn = kq + r, 0<r<k0 < r < k.
Since only the remainder of division of mm by kk is relevant, without loss of generality we may assume 0<mk0 < m \le k. We will prove that m=km = k.
If we assume that mrm \le r, then the numbers pm,pm+k,,pm+kwp_m, p_{m+k}, \dots, p_{m+kw} would be equal to the numbers k,2k,,qkk, 2k, \dots, qk in some order. This is impossible since the first sequence has q+1q+1 elements, and the second sequence has qq elements.
Hence m>rm > r and m+1+qk>nm + 1 + qk > n. There are q+1q+1 numbers 1,k+1,,qk+11, k+1, \dots, qk+1 which are equal to numbers pm+1k,pm+1,pm+1+k,,pm+1+(q1)kp_{m+1-k}, p_{m+1}, p_{m+1+k}, \dots, p_{m+1+(q-1)k}. This implies m+1k1m+1-k \ge 1, i.e. mkm \ge k. Since we assumed that mkm \le k it follows that m=km = k.

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.