- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,685

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

- Thread starter anemone
- Start date

- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,685

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

- Mar 10, 2012

- 834

Denote $S_n=\{i:2^{n-1}\leq i<2^n\}$.

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

Let $f:\mathbb N\to \mathbb N$ be the function $f(k)=a_k$.

Now its not very hard to see that $[\max f(S_n)]+1=\max f(S_{n+1})$.

This easily leads to the answer.

The maximum achieved by the sequence given is $10$.

Last edited:

- Moderator
- #3

- Feb 7, 2012

- 2,707

That neatly answers the first part of the problem. But the question also asks for the number of times that this maximum value occurs. The value 10 occurs for the first time as $a_{1023}$. But to find out how many more times it occurs in $\{a_{1024},\ldots,a_{1989}\}$ it will be necessary to look more closely at the structure of the sequence $\{a_k\}$.Denote $S_n=\{i:2^{n-1}\leq i<2^n\}$.

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

Let $f:\mathbb N\to \mathbb N$ be the function $f(k)=a_k$.

Now its not very hard to see that $[\max f(S_n)]+1=\max f(S_{n+1})$.

This easily leads to the answer.

The maximum achieved by the sequence given is $10$.

It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

- Mar 10, 2012

- 834

It can be shown by induction that $\max f(S_n)$ occurs at $i=2^{n}-1$ and that it occurs exactly once in $S_n$.That neatly answers the first part of the problem. But the question also asks for the number of times that this maximum value occurs. The value 10 occurs for the first time as $a_{1023}$. But to find out how many more times it occurs in $\{a_{1024},\ldots,a_{1989}\}$ it will be necessary to look more closely at the structure of the sequence $\{a_k\}$.

It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

This might settle second part of the problem. I will get back to this in a few hours. Have a test to write.

- Moderator
- #5

- Feb 7, 2012

- 2,707

In fact, it's obvious when you think about it. If $b_k$ is the number of 1s in the binary representation of $k$, then $b_{2k} = b_k$ (because the binary representation of $2k$ is the same as that of $k$ with an extra $0$ at the end), and $b_{2k+1} = b_{2k}+1$ (because the binary representation of $2k$ is the same as that of $2k$ with the final $0$ replaced by a $1$). Also, $b_1=1$. Therefore $b_k=a_k$.It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

So the first number with $a_k=10$ is $1023$ (whose binary representation consists of ten $1$s). In the range from $1024$ to $2047$, the numbers all have 11 binary digits, so the only ones with $a_k=10$ will be those with one binary digit $0$ and all the rest $1$s. Enumerating these, we get

$10111111111_2 = 1535_{10}$,

$11011111111_2 = 1791_{10}$,

$11101111111_2 = 1919_{10}$,

$11110111111_2 = 1983_{10}$,

$11111011111_2 = $ (greater than $1989$ in base 10, so we can stop there).

So there are five numbers $\leqslant 1989$ for which $a_k=10$.$11011111111_2 = 1791_{10}$,

$11101111111_2 = 1919_{10}$,

$11110111111_2 = 1983_{10}$,

$11111011111_2 = $ (greater than $1989$ in base 10, so we can stop there).