Answer to Question #92419 in Combinatorics | Number Theory for Yash Choudhary

Question

some friends bought some chocolates and hide them in a box and went to sleep. one of the friends wake up and ate one chocolate before taking half the number of chocolates ,now the second friend wake up did the same and went to sleep this process continued until the last person did the same and went to sleep when they woke up in the morning only one chocolate was left, if it is known that there are less than hundred chocolates then how many friends are there to the maximumwas left if it is known that there are less than hundred chocolates then how many friends are there (to the maximum)

Answer 1

Answer:

The max. no. of friends such that no. of chocolates does not exceed 100 is 5 (without the person who finds the last chocolate and can't take half anymore). The no. of chocolates is 63.

Solution I:

Let x be the no. of chocolates.

1st friend: ate 1, takes (x-1)/2 => (x-1)/2 chocolates left

2nd friend: ate 1, takes [(x-1)/2 -1] /2 = (x-3)/4 => (x-1)/2 -1 - (x-3)/4 = (x-3)/2 - (x-3)/4 = (x-3)/4 chocolates left

And so forth.

In general, kth friend ate 1, takes {{[x-(2^k-1-1)]/2^k-1} - 1} /2 and also {{[x-(2^k-1-1)]/2^k-1} - 1} /2 chocolates left

We can prove this using induction.

Base case - 1 friend & 2nd friend already verified above.

Now we assume that holds for (k-1)th friend and we must prove for kth friend.

After (k-1)th friend there are left A= [x-(2^k-1-1)]/2^k-1 chocolates (induction hypothesis), where A is just a notation

Now, the kth friend ate 1, takes (A-1)/2 and there are left A-1 - (A-1)/2 = (A-1)/2 = {[x-(2^k-1-1)]/2^k-1 - 1}/2 =

={[x -(2^k-1-1) -2^k-1] /2^k-1} /2 =[x-(2^k-1)] /2^k which proves the induction claim

Now let's assume that after the kth friend, a single chocolate remains.

According to induction, 1 = [x-(2^k-1)] /2^k => x-(2^k-1) =2^k => x =2^k+2^k -1 =2^k+1 -1

But x<100 => 2^k+1 -1 < 100 => 2^k+1 < 101 < 128 =2⁷ => k+1 < 7 => k<6 => k is 5 at max.

Therefore, there are 5 friends (excepting the person who finds the last chocolate) such that x remains under 100, namely x= 2⁵⁺¹ -1 =64-1=63

If we also count that person, we obtain 6

Solution II

We write the number of chocolates,x, starting from the end (when we know that 1 chocolate has remained).

Before remaining one chocolate, there were 2*1 =2 (since the penultimate person takes half).

Before the penultimate person to take 1, there are left 2+1=3

Now, 3 is the half of what is left after the person before the penultimate ate 1 => 3*2 +1 =7 before that

And so forth.

7*2+1 =15

15*2+1=31

31*2+1=63

63*2+1=127 false, since 127 >100

Thus we stop at 63 chocolates and count the persons for obtaining 5 (without the person who finds the last chocolate).

If we also count that person, we obtain 6 friends at maximum.