binaire getallen
Opgave - BrMO 2 2004 vraag 2
Toon aan dat er een natuurlijk getal bestaat met de volgende eigenschappen:
(i) de binaire voorstelling van $n$ heeft precies 2004 0'en en 2004 1'en;
(ii) 2004 deelt $n$.
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 2 gasten online.
Oplossing
Het eerste wat opvalt als je de binaire getallen ziet, dat is dat als je zo'n getal met 2 vermenigvuldigt, je enkel een 0 aan het getal toevoegt. Dit is eenvoudig te bewijzen: $$2(2^{a_{1}}+2^{a_{2}}+...+2^{a_{n}})=(2^{a_{1}+1}+2^{a_{2}+1}+...+2^{a_{n}+1})$$ wat dus wil zeggen dat elke term 1 rang stijgt, waardoor er achteraan een 0 aan wordt toegevoegd.
$2004=2^2 \cdot 501$,
Binair:
$3\cdot2004$= 9 I'en en 4 O'en
$5\cdot2004$= 6 I'en en 8 O'en
Nu kunnen we van $3\cdot2004$ en $5\cdot2004$ een soort lineaire combinatie maken, zodat er 501 I'en zijn en minder dan 501 O'en. Dit doen we door $3\cdot2004$ 55 keer na elkaar te zetten en er dan $5\cdot2004$ achter te zetten. Dat volledig getal zet je dan 4 keer na elkaar en dan voeg je de nodige O'en toe door het met $2^n$ te vermenigvuldigen.