3
$\begingroup$

Here is more complicated Paying the Troll toll like puzzle:

Between you and your destination, you have 7 bridges, and there is a troll under every bridge. Each troll, quite rightly, insists that you pay a troll toll. Before you can cross the $K$-th bridge, you have to give $K+1$ cakes plus they are not kind trolls and each takes additionally exactly $1/(K+1)$ of the rest. Also trolls would not accept part of a cake - just a whole one. And you can't rid of cakes between bridges. This is a sad puzzle, because you can never reach your destination, but how many bridges can you cross if you try hard? How many cakes do you need to take with you?

Explanation:
1. If you have $X$ cakes you pay first troll: $Y = 2+(X-2)/2$, second troll: $3+(X-Y-3)/3$, etc.
2. That means that $Y = 2+(X-2)/2$ and $3+(X-Y-3)/3$ must be integer numbers. So if you start with 1001 cake you fail at the very first bridge.

$\endgroup$
  • 1
    $\begingroup$ Am I missing something again? I get that if you have 224 cakes you get past with 1 cake remaining. Why can't I reach the destination? $\endgroup$ – kaine Jun 30 '14 at 14:40
  • $\begingroup$ @kaine, please reread explanation 1 and I added explanation 2. $\endgroup$ – klm123 Jun 30 '14 at 15:22
  • $\begingroup$ I think you can't get past the fifth bridge. Take $80$ cakes to get past the fourth. $\endgroup$ – Gabriel Romon Jun 30 '14 at 16:08
  • $\begingroup$ Where does it say that you can't eat/sell/discard cakes between bridges to reach a number that will allow you to cross the fifth bridge? $\endgroup$ – cjm Jun 30 '14 at 20:07
  • 2
    $\begingroup$ If we keep feeding the trolls, what will they come up with next? $\endgroup$ – kasperd Jul 1 '14 at 10:00
11
$\begingroup$

Say you start with $x$ cakes. After the first bridge, you're left with

$\frac{x-2}{2}$ cakes,

$\frac{x-8}{3}$cakes,

$\frac{x-20}{4}$ cakes

$\frac{x-40}5$ cakes

$\frac{x-70}6$ cakes

$\frac{x-112}7$ cakes

We want those to be integers.

Thus $x-8 \equiv 0 \pmod 3$ ie $x\equiv 2 \pmod 3$

and $x\equiv 70 \equiv 4 \pmod 6$

But $x\equiv 2 \pmod 3$ and $x\equiv 4 \pmod 6$ is a contradiction.

Therefore, you cannot get past the fifth bridge. To reach it, you can start with $80$ cakes

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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