Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

I believe the third one is only a matter of computation, but I don't have time to do it now...

this one is a real deadly question . actually it is from a bulgarian maths olympiad. well the answers are a)510 b)312 c)462

(Sadly, I missed the binary expansion idea, so I'm only going to post a sketch of my solution.) Let $R_n$ denote the length of the resting period before the chameleon catches the $n$-th fly. Note that when $n$ is a power of $2$, then $R_n=1$. Using induction we can see that for every positive integer $k$, the largest value of $R_n$ for $2^k<=n<2^{k+1}$ is $k+1$, which happens when $n=2^{k+1}-1$. So the first $n$ such that $R_n=9$ is when $n=2^9-1=511$, and it follows that $510$ flies were caught by the chameleon before his first resting period of $9$ minutes in a row. For every positive integer $k$, the values of $R_{2^k}$, $R_{2^k+1}$, $\dots$, $R_{2^k+2^{k-1}-1}$ are $R_{2^{k-1}}$, $R_{2^{k-1}+1}$, $\dots$, $R_{2^k-1}$, respectively. We can see that this is true by induction. Then we can note that $$\sum_{i=2^k}^{2^{k+1}-1}R_i=2\sum_{i=2^{k-1}}^{2^k}R_i+2^{k-1},$$so if we let $A_k$ be the value of the LHS, we get $A_k=2A_{k-1}+2^{k-1}$. By induction again, since $A_1=3$ is our base case, we can see that $$A_k=2^k+k2^{k-1}=2^{k-1}(k+2).$$Thus we can easily find the values of $A_n$ for the first few $n$. We now have \begin{align*} \sum_{i=1}^{98} R_i&=\sum_{i=1}^{63}R_i+\sum_{i=64}^{95}R_i+(R_{96}+R_{97}+R_{98}) \\ &=(A_0+A_1+\dots+A_5)+A_5+8, \end{align*}which is $192+112+8=312$. So the chameleon catches the $98$-th fly after $312$ minutes. The rest of the problem is just computation.

Let the number of minutes in the $x$-th resting period be $f(x)$. It is trivial by induction to see that $f(x)$ is the popcount(number of $1$'s in the binary representation) of $x$. Denote popcount by $\text{pc}$. Part a. $f(x)=9$ when the popcount of $x$ is $9$, which first happens at $x=2^9-1=511$. So the answer is $\boxed{510}$. Part b. This is just $$\left(\sum_{i=1}^{98}\text{pc}(i)\right)=\left(\sum_{i=0}^{95}\text{pc}(i)\right)+2+3+3=3\cdot\left(\sum_{i=0}^{31}\text{pc}(i)\right)+32+32+2+3+3=3\cdot(5\cdot16)+32+32+2+3+3=\boxed{312}.$$ Part c. Let $g(x)=f(1)+f(2)+\dots+f(x)$. Note that $g(2^k-1)=\sum_{i=0}^{2^k-1}\text{pc}(i)=k\cdot 2^{k-1}$. So $g(511)=2304$. Also, note that $f(8a)+f(8a+1)+\dots+f(8a+7)=8f(a)+12$. So, we can make a table of popcounts right below $64$: \begin{tabular}{|c|c|c|c|c|c|c|} \hline $x$ & 63 & 62 & 61 & 60 & 59 & 58 \\ \hline $f(x)$ & 6 & 5 & 5 & 4 & 5 & 4 \\ \hline \end{tabular}So $f(58\cdot8)+f(58\cdot8+1)+\dots+f(511)=304$. So $g(58\cdot8-1)=2000$, and our answer is $58\cdot8-2=\boxed{462}$.

What's the point of this question The waiting time before eating the $i$th fly is $s_2(i)$ where $s_p(i)$ is the sum of the digits of $i$ in base $p$. Thus, the first time he waits $9$ minutes is just before the eating the $2^9-1$th fly, or after his $\boxed{510}$th fly. Clearly, the answer is $s_2(1)+s_2(2)+\dots + s_2(98)$. One appears on the units digit $49$ times, the $2$s digit $49$ times, the $4$s digit $48$ times, the $8$s digit $48$ times, the $16$s digit $48$ times, the $32$s digit $35$ times, the $64$s digit $35$ times. Thus, the answer is $\boxed{312}$ minutes. Note that the number of minutes passed after $2^k-1$ flies is exactly $k\cdot 2^{k-1}$. After the $511$st fly, $2304$ minutes passed. Then, bash the rest. After the $111001111_2$th fly but before the $511$st fly, a total of $304$ minutes were waited, thus at the $1999$th minute, $462$ flies were caught.

"no it's on the aime silly isl stole from aime then ! ...ridiculously computational)" - jatloe cj823957y19208500239758927o30472305023874 Anyways, we note that for every 2m from m, multiplying by 2 in binary does not change the # of 1s. For 2m+1, we add a 1, and we know that the last digit was 0, so we add 1 to the # of 1s in binary representation, etc. Now for 9 minutes we have 9 ones, or 2^8+...+1=511th catch, or 510 flies were caught (almost sillied this ) For part b, we have 1 fly in 1 minute, 2 flies in 1 minute, etc., or the sum of the #1s in the numbers in binary representation from 1 to 98. 1 appears at the end 49 times (49 odd #s), 2nd from the back digit 49 times (is 2 or 3 mod 4), 3rd from the back digit 48 times (8,9,10,11,12,13,14,15 mod 16), etc, summing them up until mod 128, we get 312. For part c, we know after the 511th fly 2304 minutes passed (we can bash by doing the same mod thing), so now just take reasonable guesses by subtracting. Off the top of my head, I would say we would expect each fly to take around 7 minutes so subtract (2304-1999)/7; 44 days, and we're already very reasonably close. We get the answer is 462.

I'd like to say that I didn't expect so much calculation from IMO Let $f(n)$ be the the resting period before catching the n-th fly. $f(1)=1$ $f(n>1)= \begin{cases} f(n/2) & \text{if }n\equiv0\pmod2\\ f(n-1)+1 & \text{otherwise.} \end{cases}$ Lemma: $f(n)$ equals the number of 1s in the base 2 representation of n Proof: I will use induction Base $n=1$ is true Assume we have proven the result for all $k<n$ Now I will prove it for n Case 1: $n\equiv0\pmod2$ $n$ and $n/2$ have the same amount of zeroes in base 2 and $f(n)=f(n/2)$. Done Case 2:n\equiv1\pmod2 $n$ has one more one than $n-1$ in base 2 and $f(n)=f(n-1)+1$. Done a. The answer is one less than the first number with 9 1s in base 2 Answer=$111111111_{(2)}-1_{(2)}=510$ b. The answer is $\sum_{i=1}^{98}f(i)$ Let $s(n)=\sum_{i=1}^{2^n}f(i)$ If we consider the number $k\in[1;2^{n-1}-1]$ it has one less one than $k+2^{n-1}$ and if we consider $k=2^{n-1}$ it has the same amount of ones as $k+2^{n-1}$ With this information we can say that $s(n)=2s(n-1)+2^{n-1}-1$ With induction we prove that $s(n)=n2^{n-1}+1$ for $n\geq0$ $\sum_{i=1}^{98}f(i)=s(6)+\sum_{i=65}^{98}f(i)=s(6)+34+\sum_{i=1}^{34}f(i)=s(6)+34+s(5)+\sum_{i=33}^{34}f(i)=s(6)+34+s(5)+2+\sum_{i=1}^{2}f(i)=s(6)+34+s(5)+2+s(1)=$ $=6\cdot2^{5}+1+34+5\cdot2^{4}+1+2+2=312$ $\implies$ Answer$=312$ c. The answer is the smallest n such that $\sum_{i=1}^{n}f(i)\geq1999$ Using $s(8)=1025$ and $s(9)=2305$ I estimate that $n\in[256;512]$ $\sum_{i=1}^{n}f(i)=s(8)+\sum_{i=257}^{n}f(i)=n+769+\sum_{i=1}^{n-256}f(i)$ Case 1: $n-256<128\implies n+769+\sum_{i=1}^{n-256}f(i)<384+769+s(7)=1602$ contradiction $\implies n\in[384,512]$ $769+n+\sum_{i=1}^{n-256}f(i)=n+769+s(7)+\sum_{i=129}^{n-256}f(i)=2n+834+\sum_{i=1}^{n-384}f(i)$ Case 1: $n-384<64\implies 2n+834+\sum_{i=1}^{n-384}f(i)<2\cdot448+834+s(6)=1923$ contradition $\implies n\in[448;512]$ Suppose $n=448$ then 1923 minutes would have passed Manually checking for $449,450,451,...462$ by adding $f(449),f(450),f(451),...f(462)$ to 1923 we get that $\sum_{i=1}^{461}f(i)=1994$ and $\sum_{i=1}^{462}f(i)=2000$ $\implies$ Answer$=462$ Note: If $2^{x-1}\leq n< 2^x$ then $\sum_{i=1}^{n}f(i)=s(x-1)+\sum_{i=2^{x-1}+1}^{n}f(i)=s(x-1)+n-2^{x-1}+\sum_{i=1}^{n-2^{x-1}}f(i)$

Define $f(n)$ to be the length of the resting period after the $n$th fly is caught. Evidently $f(n)$ counts the number of bits in the binary representation of $n$. Then the answer to part (a) is $510$. The answer to part (b) is $f(1)+\dots+f(98)$. Notice: \[f(1)+\dots+f(64)=32\cdot 6+1\]\[f(65)+\dots+f(96)=32+16\cdot 5+1\]\[f(97)+f(98)=2\cdot 2+1\cdot 1+1\]and adding yields $312$. For part (c), notice: \[f(1)+\dots+f(256)=128\cdot 8+1=1025\]\[f(257)+\dots+f(384)=128+64\cdot 7+1=577\]\[f(385)+\dots+f(448)=128+32\cdot 6+1=321\]\[f(449)+\dots+f(456)=24+4\cdot 3+1=37\]and now from $f(457)$ to $f(462)$ we have values $\{5,5,6,5,6,6\}$. As $f(463)=7$ brings the total to $2000$ minutes, it follows the answer is $462$. $\blacksquare$