# Number theory

You have bought n chocolates from a shop. Now the shopkeeper offers that if you return the wrappers, then for every 3 wrappers, he will give you 1 more chocolate. And you can continue this exchange offer until you run out of wrappers. Find how many choclates you can eat.

• Shubhodip ·

suppose u have 5 chocolates

how many can u eat

first u have to eat three

so two left

get one more from the 3 wrappers

so three now

eat them

get one more

drink water

so u ate 7

is that what u mean ?

i think yes

• Debosmit Majumder ·

but if u have have even no. of chocolates then??
lets say u`ve bought 4....then u can hv only 5 chocolates

• Shubhodip ·

thats not any big problem

eat 3, get 1, eat two, total 5

I m almost sure that this is a nothing problem

he posted it in mathlinks too in olympiad section,where the moved it to 13+, :D

• Hari Shankar ·

i received this one on sms quite some time ago :D. Apparently a variant of this figured on the CAT paper that year. cant vouch for authenticity though!

• Subham Soni ·

Let p(x) denote the number of chocolates one can have when you start with x chocolates.

if x<3, p(x)=x
if x<9, p(x)=x+[x/3]
if x<27, p(x) = x+[x/3]+[x/9]
and so on....

That should be the basic principle, but since the wrapper from the previous time can also be added to the current wrapper, we cannot actually use this formula.

Another way would be to analyze all the possible values of x and p(x) and see if it leads somewhere

x p(x) p(x)-p(x-1)
1 1 1 -
2 2 2 1
3 4 3+1 2
4 5 4+1 1
5 7 5+1+1 2
6 8 6+2 1
7 10 7+2+1 2
8 11 8+2+1 1
9 13 9+3+1 2
10 14 10+3+1 1

As you can see, the values make almost no sense at all because there is too much of recursion and complication.

(Actually, there is a pattern emerging, but I am not very sure of it. Wait. Now that I paid a little attention to it, the pattern makes absolute sense. It should have been there.)

So p(x)-p(x-1)=2 if x is odd, and 1 if x is even.
In other words, p(x)=p(x-2)+3, where 1 and 2 are the first two values for p(x).

Generalising it, we will get
p(x) = 1+3(x-1)/2 if n is odd
= 2+3(x-2)/2 if n is even

which again boils down to
3x/2 - 1/2 (n is odd)
3x/2 - 1 (n is even)

I guess the two can be generalised even further into a single box function kind of solution, but I dont seem to be getting it at the instant.

______________________________________________________________________

Also, another approach to the problem could have been-

Every time u (The current number of unused wrappers you have at the instant) > 3, we decrease u by 2 and add 1 to c (The number of chocolates we have in total)

This approach again will lead to the very same result as before in the following way

If you have x+2 chocoaltes at the instant, you state will be the same as that of x (only that you will have 2+1 chocolates extra [2 since originally it was 2 more, and one because of the wrapper you got])

Which, in other words means that p(x+2)=p(x)+3 [which we have already got earlier]

==================================================

Interestingly, this problem can also be generalised even further -

You get m chocolates for returning n wrappers.(Obviously n>m or the answer will be infinity) What will be the number of chocolates you finally get when you buy x chocolates originally.

This will finally come to -
p(x+n-m)=p(x)+(n-m+m)
or p(x+n-m)=p(x)+n

And then finally get the main formula from the above and so on.......

• 