Apples Across a Bridge (word problem)

Question

Here is a fun problem that I am having trouble answering:

Let’s say I live in Town A, and I want to transport 249 apples across a bridge to Town B, but I can only carry 100 at a time. The bridge is 100 feet long, and I will lose one apple every foot I walk in the direction of Town B and it cannot be recovered. I will not lose apples if I walk in the direction of Town A. I am also permitted to set down apples at any point on the bridge and pick them up later. What is the minimum amount of apples I need to get 249 of them across the bridge?

Answer 1

Assume you have $a_k$ apples at some position $k\in\{0,\dots100\}$, say $a_k=365$. To push them forward you at least four chunks of at most hundred apples; more that four chunks will be too costly. So you move them forward for position at the cost of $4\times4$ apples.

Working back from position $100$, where we must have $a_{100}=249$ apples, we should have $a_{99}=252$ apples, $a_{96}=261$, $a_{93}=270$, that is, moving back $3$ position at the cost of $9$ each until we reach $a_k>300$, from where $4$ steps cost $16$ each and so and. If I'm not mistaken, $a_4= 650$, so $678$ apples are enough.

Answer 2

I'll give my mathematical model first, so it's easier to figure out if a disagreement comes from an incorrrect argument or a different understanding of the problem.

I consider this a discrete problem, the person will be able to move on the bridge only in integer multiple of $1$ft in either direction. Otherwise, the "I will lose one apple every foot I walk in the direction of Town B" condition becomes hard to interpret without more clarification (for example, if I move $1$ ft in $10$ steps of $0.1$ft each, putting down and taking up some apples on the way, when and how do I loose the $1$ apple).

Then it makes sense to mark the $100$ points of interest on the bridge where the person can stop by their distance in feet from the edge of the bridge towards town A. So point $0$ is the edge of the bridge towards town A, getting apples here incurs no losses. Point $1$ is $1$ft away from it a.s.o., and point $100$ is the edge of the bridge towards town B, where $249$ apples need to be brought to.

First, it is enough to get $252$ apples to point $99$. Then the person can take them in $3$ walks to point $100$, starting for example with $100$, $100$ and $52$ and arriving with $99$, $99$ and $51$, resp., going back empty handed each time for the next batch.

But it is also necessary for any solution to get at least $252$ different apples to point $99$. Because bringing $249$ apples to point $100$ requires at least $3$ trips (with apples) from point $99$ to point $100$, so the person will lose at least $3$ apples that reached point $99$ on those trips. If less then $252$ different apples make it to point $99$, less then $249$ different apples make it to point $100$.

This argument can again be applied to the point $98$: Bringing $255$ apples there is enough to solve the problem, and you need to bring at least $255$ different apples there, in order to solve the problem (aka bring $252$ different apples to point $99$).

This argument continues, increasing the number of apples that need to be brought to point $X-1$ vs. point $X$ by $3$, until you reach point $84=100-16$. The above argument shows that it is necessary and sufficient to bring $297=249+16\times3$ apples there. Since $297=3\times 99$, the above argument just barely works to show that it is necessary and sufficient to bring $300$ apples to point $83$, then make $3$ trips (starting with $100$ apples each time, arriving with $99$ each time) from point $83$ to $84$.

But now we need at least $4$ trips to reach point $83$ from point $82$ bringing $300$ apples there, so we lose at least $4$ apples on that $1$ft trip. So now the number of apples that it is necessary (and sufficient) to bring to point $82$ is increased by $4$ from what it was for point $83$, so that number is $304$.

Again this continues, and we see that we need $308$ apples at point $81$ a.s.o, until we reach point $59=83-24$, which requires $396=300+24\times4$ apples, which is just managable with $4$ trips from point $58$, which needs $400$ apples. From here on we need at least $5$ trips for each $1$ft step, so point $57$ requires $405$ apples,a.s.o.

The next 'step up' in the number of required trips for $1$ft happens between points $38$ and $37$. Point $38=58-20$ requires $500=400+20\times5$ apples, which needs 6 trips from point $37$.

The next 'step up' in the number of required trips for $1$ft happens between points $22$ and $21$. Point $22=38-16$ requires $596=500+16\times6$ apples, which needs 7 trips from point $21$ (since each trip can only arrive with at most $99$ apples, $6$ trips aren't enough, as $596 > 594 = 6\times99$).

The next 'step up' in the number of required trips for $1$ft happens between points $8$ and $7$. Point $8=22-14$ requires $694=596+14\times7$ apples, which needs 8 trips from point $7$.

This means we need to bring (and it is enough to bring) $758=694+8\times8$ apples to point $0$, which is the end if the bridge towards town A. As bringing apples to this point is lossless, that the answer:

The person transporting apples needs to start with at least $758$ apples in town A, and that many apples is enough.