2
$\begingroup$

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?

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

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.

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

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.

$\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.