Breadcrumbs

[plasmid]

Warning: This is a problem I have not yet found an optimal (or even very good) solution to. But it seems awfully non-trivial, and not in a genre that I've seen before, so I'm throwing it out there for the Den. ( @bonanova that means you should take a look.)

You have a pet mouse. It's an awfully cute mouse. Kind of like those mice on Pinky and the Brain. And you'd like to make it even cuter by teaching it some tricks. The only problem is that your mouse is, well... let's just say it has the brain of a mouse so it's kind of hard to teach it any tricks. But it is very good at eating food. In fact, it will always manage to find the closest morsel of food and go eat it, then find the closest from its new position and go eat that, etc. until it eats everything in sight. So, you'd like to "teach" your mouse to do some tricks given that behavior.

The first exercise is to place morsels of food at the corners of a square and place breadcrumbs so the mouse runs to diagonal corners as much as possible. In other words, suppose you have a square with points A, B, C, D in clockwise order with the mouse starting at point A and you'd like to make the mouse go to point C (diagonal from point A), then point B (one of the two remaining), then point D (diagonal from point B). There are already some breadcrumbs at points B, C, and D (since there need to be breadcrumbs there if you want the mouse to stop at those points) and your goal is to place breadcrumbs to make the mouse go from A to C to B to D while placing as few breadcrumbs as possible.

That first exercise might be a challenge for your kid brother, but for a BrainDen level challenge (the one I haven't convinced myself I've found an optimal solution for yet): Instead of a square, suppose you have a regular pentagon with points A, B, C, D, and E in clockwise order and want to get the mouse to go from A to C to E to B to D?

[plasmid]

CaptainEd has the best answer so far and asked to see my solution so I'll go ahead and PM it, but will leave this open in case anyone else drops in and wants to take a crack.

[bonanova]

@plasmid Interesting puzzle and thanks for the call out.

EDIT: Thought this was optimal, but now have read @CaptainEd's solution.

Tip of the cap, Nice going. FWIW, my best efforts follow ....

Breadcrumbs (red circles) are placed at the five vertices A B C D and E.

Object is for our mouse to take four straight paths: AC, CE, EB, and BD.

Because we have a greedy mouse that goes to the nearest snack, it will move from a vertex to an adjacent vertex whenever it has an uneaten crumb. That must be prevented. So we draw inter-vertex-radius circles -- a red circle centered on A, a green circle centered on C and a blue circle centered on E -- to help define advantageous areas to place our minimum (M) count of additional tasty crumbs to keep our mouse on its intended path.

It is quickly evident that M can't be less than 5. (First-pass solution.)

Spoiler

1. Path AC needs an added crumb inside the red circle to keep the mouse from going first to B or E. Similarly Path CE needs one inside the green circle to avoid going next to B or D; and Path EB needs one inside the blue circle to keep the mouse from going next to D. So M is at least 3.

2. But the points on Path AC inside the red circle are closer to B than to C. A second crumb is needed on AC that is outside the red circle. Similarly a second one is needed on CE that is outside the green circle. But Path EB does not need another crumb. So long as the first crumb is placed beyond the bisector of angle CAD. Once we're at crumb 5 the only remaining crumbs are at B (closest) and D. With these additions, M is now at least 5.

3. Once the mouse reaches B he goes unaided to the final breadcrumb at D and we're done. M is still at least 5.

 

 
This diagram shows these breadcrumbs, in sequence, as numbers, and we hope for the mouse to visit the points in this order: A 1 2 C 3 4 E 5 B D.

But that won't happen. No matter where we put crumb 1 on Path AC, crumb 5 will block either A->1 or 1->2. More crumbs are needed, but how many more? If we can only get to vertex C, crumbs 3-5 can get us home. Path AC is the problem to be solved. We need to insert a minimal number of additional crumbs on AC that will get us past the evil Crumb 5.

Second-pass solution.

Spoiler

This solution provides two additional crumbs, (a) and (b), and thus makes M=7 and total (including vertex crumbs) of twelve.

 

1. Recall that we placed crumb 5 on EB just beyond the bisector of angle CAD. (See 9 below.) This fixes the distance A5.
2. Place crumb (a) as far from A as possible, keeping Aa < A5.
3. Place crumb (b) as far from (a) as possible, keeping distance ab < a5.
4. Place crumb 1 as far from (b) as possible, keeping distance b1 < b5.
5. Place crumb 2 as far from 1 as possible, keeping distance 12 < 15 and distance 2C the least from crumb 2 after that.
   
   That gets us to C, and only crumbs 3, 4 and 5 remain uneaten.
    
6. Place crumb 3 as far from C as possible, keeping it within the green circle. Thus keeping distance C3 < C5.
7. Place crumb 4 as far from 3 as possible, keeping distance 34 < 35 and distance 4E < 45.
   
   That gets us to E, with only crumb 5 uneaten.
    
8. Since crumb 5 is within the blue circle, distance E5 < ED.
9. Since crumb 5 is beyond angle CAD's bisector, distance 5B < 5D.

That gets us to B, with a straight shot of BD to the last crumb, at D.

To summarize: Five additional crumbs are needed to navigate the four paths in isolation. (1 2) enable path AC; (3 4) enable Path CE; (5) enables path EB. Two more are needed to prevent complications with crumb 5. (a) prevents A->5 and (b) prevents (a)->5.

Twelve crumbs, in all, will get our mouse from A to C to E to B to D along 4 straight paths.

 

[bonanova]

@CaptainEd

Spoiler

Nice work getting AC to work with only 3 crumbs. It took me four. Nice solve.

@plasmid

Spoiler

Your post almost claims a 10-crumb solution!
If you found a 2 on AC, 2 more on CE along with 1 on EB solution, I will be totally in awe.

 

[plasmid]

10 hours ago, bonanova said:

@CaptainEd

  Hide contents

Nice work getting AC to work with only 3 crumbs. It took me four. Nice solve.

@plasmid

  Hide contents

Your post almost claims a 10-crumb solution!
If you found a 2 on AC, 2 more on CE along with 1 on EB solution, I will be totally in awe.

 

Sort of a hint... (But note the edit below the spoiler before you open the spoiler.)

Spoiler

How sure are you about the conclusion that the path from C to E requires two breadcrumbs, and the underlying rationale?

Edit: To clarify: the mouse doesn't need to travel along straight lines to each of the points. It can go along any curved, jagged, or whatever sort of two-dimensional path you want, which makes the problem more interesting. If that's enough clarification, then don't open the spoiler :3

Edited June 22, 2019 by plasmid
Clarification of the OP

[bonanova]

1 hour ago, plasmid said:

Edit: To clarify: the mouse doesn't need to travel along straight lines to each of the points. It can go along any curved, jagged, or whatever sort of two-dimensional path you want, which makes the problem more interesting. If that's enough clarification, then don't open the spoiler :3

I understand that the mouse goes to the nearest crumb, and that "nearest" means shortest euclidean (straight line) distance. So (haven't read the spoiler yet) I never conceived the mouse would get advantage by doing otherwise.

I'm assuming the mouse is playing strictly according to his own hunger advantage. Am I right about that?

Oh wait. you're saying that
 

Spoiler

 

that the crumbs don't have to be placed on diagonals.

* headslap *

Now I can imagine a solution that adds 2, 2 and 1.

 

Give me a day or two to work on that?

[plasmid]

16 minutes ago, bonanova said:

I understand that the mouse goes to the nearest crumb, and that "nearest" means shortest euclidean (straight line) distance. So (haven't read the spoiler yet) I never conceived the mouse would get advantage by doing otherwise.

I'm assuming the mouse is playing strictly according to his own hunger advantage. Am I right about that?

Oh wait. you're saying that
 

  Hide contents

 

that the crumbs don't have to be placed on diagonals.

* headslap *

Now I can imagine a solution that adds 2, 2 and 1.

 

Give me a day or two to work on that?

That's correct. The mouse can take whatever path you want it to take, even if it's not straight lines from A to C to E to B to E, as long as it reaches the specified destinations in the specified order.

And it took me more than a day or two, so I certainly wouldn't fault you if it takes more than that.

[bonanova]

This was a fun puzzle.

Spoiler

Thanks to @plasmid for hinting that OP does not constrain the mouse to travel the diagonals, where the best I can do is 12 crumbs.

A-1-2-3-4-C-5-6-E-7-B-D

If there were to be a 10-crumb, off-diagonal path, it seemed clear that the E-to-B traverse would be the simplest, if one could be found, needing only one helper crumb. The mouse would then eat the crumbs in this order.

A-1-2-C-3-4-E-5-B-D,

Mentally I could get E without difficulty. I anticipated that placing crumb 5 would be the challenge. And making a quick sketch didn't resolve the question. It would be close.

Photoshop to the rescue.

I constructed the partial paths A-1-2-C and C-3-4-E identically. I placed crumb 2 on the BC edge, just lightly closer to C than to B. Then I placed crumb 1 at the vertex of an equilateral triangle B-2-1-B, being careful to nudge crumb 1 lightly toward crumb 2 to insure that distance 12 would be shorter than 1B.

With crumb 1 placed, I drew a circle around A at that radius, to exclude all crumbs other than crumb 1. That was enough to insure the A-1-2-C path would be taken. Constructing path C-3-4-E identically produced no interference, since the previous crumbs had now been eaten, and C was in that sense a fresh start. That gets us to crumb E.

1. I constructed a circle around E at radius equal to the distance ED.
   Crumb 5 would have to be inside, to keep the mouse from going to D next (from E.)
    
2. I bisected the diagram with a line from C through the center.
   Crumb 5 would have to be north of that line to make it closer to B than to D.
    
3. Finally crumb 5 would have to be outside the exclusion circle centered on A.

As luck would have it, there was a tiny area that did those three things. I plopped crumb 5 into it, insuring that from E, the mouse would dine next at crumbs 5, B and D, in that order.

The figure is the proof that this placement of crumbs solves the problem. That is, the required inequalities are shown graphically. There is enough wiggle room for each of crumbs 1-5 to make up for any slight Photoshop errors. (i.e. I didn't calculate all the crumb coordinates.)

 

[plasmid]

26 minutes ago, bonanova said:

This was a fun puzzle.

  Reveal hidden contents

Thanks to @plasmid for hinting that OP does not constrain the mouse to travel the diagonals, where the best I can do is 12 crumbs.

A-1-2-3-4-C-5-6-E-7-B-D

If there were to be a 10-crumb, off-diagonal path, it seemed clear that the E-to-B traverse would be the simplest, needing only one helper crumb and them mouse would eat the crumbs in this order.

A-1-2-C-3-4-E-F-B-D,

Mentally I could get E without difficulty. I anticipated that placing crumb 5 would be the challenge. True enough, and quick sketch left things in doubt. Photoshop to the rescue.

I constructed the partial paths A-1-2-C and C-3-4-E identically. I placed crumb 2 on the BC edge, just lightly closer to C than to B. Then I placed crumb 1 at the vertex of an equilateral triangle B-2-1-B, being careful to nudge crumb 1 lightly toward crumb 2 to insure that distance 12 would be shorter than 1B.

With crumb 1 placed, I drew a circle around A at that radius, and excluded all crumbs other than crumb 1. That was enough to insure the A-1-2-C path would be taken. Constructing path C-3-4-E identically produced no interference, and that gets us to crumb E.

1. I constructed a circle around E at radius equal to the distance ED. Crumb 5 would have to be inside, to keep the mouse from going to D next (from E.)
2. I bisected to diagram with a line from C through the center. Crumb 5 would have to be north of that line to make it closer to B than to D.
3. Finally crumb 5 would have to be outside the exclusion circle centered on A.

As luck would have it, there was a tiny area that did those three things, and I plopped crumb 5 into it, insuring that from E, the mouse would dine next at crumbs 5, B and D, in that order.

The figure is the proof that these placements solve the problem. There is enough wiggle room for each of crumbs 1-5 to make up for any slight Photoshop errors. (i.e. I didn't calculate all the crumb coordinates.)

 

 

That's the best solution so far, and matches the number of breadcrumbs I had even though it seems substantially different. I strongly suspect that there aren't any better solutions with fewer breadcrumbs, although I don't know of a way of proving it, let alone finding a general solution for determining the fewest number of breadcrumbs it would take to "teach" a dumb but hungry mouse to travel any arbitrary path. And I sort of doubt that anyone has figured it out since this sort of puzzle isn't a common thing. But I'll go ahead and share my perspective on the problem and the solution I reached.

Spoiler

I’ll start with some mouse luring theory for general cases, and will make some definitions: Call the Goal points G(1), G(2), G(3), … G(N) where the mouse needs to go from G(1) to G(2) to G(3) etc. and end at G(N). If there’s a set of Breadcrumbs that lure the mouse from G(1) to G(2) then call them B(1,1), B(1,2), B(1,3), ... B(1,M(1)) in the order they get eaten and the set of Breadcrumbs that lure the mouse from G(2) to G(3) would be B(2,1), B(2,2), B(2,3), … B(2,M(2)), etc.

CaptainEd noticed the first important thing: if the mouse has already gotten to point G(A), then it must have eaten everything from G(1) to G(A-1) and from B(1,X) to B(A-1,X), so you only have to worry about the breadcrumbs from G(A) onward and B(A,1) onward. That means it’s probably a good idea to start at the end and work backward. Make sure that if the mouse reaches G(N-1) it will go to G(N), which is pretty much a given since there won’t be any other breadcrumbs left at that point and the mouse will go to G(N) because that’s the only bit of food left. Then make sure that if the mouse reaches G(N-2) it will go to G(N-1), which might require some breadcrumbs if G(N) is closer to G(N-2) than G(N-1) is, which is the case with the pentagon where D is closer to E than C is, but at least you know that all of the other breadcrumbs will have been eaten so you just need to worry about placing B(N-2,X) breadcrumbs to lure the mouse to G(N-1) without going to G(N) first. Then place some B(N-3,X) breadcrumbs to make sure that if the mouse reaches G(N-3) it will go to G(N-2) next and not eat any of the G(N), G(N-1), or B(N-2,X) breadcrumbs.

(Notice that I said it’s probably a good idea to do that – it makes it easier to approach the problem, but doesn’t guarantee you’ll find an optimal solution.)

Two other things are worth mentioning about mouse luring before we get started with the pentagon. First is something that bonanova made use of in a sort of inverse way than I did since he worked forward instead of backward: if the mouse is at a point, then you can find the closest bit of food to that point that hasn’t been eaten yet and call the distance between them R. The next breadcrumb you place to lure the mouse must be within a circle of radius R around the mouse’s current position if you want it to be lured by that breadcrumb. Second, it helps to have a Voronoi diagram to know where the mouse will go next if you place a breadcrumb. Briefly stated, if you take all of the morsels of food that are still in play and draw lines that are equidistant from pairs of points to tile the plane, the mouse will next go to whichever morsel of food is at the center of the tile that the breadcrumb is in.

Now for the actual pentagon, where I’ll define a length of 1 unit to be the length of each side of the pentagon. If the mouse reaches G(4) and everything else has been eaten except G(5), then the mouse will go to G(5) and we don’t need to worry about placing any B(4,X) breadcrumbs.

If the mouse reaches G(3) and the only other bits of food are at G(4) and G(5), then we just need to lure the mouse from G(3) to G(4) without having it get sidetracked to G(5). So we need a point B(3,1) that lies within a circle of radius 1 around G(3) and that will take the mouse closer to G(4) than G(5) – in this case the Voronoi diagram just has a border between the G(4) and G(5) territory which is a line going through G(2) and the center of the pentagon. Easy enough… I’ll just place breadcrumb B(3,1) at distance 1 from G(3) along a line parallel to the G(2)-G(5) line as shown in the figure. Technically I’ll need to nudge the breadcrumb a little bit closer to G(3) to make the distance from G(3) to B(3,1) slightly less than 1 so I can be sure the mouse will go to B(3,1) instead of G(5), but this will be an infinitesimally small nudge and I’ll talk more about exactly how this breadcrumb will be nudged later on.

Next we need to get the mouse from G(2) to G(3) while the food in play is G(3), G(4), G(5), and the B(3,1) that we know the approximate location of. I’ve drawn dashed lines for the Voronoi diagram that are halfway between G(3) and B(3,1), G(3) and G(5), and G(5) and B(3,1) so the territory for G(3) is the left and upper-left segment, the territory for B(3,1) is the right and upper-right segment, and the territory for G(5) is the two lower segments. (I won’t worry about G(4) since it’s pretty far away.) Notice that G(3), B(3,1), G(2), and G(5) form a parallelogram so all sides are length 1 and opposite angles are equal.

We know the angle from G(3) to G(5) to G(2) is 108º (for a regular N-gon it will be 180 – (360 / N)) so the other angles of the isosceles triangle formed by those points is (180 – 108) / 2 = 36º. Half the distance from G(2) to G(3) would be 1 x cos(36), so the full distance from G(2) to G(3) would be 2 x cos(36). If we place B(2,1) a distance of 1 away from G(2) along the line going from G(2) to G(3), then the remaining distance from B(2,1) to G(3) would be 2 x cos(36) – 1. So where does that fall in relation to the Voronoi border? The “x-axis” distance from G(3) to B(2,1) in the figure is (2 cos(36) – 1) x cos(36), which happens to be 0.5. So the breadcrumb would be exactly on the borderline in the Voronoi diagram! But remember that the exact position of B(3,1) isn’t carved in stone yet and it will need to be nudged anyway, so while we’re nudging it we can give it a nudge to move counterclockwise around the circle of radius 1 around G(3), which will rotate the vertical line in the Voronoi diagram counterclockwise to increase the territory for G(3) in the upper left segment and open an area to drop B(2,1).

Then the last and hardest part will be to get the mouse from G(1) to G(2) with all the food in play. First we figure out the radius of the circle around G(1) where we can drop a breadcrumb that will lure the mouse. The closest point to G(1) is B(3,1). If we ignore the nudging of B(3,1) and say it’s on the line from G(3) to G(4), the angle formed by G(1), G(3), and B(3,1) is 36º for the same reason the G(5), G(2), G(3) angle is 36º. A little bit of trig will tell you that the distance from G(1) to B(3,1) is 2 sin(18), so the first breadcrumb must be within that distance of G(1).

Let’s place B(1,1) along the line from G(1) to G(4) at a distance 2 sin(18) from G(1). Using the same bit of trig again, we see that the distance from B(1,1) to B(3,1) is (2 sin(18))squared. The distance from B(1,1) to G(4) is 1 – 2 sin(18). And it turns out that those two distances are equal, which makes the math easier going forward as we just take a vertical path straight down next.

We know that the angle from vertical going up to B(1,1) to G(4) is half of 108º (since B(1,1) is on the line from G(4) to G(1) and we know that’s true at G(1)) so that angle is 54º, and by symmetry the angle to B(3,1) is also 54º. If we go down from B(1,1) for a distance of 1 – 2 sin(18) and drop B(1,2) there, we have an isosceles triangle with two 63º angles (since (180 – 54) / 2 = 63).

We know the angle from G(4) to B(1,2) to G(2) is 180 – 63 = 117. We also know that the angle from G(4) to G(2) to the horizontal is 180 – 108 = 72º so the angle from B(1,2) to G(2) to G(4) is 90 – 72 = 18º. And the angle from B(1,2) to G(4) to G(2) is 180 – 117 – 18 = 45º. Since we know the length from G(4) to G(2) is 1, I can take the coward’s way out by going to an online calculator like calculator.net/triangle-calculator.html to solve for the distance from B(1,2) to G(2) as 0.794 and B(1,2) to G(4) as 0.347. So we can place one more breadcrumb B(1,3) at a distance of 0.346 going down from B(1,2) which will be distance 0.448 from G(2), which is clearly within G(2)’s area on the Voronoi diagram because the distance is less than 0.5 and the other points like B(2,1), B(3,1), and G(4) are all a distance of 1 from G(2), and we even have some room to spare so we can feel comfortable about going back and making those infinitesimal nudges we promised.

That’s a solution for the pentagon, and I think it’s not possible to solve it with fewer than five breadcrumbs, but I don’t see any good way of proving it for more general cases. You can say that for any distribution of a finite number of goals G(1), G(2), G(3), … G(N) you can always lay a set of breadcrumbs to solve it – just do as CaptainEd mentioned earlier and draw straight lines between each of the G(X-1) to G(X) (in reverse order, starting from X=N and working backward), find the nearest bit of food to that line that could cause the mouse to go astray, and drop breadcrumbs along the line so the distance between breadcrumbs is always less than that critical distance but be sure that you never drop a breadcrumb directly on top of a line connecting another pair of points G(Y-1) to G(Y) that the mouse will need to traverse. And if the line between G(X-1) and G(X) has a goal point directly on that line, just drop a breadcrumb somewhere else to serve as a waypoint W and make the mouse go from G(X-1) to W and then to G(X). So there’s always a solution for any situation, and since any solution must have a finite number of points there must be a smallest number of points that can be a solution, but I don’t have any idea how to prove you’ve found an optimal solution for complex cases.

 

[bonanova]

I think there's a proof for the pentagon case.

Spoiler

To answer your spoilered question in your Friday at 11:43 PM (edited) post.

You need two helper crumbs to get from A to C without encountering B.  (1) has to be closer to A than B is, and (2) has to be closer to C than to B. Ditto for getting from C to E without nibbling at D.

And I think it would be provable by drawing appropriate circles, showing there is no way to do either task with a single helper crumb.

Without at least one more helper, the mouse will go from E to D, bypassing the crumb at B. So, 5 helpers, minimum.

-----------

General case ... you can guide the mouse along any desired path, with crumbs placed arbitrarily closely, and possibly finagling things where the path crosses itself. So there exists a minimum (by removing crumbs until at some point things don't work.)

But saying an answer exists and finding it are two different things.

 

[plasmid]

7 minutes ago, bonanova said:

I think there's a proof for the pentagon case.

  Hide contents

To answer your spoilered question in your Friday at 11:43 PM (edited) post.

You need two helper crumbs to get from A to C without encountering B.  (1) has to be closer to A than B is, and (2) has to be closer to C than to B. Ditto for getting from C to E without nibbling at D.

And I think it would be provable by drawing appropriate circles, showing there is no way to do either task with a single helper crumb.

Without at least one more helper, the mouse will go from E to D, bypassing the crumb at B. So, 5 helpers, minimum.

-----------

General case ... you can guide the mouse along any desired path, with crumbs placed arbitrarily closely, and possibly finagling things where the path crosses itself. So there exists a minimum (by removing crumbs until at some point things don't work.)

But saying an answer exists and finding it are two different things.

 

I would have to disagree with that since I just posted a solution with only one breadcrumb going from C to E. But I do agree that there probably isn't a better solution for the pentagon case than adding five new breadcrumbs.

[bonanova]

What precludes the mouse from going from G(2) to G(5)? (My eyes are getting bleary ...)

[plasmid]

9 hours ago, bonanova said:

What precludes the mouse from going from G(2) to G(5)? (My eyes are getting bleary ...)

Spoiler

It's the nudging that I promised to do; B(2,1) has to be nudged so the distance from G(2) to B(2,1) is slightly less than 1. That's done by nudging B(3,1) slightly counterclockwise around G(3) to open up a tiny area where the Voronoi tile for G(3) extends a little closer to G(2) -- in the figure for the G(2) to G(3) movement, nudging B(3,1) counterclockwise would rotate the vertical Voronoi border slightly counterclockwise so the corner of the G(3) Voronoi tile (upper left and left segments of the dotted line regions) extends into the unit circle around G(2).

 

[plasmid]

On 6/23/2019 at 5:40 PM, bonanova said:

With discussion help from @plasmid, here is a 9-crumb solution. Kudos again for an engaging puzzle.
 

  Reveal hidden contents

 

Each helper is in a circle centered on the previous breadcrumb. The circle excludes subsequent breadcrumbs.

 

Path A 1 2 C

  Reveal hidden contents

 

Circle A includes Crumb 1 and excludes all others.
Circle 1 includes Crumb 2 and excludes all others.
Crumb 2 is to the right of bisector through E and the center, so from 2 mouse goes to C rather than to B.

 

Path C 3 E

  Reveal hidden contents

 

Circle C includes Crumb 3 and excludes B and D. (1 and 2 have been eaten.)
Crumb 3 lies to the left of the bisector through B and the center, so crumb E is next, not D.

The path from C to E using only one helper is due to @plasmid. I believed it took two helpers.

We can't also shorten the A 1 2 C path, cuz the single helper ends up too close to the center.
The single helpers would end up too close, and mouse would go { A 1 3 E } and spoil things.

So there's no 8-crumb solution.

Path E 4 B D

  Reveal hidden contents

 

Circle E includes Crumb 4 and excludes D. (Crumbs A 1 and 3 have been eaten.)
Crumb 4 lies above the bisector through C and the center, so mouse will go next to B rather than to D.
At B, only Crumb D remains.

 

 

 

It looks like that will indeed work. And I know I just said this about the previous solution, but now I really don't think there's a way to do it with any fewer breadcrumbs.

As for ever finding a general solution to the breadcrumbing problem, 

Spoiler

It looks like a key feature of this solution that lets it use fewer crumbs than the one I had is that the final breadcrumb is way out far away from the interior of the pentagon, leaving more free room in the center to play with in the earlier steps. The complete opposite of a greedy algorithm. Which makes me less optimistic about finding a general solution easily... but on the other hand probably makes this sort of problem more fertile ground for puzzling.