Megoldás. Jelölje $f\left(n\right)$ az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számok között fellépő kettőhatvány különbségek számát, $F\left(n\right)$ pedig legyen az $n$ különböző egész között fellépő kettőhatvány különbségek maximális száma. Ezzel a feladat állítása $F\left(n\right)=f\left(n\right)$ alakot ölt, amit $n$ szerinti teljes indukcióval bizonyítunk. Az $n=1$ eset triviális, hisz $F\left(1\right)=f\left(1\right)=0$.
Tegyük fel tehát, hogy $n<N$ esetén már igazoltuk az $F\left(n\right)=f\left(n\right)$ egyenlőséget. Célunk az $F\left(N\right)=f\left(N\right)$ bizonyítása. Legyenek tehát az $a_1<a_2<\text{...}<a_N$ egészek olyanok, hogy a belőlük képezhető kettőhatvány különbségek száma $F\left(N\right)$, és az ilyen tulajdonságú sorozatok közül olyat válasszunk, amire az $a_N-a_1$ különbség a lehető legkisebb.
Feltehető, hogy az $a_i$ számaink között van páros. Ha ugyanis minden $a_i$ páratlan, akkor az $\left\{a_i+1:1\le i\le N\right\}$ halmazból a képezhető kettőhatvány különbségek száma $F\left(N\right)$, és a legnagyobb és legkisebb szám különbsége sem változott. Ha netán minden $a_i$ páros, akkor az egész számokból álló $\left\{a_i/2:1\le i\le N\right\}$ halmazból is $F\left(N\right)$ kettőhatvány különbség képezhető, ráadásul a legnagyobb és legkisebb szám különbsége csökkent. Mivel az $a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_N$ sorozatot úgy választottuk, hogy ez a különbség minimális legyen, az $a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_N$ számok között bizonyosan van páros és páratlan is. Legyen tehát $k$ a páros és $N-k$ a páratlan $a_i$-k száma, ahol $1\le k<N$. Az is feltehető, hogy $k\le \frac{N}{2}$, ha ugyanis ez nem így volna, akkor minden $a_i$-t eggyel megnövelve olyan sorozatot kapnánk, amiben kevesebb a páros szám mint a páratlan, a kettőhatvány különbségek száma $F\left(N\right)$ és a legnagyobb és legkisebb szám különbsége sem változik ettől.
A sorozatunkban fellépő kettőhatvány különbségek háromfélék lehetnek. Két páros szám között fellépő kettőhatvány különbségből az indukciós feltevés szerint legfeljebb $f\left(k\right)$ lehet, ami megegyezik a $\mathrm{2,4,}\text{...}\mathrm{,2}k$ számok között fellépő kettőhatvány különbségek számával. Hasonlóan, a páratlan $a_i$-k szintén az indukciós feltevés szerint legfeljebb $f\left(N-k\right)$ kettőhatvány különbséget határoznak meg, és ez éppen az
$\mathrm{1,3,5,}\text{...}\mathrm{,2}\left(N-k\right)-1$ számok között fellépő kettőhatvány különbségek száma. Végül a páros és páratlan $a_i$-k között fellépő kettőhatvány különbségek páratlanok, így $1$-gyel egyenlők. Minden páros $a_i$ legfeljebb két ilyen különbségben szerepelhet, ezért legfeljebb $2k$ lehet ezekből, de az is igaz, hogy minden ilyen különbség $a_{i+1}-a_i$ alakú, amiből összesen $N-1$ van. Figyeljük meg, hogy a $\left\{\mathrm{2,4,}\text{...}\mathrm{,2}k\right\}$ és $\left\{\mathrm{1,3,5,}\text{...}\mathrm{,2}\left(N-k\right)-1\right\}$ halmazokból egy-egy elemet kiválasztva pontosan $2k$-féleképpen választhatunk szomszédos számokat, kivéve, ha $k=\frac{N}{2}$, amikor csak $N-1$ ilyen választás lehetséges.
Azt kaptuk, hogy az általunk vizsgált $\left\{a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_N\right\}$ halmazban legfeljebb annyi kettőhatvány különbség lép fel, mint a $H=\left\{\mathrm{1,2,3,}\text{...}\mathrm{,2}k\mathrm{,2}k+\mathrm{1,2}k+\mathrm{3,}2k+5\mathrm{,}\text{...}\mathrm{,2}\left(N-k\right)-1\right\}$ halmazban. Ezért az indukciós lépés befejezéséhez azt kell megmutatnunk, hogy a $H$ halmaz legfeljebb annyi kettőhatvány különbséget határoz meg, mint az $\left[N\right]:=\left\{\mathrm{1,2,}\text{...}\mathrm{,}N\right\}$ halmaz. Ha $k=\frac{N}{2}$, akkor $H=\left[N\right]$, és nincs mit bizonyítanunk. A továbbiakban feltesszük tehát, hogy $k<\frac{N}{2}$.
Vegyük észre, hogy $\left[2k+1\right]:=\left\{\mathrm{1,2,}\text{...}\mathrm{,2}k+1\right\}$ részhalmaza $H$-nak és $\left[N\right]$-nek is, ezért a $\left[2k+1\right]$ halmazon belül fellépő kettőhatvány különbségek nem okoznak eltérést.
A $H\setminus \left[2k+1\right]=\left\{2k+\mathrm{3,2}k+\mathrm{5,}\text{...}\mathrm{,2}\left(N-k\right)-1\right\}$, illetve $\left[N\right]\setminus \left[2k+1\right]=\left\{2k+\mathrm{2,2}k+\mathrm{3,}\text{...}\mathrm{,}N\right\}$ halmazok egyaránt $f\left(N-2k-1\right)$ kettőhatvány különbséget határoznak meg. Annyit kell tehát bizonyítanunk, hogy a $\left[2k+1\right]$ halmaz és a $H\setminus \left[2k+1\right]$ halmaz elemei között fellépő kettőhatvány különbségek száma nem lehet több, mint a $\left[2k+1\right]$ halmaz és az $\left[N\right]\setminus \left[2k+1\right]$ halmaz elemei között fellépő kettőhatvány különbségek száma. Ha azonban az $x\in \left[2k+1\right]$ és az $y\in H\setminus \left[2k+1\right]$ számok különbsége kettőhatvány, akkor mivel e különbség legalább $2$ és $y$ páratlan, ezért $x$-nek is annak kell lennie. Így a $\left(2k+1\right)$-ből ,,felére kicsinyített''