grootste element van rij

Opgave - IrMO 1989 dag 1 vraag 3

De rij $a_1,a_2,a_3,\ldots$ wordt gedefinieerd door $a_1=1,a_{2n}=a_n,a_{2n+1}=a_{2n}+1$. Vind het grootste element uit $a_1,\ldots,a_{1989}$ en het aantal keer dat het voorkomt.

Oplossing

Na eventjes observeren zien we dat $a_n$ gelijk is aan het aantal eentjes in de binaire voorstelling van $n$. Van de getallen $a_1$ tot en met $a_{1023}$ is $a_{1023} = 10$ duidelijk het grootste. Het getal $11$ komt pas voor vanaf $a_{2047}$. Het enige wat we dus moeten nagaan is hoeveel keren het getal $10$ nog voorkomt tussen $a_{1023}$ en $a_{1989}$. Wat spelen met binaire getallen toont ons dat dit nog $4$ keer is. In totaal komt $10$ dus $5$ keer voor.