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?


3 Answers 3


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.

  • $\begingroup$ 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. $\endgroup$ Commented Oct 21, 2017 at 8:13
  • 2
    $\begingroup$ @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. $\endgroup$
    – user41655
    Commented Oct 21, 2017 at 10:03
  • $\begingroup$ 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?) $\endgroup$
    – Lawrence
    Commented Oct 21, 2017 at 13:18
  • 1
    $\begingroup$ @Rob, thanks for your explanation. It is my bad that I did not read the question till the end. $\endgroup$ Commented Oct 21, 2017 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.

  • $\begingroup$ 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. $\endgroup$
    – Timoris
    Commented Oct 21, 2017 at 14:09
  • $\begingroup$ @Timoris Forgot to the add the + 2 there, thanks for the catch. It'll work for 2^101 + 2, etc. $\endgroup$
    – Cyan
    Commented Oct 21, 2017 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – Gareth McCaughan
    Commented Oct 21, 2017 at 16:17
  • $\begingroup$ @Cyan, in your answer you could have explained what k is or what it denotes. $\endgroup$ Commented Oct 21, 2017 at 16:35
  • $\begingroup$ @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 $\endgroup$
    – Cyan
    Commented Oct 21, 2017 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.

  • 3
    $\begingroup$ He can hold as many apples as he wants, but the guards and king are interested in lemons. ;D $\endgroup$
    – Alpha
    Commented Oct 26, 2017 at 4:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.