11[13][13][13][13][13]
A biologist watches a chameleon. The chameleon catches flies and rests after
each catch. The biologist notices that:
(i) The first fly is caught after a resting period of 1 minute.
(ii) The resting period before the 2mth fly is caught is the same as the resting
period before catching the mth fly and 1 minute shorter than the resting period
before the (2m+1)st fly.
(iii) When the chameleon stops resting, he catches a fly instantly.
(a) How many flies were caught by the chameleon before his first resting period
of 9 consecutive minutes?
(b) After how many minutes will the chameleon catch his 98th fly?
(c) How many flies have been caught by the chameleon after 1999 minutes have
passed?
-
UP 0 DOWN 0 4 16
16 Answers
11Ans :
a) 510 flies
b) 309 mins.
c) will give the ans after 1999 mins [9][9]
39THIS IS A QUESTION I HAD DONE BEFORE. IF MY MEMORY IS NOT WRONG , ITS ONE OF
IMOSL QUESTIONS.
39believe me, anyone able to answer 3 perfectly would be a hell of a genious !
1Let f(x) denote time before catching x^{th} fly.
Then essentially we need to solve:
f(x):\mathbb{N}\to\mathbb{N} \\ i) f(1)=1. \\ ii) f(2m)=f(m) \\ iii)f(2m)+1=f(2m+1).
Write out some initial terms and the pattern comes into view:
1 2 3 2 3 3 4 2 3 3 4 3 4 4 5 ...
As the function involves 2m, 2m+1, Instinct tells something has to do with binary...
And what we get!!!
f[(b_mb_{m-1}b_{m-2}\cdots b_0)_2]=b_m+b_{m-1}+b_{m-2}+\cdots b_0
Now to prove that by induction is piece of cake.
Check that by multiplying a no. by 2 increases a zero in its binary expression. So f(2m)=f(m).
And by adding a 1 to that last zero in binary expression of f(2m), we get f(2m+1)=f(m)+1.
Now come to the problem.(rather,i say deceptive statement ;-)
when f(n)=9 for first time, m must be 9 and all bi must be 1.
So for f(n)=9 for 1st time, n=(111111111)2=511.
So the fly cathes 510 flies before that.
we need to calculate \sum_{i=1}^{98}f(i).
For that we need to know what is g(n)=\sum_{i=1}^{n}f(i).
The recurrence for g is g(1)=1 \\ g(2n)=g(n)+g(n-1)+n \\ g(2n+1)=2g(n) +n+1
So we have
g(5)=7
g(6)=9
g(11)=20
g(12)=22
g(23)=52
g(24)=54
g(48)=52+54+24=130
g(49)=2.54+24+1=133
g(98)=130+133+49=312
Now part 3.
We have
g(2^n)=n*2^{n-1}+1
[easy to prove by induction,since g(2^{n}+1)=2g(2^{n-1})+n-1+1=2(n-1)2^{n-2}+n+2 \\ and \\ f(2^{n}+1)=2]
So
g(256)=1025 giving g(255)=1024 since f(2n)=1. Similarly
g(512)=2305
so our sought number is inbetween.
The numbers from 256 to 383 (= 256 + 127) are the same as those from 0 to 127 with an additional initial 1. Hence g(383) = g(255) + 128 + g(127) = 1600.
The numbers from 384 = 256 + 128 to 447 = 256 + 128 + 63 are the same as those from 0 to 63 with an additional two initial 1s. Hence g(447) = g(383) + 128 + g(63) = 1920.
The numbers from 448 = 256 + 128 + 64 to 463 = 256 + 128 + 64 + 15 are the same as those from 0 to 15 with an additional three initial 1s. Hence g(463) = g(447) + 48 + g(15) = 2000.
Hence sought number is 462.
39yup ith power. this is the solution. its a problem proposed bby UK for imo. and is from IMO shortlist.
1i must suspect that it never got to imo for the boring (not so mathematical) calculation.
39yes i th power. imo involves thinking and not writing. thats the reason they might have ignored this :P