Maths Olympiad Prep

Library / /43 of 60

Algebra Difficulty 7.7 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Find all positive integers k<202k<202 for which there exists a positive integer nn such that
{n202}+{2n202}++{kn202}=k2 \left\{\frac{n}{202}\right\}+\left\{\frac{2 n}{202}\right\}+\cdots+\left\{\frac{k n}{202}\right\}=\frac{k}{2}
where {x}\{x\} denote the fractional part of xx.
Note: {x}\{x\} denotes the real number kk with 0k<10 \leq k<1 such that xkx-k is an integer.

Solution

Denote the equation in the problem statement as (*), and note that it is equivalent to the condition that the average of the remainders when dividing n,2n,,knn, 2 n, \ldots, k n by 202202 is 101101. Since {in202}\left\{\frac{i n}{202}\right\} is invariant in each residue class modulo 202202 for each 1ik1 \leq i \leq k, it suffices to consider 0n<2020 \leq n<202.

If n=0n=0, so is {in202}\left\{\frac{i n}{202}\right\}, meaning that ()(*) does not hold for any kk. If n=101n=101, then it can be checked that ()(*) is satisfied if and only if k=1k=1. From now on, we will assume that 101n101 \nmid n.

For each 1ik1 \leq i \leq k, let ai=in202=in202{in202}a_{i}=\left\lfloor\frac{i n}{202}\right\rfloor=\frac{i n}{202}-\left\{\frac{i n}{202}\right\}. Rewriting ()(*) and multiplying the equation by 202202, we find that
n(1+2++k)202(a1+a2++ak)=101k n(1+2+\ldots+k)-202\left(a_{1}+a_{2}+\ldots+a_{k}\right)=101 k
Equivalently, letting z=a1+a2++akz=a_{1}+a_{2}+\ldots+a_{k},
nk(k+1)404z=202k n k(k+1)-404 z=202 k
Since nn is not divisible by 101101, which is prime, it follows that 101k(k+1)101 \mid k(k+1). In particular, 101k101 \mid k or 101k+1101 \mid k+1. This means that k{100,101,201}k \in\{100,101,201\}. We claim that all these values of kk work.

- If k=201k=201, we may choose n=1n=1. The remainders when dividing n,2n,,knn, 2 n, \ldots, k n by 202202 are 1,2,,2011,2, \ldots, 201, which have an average of 101101.

- If k=100k=100, we may choose n=2n=2. The remainders when dividing n,2n,,knn, 2 n, \ldots, k n by 202202 are 2,4,,2002,4, \ldots, 200, which have an average of 101101.

- If k=101k=101, we may choose n=51n=51. To see this, note that the first four remainders are 51,102,153,251,102,153,2, which have an average of 7777. The next four remainders (53,104,155,453,104,155,4) are shifted upwards from the first four remainders by 22 each, and so on, until the 2525th set of the remainders (99,150,201,5099,150,201,50) which have an average of 125125. Hence, the first 100100 remainders have an average of 77+1252=101\frac{77+125}{2}=101. The 101101st remainder is also 101101, meaning that the average of all 101101 remainders is 101101.

In conclusion, all values k{1,100,101,201}k \in\{1,100,101,201\} satisfy the initial condition.

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.