Jump to content
BrainDen.com - Brain Teasers
  • 2
Sign in to follow this  
plasmid

Breadcrumbs

Question

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?

Share this post


Link to post
Share on other sites

Recommended Posts

  • 0

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.

plasmid_crumbs.jpg

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.)

 

Share this post


Link to post
Share on other sites
  • 1
8 hours ago, CaptainEd said:

Square, simpler:

 

  Hide contents

 

(0,0),  (2/3, 2/3), (1,1), 

(1,1/4), (1,0), (0,1)

 

 

Right on, that solves the square problem with the minimum number of breadcrumbs.

Share this post


Link to post
Share on other sites
  • 0

The Pentagon one is easy, cause you just have to fill the condition AC<CE<EB<BD, the square one though, is an impossible one :/

Share this post


Link to post
Share on other sites
  • 0

In case this helps clarity: the warm up problem is to take this setup with the mouse at A (I told you it was cute!) and breadcrumbs at B, C, D, and your job is to place more breadcrumbs to ensure the mouse goes first to C, then B, then D. Ideally, using as few breadcrumbs as possible.

image.png.c1ce68bc91cc88818f746af38fba2138.png

The real problem is to take this setup with breadcrumbs at points B, C, D, E and place more breadcrumbs to make the mouse go first to C, then E, then B, then D. Again, using as few breadcrumbs as possible.

image.png.eb74b8f6f74acb02aa52292354f295b1.png

 

 

Share this post


Link to post
Share on other sites
  • 0
1 hour ago, CaptainEd said:

Silly question: are we required to make the paths as straight lines: AC, CB, BD?

That's definitely not a silly question. In the question I had in mind, the paths don't need to be straight lines. But down the line when we solve the pentagon case and start thinking about generalizations, we could talk about solving for cases with straight line paths.

Share this post


Link to post
Share on other sites
  • 0

For the square

coordinates:

(0,0), (1/3, 1/3), (2/3, 2/3), (1,1), 

(1,1/4), (1,0), (0,1)

So, 3 crumbs in addition to the original ones

Share this post


Link to post
Share on other sites
  • 0
Spoiler

For the square case ... 2 at C, 1 at B and 1 at D

For the pentagon case, it looks like 4 at C, 3 at E, 2 at B and 1 at D, but that's probably not what is wanted!

 

Edited by rocdocmac

Share this post


Link to post
Share on other sites
  • 0

In your 4 sided box, insert 4 small triangles against the 4 box sides, which now create 2 paths, a to c, and b to d.

Repeat the mouse feeding exercise several times and the mouse will learn how to get to the 4 box corners using the your desired

directions. Then remove the 4 triangles and watch what happens.

Or, you could eat the bread yourself and feed the mouse to the neighbors cat.

Share this post


Link to post
Share on other sites
  • 0

Definitely an interesting puzzle with a new principle; nice job, Plasmid!


Partial analysis:


Let a0 be a breadcrumb on point A, a1 the first breadcrumb on the path to C, etc.
Then come c0=C, c1..., e0=E, e1..., b0= B, b1..., d0 = D

Working back from the last move:
There must be a crumb on D to attract the mouse to the endpoint.
Before that, a crumb on B, and then the mouse will see nothing but D, so no further bi are needed.
Before that, a crumb on E. After that, e1 has to be closer to E than D is, else the mouse at E will go directly to D without going to B first. There may need to be additional ei
Before that, a crumb on C, and afterward c1 must be closer to C than B is.
Before that, a crumb on A, afterward a1 has to be closer to A than E is.

Here are the endpoints and all the line segments from each endpoint to the next:
A, Aa1 < AE, a1a2,...,axC,
C, Cc1 <  CB, c1c2,...,cyE,
E, Ee1 < ED , e1e2,...,ezB,
B,
D

But I don’t yet see how to express the constraints on ai:i in 2...x, ci:i in 2..y, and ei:i in 2...z,  nor the values of x, y, and z.

Multiple crumbs on a spot


I doubt that putting more than one crumb on a spot has any effect.  There’s no instruction in OP suggesting that the mouse is swayed by mass, only distance. If more than one crumb is at a spot, and the mouse goes there, it will eat one crumb, then the next and the next, until they’re all gone, and then will move to the nearest crumb.

Share this post


Link to post
Share on other sites
  • 0
On 5/9/2019 at 5:30 AM, jjs323 said:

3 at c, 2 at b,1at d

... wut?

16 hours ago, rocdocmac said:
  Hide contents

For the square case ... 2 at C, 1 at B and 1 at D

For the pentagon case, it looks like 4 at C, 3 at E, 2 at B and 1 at D, but that's probably not what is wanted!

 

... Wat?

The mouse always goes and eats the nearest bit of food to its current position. So like Captain Ed says, putting multiple pieces of food at one spot wouldn't be helpful. If the mouse starts at point A of the square, then the food at either B or D will be closer than C (even if there are multiple breadcrumbs at C), so the mouse will go to the closer food at either B or D.

14 hours ago, Dave said:

In your 4 sided box, insert 4 small triangles against the 4 box sides, which now create 2 paths, a to c, and b to d.

Repeat the mouse feeding exercise several times and the mouse will learn how to get to the 4 box corners using the your desired

directions. Then remove the 4 triangles and watch what happens.

Or, you could eat the bread yourself and feed the mouse to the neighbors cat.

Nah, this mouse really is pretty dumb. It won't manage to learn, it'll still keep right on pursuing whatever bit of food is closest until it eats everything in sight.

Share this post


Link to post
Share on other sites
  • 0
3 hours ago, CaptainEd said:

Definitely an interesting puzzle with a new principle; nice job, Plasmid!


Partial analysis:

  Reveal hidden contents


Let a0 be a breadcrumb on point A, a1 the first breadcrumb on the path to C, etc.
Then come c0=C, c1..., e0=E, e1..., b0= B, b1..., d0 = D

Working back from the last move:
There must be a crumb on D to attract the mouse to the endpoint.
Before that, a crumb on B, and then the mouse will see nothing but D, so no further bi are needed.
Before that, a crumb on E. After that, e1 has to be closer to E than D is, else the mouse at E will go directly to D without going to B first. There may need to be additional ei
Before that, a crumb on C, and afterward c1 must be closer to C than B is.
Before that, a crumb on A, afterward a1 has to be closer to A than E is.

Here are the endpoints and all the line segments from each endpoint to the next:
A, Aa1 < AE, a1a2,...,axC,
C, Cc1 <  CB, c1c2,...,cyE,
E, Ee1 < ED , e1e2,...,ezB,
B,
D

But I don’t yet see how to express the constraints on ai:i in 2...x, ci:i in 2..y, and ei:i in 2...z,  nor the values of x, y, and z.

 

Multiple crumbs on a spot

  Reveal hidden contents

I doubt that putting more than one crumb on a spot has any effect.  There’s no instruction in OP suggesting that the mouse is swayed by mass, only distance. If more than one crumb is at a spot, and the mouse goes there, it will eat one crumb, then the next and the next, until they’re all gone, and then will move to the nearest crumb.

 

 

Yep, this gets harder than it looks ^_^

Share this post


Link to post
Share on other sites
  • 0

I believe I’ve got an answer, but the precise locations will come later when I can get to Excel on something easier than my phone.

Mouse starts at A. Breadcrumbs at B, C , D, E, plus 6 more

3 on segment AC, 2 on CE, 1 on EB. Details To Be Announced

Share this post


Link to post
Share on other sites
  • 0

Just to get my own mind at peace (square case) ...

Spoiler

One extra crumb in one of the orange regions (E or F) between center O and X or between O and Y, but not at X, Y or O,

since BC=CD=CX=AY and BO=CO=DO (equidistances).

Mouse moves from A to E (or F) to C, then to B (or D), and finally to D (or B).

 

blob.png.d1e422dc9fa813b7152b1f781383579f.png

 

Share this post


Link to post
Share on other sites
  • 0
4 hours ago, rocdocmac said:

Just to get my own mind at peace (square case) ...

  Reveal hidden contents

One extra crumb in one of the orange regions (E or F) between center O and X or between O and Y, but not at X, Y or O,

since BC=CD=CX=AY and BO=CO=DO (equidistances).

Mouse moves from A to E (or F) to C, then to B (or D), and finally to D (or B).

 

blob.png.d1e422dc9fa813b7152b1f781383579f.png

 

I see what you're saying -- if we don't care whether the mouse goes from C to B or from C to D then that would work and you could let the mouse just flip a coin after it reaches C. The OP was phrased sort of ambiguously since I first talked about making the mouse take as many diagonals as possible (in which case that would be fine to do) and later said the specific letter sequence of ACBD (in which case that wouldn't).

The only thing I'd say, though, is that if you drop a breadcrumb in region E, it seems like the mouse would go eat the breadcrumb there and then go to either B or D instead of C -- either of those two points would be closer to region E than C is.

Share this post


Link to post
Share on other sites
  • 0
On 5/15/2019 at 4:24 PM, plasmid said:

The only thing I'd say, though, is that if you drop a breadcrumb in region E, it seems like the mouse would go eat the breadcrumb there and then go to either B or D instead of C -- either of those two points would be closer to region E than C is.

So I see!

Spoiler

So, mouse moves from A → F → C → B/D → D/B

blob.png.2da017ce8847276305a2a800abe94c8d.png

 

 

Edited by rocdocmac
typo

Share this post


Link to post
Share on other sites
  • 0
7 hours ago, CaptainEd said:

Locations, as promised, for pentagon, in the columns labelled x and y.

  Reveal hidden contents

Uploaded Images

  •  
  •  

 

Putting coordinates into a spreadsheet and calculating distances sure is a good way of checking your work; now I wish I had thought of doing that!

I believe I have a way of doing it with five breadcrumbs aside from the five vertices. Up to you if you'd like to look at it a little longer or if I should go ahead and convert my chicken scratch to an intelligible post when I get a chance.

Share this post


Link to post
Share on other sites
  • 0

I’ll try a little longer, it’s a useful tool for testing out alternatives. I’m impressed with your 5 extras!

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...