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$
6
  • 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
    Commented Jun 30, 2014 at 14:40
  • $\begingroup$ @kaine, please reread explanation 1 and I added explanation 2. $\endgroup$
    – klm123
    Commented Jun 30, 2014 at 15:22
  • $\begingroup$ I think you can't get past the fifth bridge. Take $80$ cakes to get past the fourth. $\endgroup$ Commented Jun 30, 2014 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
    Commented Jun 30, 2014 at 20:07
  • 3
    $\begingroup$ If we keep feeding the trolls, what will they come up with next? $\endgroup$
    – kasperd
    Commented Jul 1, 2014 at 10:00

1 Answer 1

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 and acknowledge you have read our privacy policy.

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