Maths Olympiad Prep

Library / Team Selection Tests for BMO /4 of 7

Team Selection Tests for BMO, 2018

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Saudi Arabia

Find the smallest positive integer nn which can not be expressed as n=2a−2b2c−2dn=\frac{2^{a}-2^{b}}{2^{c}-2^{d}} for some positive integers a,b,c,da, b, c, d.

Solution

Let SS be the set of positive integers which can be written as s=2a−2b2c−2ds=\frac{2^{a}-2^{b}}{2^{c}-2^{d}} for some positive integers a,b,c,da, b, c, d.
Since s>0s>0, we can assume that a>b,c>da>b, c>d and write s=2b−d2a−b−12c−d−1s=2^{b-d} \frac{2^{a-b}-1}{2^{c-d}-1}. It's now clear that b−d=v2(x)b-d=v_{2}(x).
So if we set x=2v2(x)yx=2^{v_{2}(x)} y then y=2u−12v−1y=\frac{2^{u}-1}{2^{v}-1} (u,vu, v are positive integers). In particular, the number we are looking for is odd. Clearly the numbers of the form 2u−12^{u}-1 (v=0v=0) belong to SS. More generally, we know that 2v−1∣2u−12^{v}-1 \mid 2^{u}-1 if and only if v∣uv \mid u. Set u=dvu=d v then
y=2u−12v−1=2dv−12v−1=2(d−1)v+2(d−2)v+⋯+2v+1 y=\frac{2^{u}-1}{2^{v}-1}=\frac{2^{d v}-1}{2^{v}-1}=2^{(d-1) v}+2^{(d-2) v}+\cdots+2^{v}+1
This means that the base 2 representation of yy is of the form
y=10…0⏟v−110…0⏟v−11…0…0⏟v−11 y=1 \underbrace{0 \ldots 0}_{v-1} 1 \underbrace{0 \ldots 0}_{v-1} 1 \ldots \underbrace{0 \ldots 0}_{v-1} 1
(dd digits 1, every two consecutive 1's are separated by v−1v-1 0's). So the number we are looking for is the smallest odd number not of this form (for some d≥1,v≥1d \geq 1, v \geq 1). Note that
1=1‾, 3=11‾, 5=101‾, 7=111‾, 9=1001‾, 11=1011‾ 1=\overline{1},\ 3=\overline{11},\ 5=\overline{101},\ 7=\overline{111},\ 9=\overline{1001},\ 11=\overline{1011}
We can conclude that 11 is the smallest odd number whose base 2 representation is not of the desired form. So the answer is n=11n=11.

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.