Maths Olympiad Prep

Library / EGMO TST /3 of 4

EGMO TST

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

Let N≥3N \ge 3 be an integer, and a0,…,aN−1a_0, \dots, a_{N-1} be pairwise distinct reals so that ai≥a2ia_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 p∤Np \nmid N where pp is an odd prime. Now, observe that p∤1p \nmid 1 but p∣2k−1p \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∣(2k−1)α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 j≠Nj \ne N then ν2(2j)=ν2(j)+1\nu_2(2j) = \nu_2(j) + 1 and thus aj≥a2ja_j \ge a_{2j}. □\square

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.