# How many lemons? [duplicate]

A king announced to his subjects that "Whoever brings me two lemons from the magic garden, will be crowned as king."

One clever young man dared to go in search of the lemons. He came near the first door of the garden. The guard told the young man that "When you return you should give me half of the lemons you have with you. Half of the quantity means strict half, that is, if you bring 10, I should have 5 and you should have 5. If we have unequal amounts I will kill you. If you satisfy these conditions as a token of appreciation I will give you one lemon back."

He has to pass all 100 doors with guards with these same conditions.

On returning back he satisfied all the conditions of guards and gave the king the two lemons and became the king.

How many lemons did he pick?

He picked

2 lemons. So at every guard he gives away 1 lemon, but gets back 1 lemon. No matter how many guards he passes, he will still have 2 lemons in the end.

• I go with this as the intended correct answer. However, this answer assumes that(as I feel)... initially the young man has picked up 2 lemons but afterwards before he meets all remaining 99 guards, he picks up one lemon each per door. Pls. check. – Mea Culpa Nay Oct 21 '17 at 8:13
• @Mea Culpa Nay. If he picked up two lemons initially, and met a guard, he would have 1 lemon after giving the guard half his lemons. THEN the guard, since the YM followed instructions to the letter, gives the YM "one lemon back." So the YM has two lemons...IF he picks up ANOTHER lemon, he will have three, which he cannot halve, so the next guard will kill him. (THEN, strictly speaking, the guard should hand one lemon back to the corpse, but that does not seem to help the YM very much.) A.P.. 'S answer is sound. 2 initial lemons, and the YM can get thru every door and still have 2 lemons. – user41655 Oct 21 '17 at 10:03
• Why can't he slice the lemons when sharing them with the guards? (I know that makes the answer "at least 2", which isn't as interesting as "exactly 2", but how does it violate the terms of the question?) – Lawrence Oct 21 '17 at 13:18
• @Rob, thanks for your explanation. It is my bad that I did not read the question till the end. – Mea Culpa Nay Oct 21 '17 at 16:30

Strictly speaking,

he could have picked $k \cdot 2^{100} + 2$ lemons, for arbitrary values of $k \in \mathbb{N}_{0}$.

He will have $k+2$ lemons left over and can give two of them to the king:
The first guard takes half of the $k \cdot 2^{100}$ lemons and one lemon for the $2$ additional lemons, then gives him back the one lemon again, leaving him with $k \cdot 2^{99} + 2$ lemons. This allows him to continue the same process with the next, for the total of a hundred, guards and leaves $k + 2$ lemons to bring to the king (or to become a lemon-selling magnate, depending on the value of $k$).

Admittedly, the alternative amounts could never realistically be picked by him.

• Your second solution wouldn't quite work, due to the single lemon each guard gives back to the man. If he picked 2^101 lemons, for example, he would get killed by the second guard on his return. – Timoris Oct 21 '17 at 14:09
• @Timoris Forgot to the add the + 2 there, thanks for the catch. It'll work for 2^101 + 2, etc. – Cyan Oct 21 '17 at 14:12
• Actually, on these terms surely he can start with any number that's 2 mod 2^100. The first guard turns 2^100.m+2 into 2^99.m+1 and then into 2^99.m+2, and similarly for the other guards. – Gareth McCaughan Oct 21 '17 at 16:17
• @Cyan, in your answer you could have explained what k is or what it denotes. – Mea Culpa Nay Oct 21 '17 at 16:35
• @Mea Culpa Nay k is a parameter, it can take the value of any natural number (including zero) - the solution works regardless of which value is actually used – Cyan Oct 21 '17 at 16:55

Let $n$ be the number of apples he originally picked up.
We can try and find out the number of apples he'll have after the $k^{\text{th}}$ door.
$n - \frac{n}{2} + 1$
$\frac{n}{2} + 1 - \frac{n}{4} - \frac{1}{2}$
$\frac{n}{4} + \frac{1}{2} + 1$
$\frac{n}{8} + \frac{1}{4} + \frac{1}{2}$
$\cdots$
$\frac{n}{2^k} + \frac{n}{2^{k-1}} + \cdots \frac{1}{2}$
In general:
$$n{\cdot}2^{-k} + \frac{1(1 - 2^{k-1})}{1 - \frac{1}{2}}$$ For $100$ doors:
$$n{\cdot}2^{-100} + \frac{1(1 - 2^{99})}{1 - \frac{1}{2}}$$ $$\frac{n}{2^{100}} + 1(1 - \frac{1}{2^{99}}$$ $$\frac{n - 2}{2^{100}} + 2 = 2$$ $$\frac{n - 2}{2^{100}} = 2 - 2$$ $$\frac{n - 2}{2^{100}} = 0$$ Multiply through by $2^{100}$:
$$n - 2 = 0$$ $$n = 2$$

I don't know how to use spoilers, so feel free to edit them in.

• He can hold as many apples as he wants, but the guards and king are interested in lemons. ;D – Alpha Oct 26 '17 at 4:51