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?

[bonanova]

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

Spoiler

 

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

 

Path A 1 2 C

Spoiler

 

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

Spoiler

 

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

Spoiler

 

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.

 

 

 

[CaptainEd]

Square, simpler:

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

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

[plasmid]

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.

[Oumaima]

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 :/

[rocdocmac]

It's a regular pentagon, Oumaima!

Edited May 7, 2019 by rocdocmac

[plasmid]

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.

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.

 

 

[CaptainEd]

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

[plasmid]

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.

[CaptainEd]

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

[plasmid]

Good start, that would work, but the square can be done with fewer breadcrumbs.

[jjs323]

3 at c, 2 at b,1at d

[rocdocmac]

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 May 13, 2019 by rocdocmac

[Dave]

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.

[CaptainEd]

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.

[plasmid]

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.

[plasmid]

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

[CaptainEd]

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

[rocdocmac]

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

 

 

[plasmid]

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

 

 

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.

[rocdocmac]

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

 

 

Edited May 16, 2019 by rocdocmac
typo

[CaptainEd]

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

Spoiler

• Drag files here to attach, or choose files... 
  Max total size 9.06MB
  
• Insert other media 

Uploaded Images

•  
•  

 

[plasmid]

7 hours ago, CaptainEd said:

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

  Reveal hidden contents

• Drag files here to attach, or choose files... 
  Max total size 9.06MB
  
• Insert other media 

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.

[CaptainEd]

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

[CaptainEd]

OK, plasmid, I've squeezed them around a bit, and I'm down to 5 extra crumbs.

Spoiler

 

[CaptainEd]

oops error! My point #3 is too close to #1. Back in a bit...