Maths Olympiad Prep

Library / /3 of 5

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it India

Let N3N \ge 3 be an integer, and a0,,aN1a_0, \dots, a_{N-1} be pairwise distinct reals so that aia2ia_i \ge a_{2i} for all ii (indices are taken mod NN). Find all possible NN for which this is possible.

Solution

The only such NN are powers of 22.

If NN is not a power of 22, let's say pNp \nmid N where pp is an odd prime. Now, observe that p1p \nmid 1 but p2k1p \mid 2^k - 1 for some k>1k > 1. Then, let α=Np\alpha = \frac{N}{p}. Now,
aα>a2αa4αa2kα    aα>a2kα a_{\alpha} > a_{2\alpha} \ge a_{4\alpha} \dots \ge a_{2^k \alpha} \implies a_{\alpha} > a_{2^k \alpha}
But now, a2kα=aαa_{2^k \alpha} = a_{\alpha} as N(2k1)αN|(2^k - 1)\alpha but then this is a contradiction! We have that aα>a2αa_{\alpha} > a_{2\alpha} since all reals in the circle are distinct and NαN \nmid \alpha.

Now, if N=2mN = 2^m is a power of 22, let aj=ν2(j)+j2Na_j = -\nu_2(j) + \frac{j}{2N}. This is clearly okay if j=Nj = N and if jNj \ne N then ν2(2j)=ν2(j)+1\nu_2(2j) = \nu_2(j) + 1 and thus aja2ja_j \ge a_{2j}. \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 reproduced verbatim; metadata (topic, difficulty) added by this project.