# Apples Across a Bridge (word problem)

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?

• The apple is lost if it falls. That’s a great question - I’ll edit my post to make it more clear. Thank you! – Jaken Nov 16 '19 at 7:42
• I'll work with $500$ apples, but it should work with less. – Michael Hoppe Nov 16 '19 at 10:41
• @MichaelHoppe I think you need much more than 500 apples. Can you give a solution that works with 500 apples? – Ingix Nov 16 '19 at 14:23
• You're right: I was wrong. – Michael Hoppe Nov 16 '19 at 14:44
• But $1000$ is more than enough. – Michael Hoppe Nov 16 '19 at 14:52

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.

• We seems to have similar ideas, but I get a different number at the end. – Ingix Nov 16 '19 at 16:34
• You' re right, did a stupid mistake, the principle is similar. – Michael Hoppe Nov 16 '19 at 16:58

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.