# Infinite Troll Tolls

So, recently there was a very good riddle posted here: Paying the Troll toll. I would like to propose a similar question which might have been partially answered. But anyways...

So, same basic idea as the original Paying the Troll toll riddle, however, assume now that there are an infinite number of bridges with an infinite number of trolls. How many pies must I leave with to ensure that I arrive at grandmas' with a whole number of pies? (Edit: assume that you do reach a point at which you arrive at grandmas. This would be when a sequence approaches zero as the number of bridges you go over tends to infinity.)

In addition, how would this answer change if the ratio of pies given to the trolls were to change. That is instead of half, what about an eighth, etc.?

• I have answered infinite situation in the original question. for the ratio part it is obvious that no ratio greater than 0.5 of the cakes to trolls will not make the way through infinite bridges. – Rafe Sep 29 '14 at 19:21
• If an answer helped you, remember you can click the green check next to it to mark it so. This will help future readers who have the same problem as you do, to get good answers quicker. – warspyking Oct 27 '15 at 21:39

First of all, you'd never reach grandmas.

Moving on from the obvious...

2 pies, get to a bridge, give 1, get it back, now you have 2, keep it going for infinite number of bridges, same solution, but different number of bridges.

There are n bridges, you have p pies, at each bridge, you have p/2+1 pies left.

There are inf bridges, you have 2 cakes, at each bridge, you have 2/2+1 (2) pies left.

If you were to give them different ratios it would be something like

p/r+1

In order to always reach grandmas that equation has to evaluate to p, or p/r + floor(p/r/3) must be less than the total amount of bridges. Since there are infinite bridges, that won't happen, and the only time p/r+1 = p is when p = 2 and r = 2.

p/r+1 = p
p/r = p-1
r(p/r) = r(p-1)
p = r(p)-r
p+r = p(r)

And the only pair of positive integers where when added together are equivalent to when multiplied together are 2, 2.

Simple Answer "How many pies must I leave with ...?" There is no unique answer, but most simply, leave home with no pies. Details below.

Original conditions

From the original question: "The trolls can't give you half a cake back. It is unhygienic and disgusting." Since the trolls can only adjust your number of pies by integer amounts, just start with any number of whole pies to reach grandma's with a whole number of pies. Since the trolls give you back 1 whole pie after taking some number of yours, you will have at least 1 pie to present at grandma's.

Fractional pies

If trolls can give potions of a pie back, and assuming they can subdivide pies into any real number, you can still start with any real number of pies and reach grandma's with a whole number of pies.

Suppose you start with $p$ pies. You leave bridge 1 with $\frac{p}{2^1} + \frac{2^1 - 1}{2^0}$ pies, bridge 2 with $\frac{p}{2^2} + \frac{2^2 - 1}{2^1}$ pies, and in general, bridge $n$ with $\frac{p}{2^n} + \frac{2^n - 1}{2^{n-1}}$ pies.

In the limit as $n$ tends to infinity, you end up with exactly 2 pies when you reach grandma's, regardless of how many pies you started with, whether positive, negative, fractional, or real. In the case of negative pies (you borrowed them), your pie debt transferred to the trolls, piecemeal ... your friends might not be happy to get those pies back under those conditions.

Conveniently, you can still start out with zero pies. If the tolls work the same manner going home, you'll even end up with two pies for yourself when you get home :) .

Different tolls

The final part of the question changes the toll so that crossing the bridge with $p$ pies, you leave the bridge with $\frac{p}{k}+1$ pies, for some $k$. (Note: previously, $k=2$.)

Solving the power series expansion and leaving home with $p$ pies, you leave bridge $n$ with $\frac{p}{k^n} + \frac{k^n - 1}{k^{n-1} (k-1)}$ pies.

In the limit as $n$ tends to infinity, you end up with $\frac{k}{k-1}$ pies at grandma's house. If $k \neq 2$, you don't get to grandma's house with a whole number of pies, regardless of how many pies you left home with. So you might as well leave home with no pies if $k \neq 2$.