Jump to content
BrainDen.com - Brain Teasers


  • Content Count

  • Joined

  • Last visited

  • Days Won


Posts posted by plasmid

  1. The first thing that jumps out at me is that when I do Einstein puzzles by hand I usually need to do many iterations of going through the rules and filling out as much as I can, and then going through the rules again to narrow things down further based on what I’ve eliminated so far. In this case there’s a single loop of

    For cr = 1 to cntRules

    that gets executed once, as if a human were to just go through all the rules once instead of iteratively. If you as a human are able to solve the puzzle by going over each of the rules once in the order that they're presented, then the program should work. Otherwise maybe it would help if you wrap the for/next loop of cr in a loop similar to the one you currently have with bDoAgain checking for any changes since the last iteration before letting the program end.

    If you can go through this particular Einstein puzzle by hand and complete it in a single iteration (so the above isn't applicable), then could it be an issue with how the rules are encoded? I'm afraid I can't get the app working, but I’m used to seeing things like “The plumber lives in a house to the left of the guy who goes birdwatching on Thursdays” which aren’t so easily encodable with a plus/minus system.

  2. We'll have to see the algorithm and what it's doing in order to say much. Could you share it and walk through how it would handle an example Einstein puzzle that folks without the game could follow (say the one at https://web.stanford.edu/~laurik/fsmbook/examples/Einstein'sPuzzle.html)? If you solve the puzzle the old fashioned way and keep track of what you eliminate and why, is your algorithm able to recreate the path to the solution? If not, then what parts is it missing?

  3. On 11/1/2020 at 2:16 PM, EventHorizon said:
      Reveal hidden contents

    In both xp2008's and my solutions, you don't scan over the same range twice, once for each parity.  You increase the range by the scale factor every time you switch the parity.


    Ah, I see. So in that spirit you could present your solution #2 this way (not particularly efficient, but crystal clear that it works)


    Suppose the groundhog started at hole #0. Check hole #0 on the first day, and if he’s there then you’re done.

    Suppose the groundhog started at hole -1 or hole 1. By the second day (after you’ve checked hole 0) he’ll be at hole -2, 0, or 2. Have the two of you check holes ±2 on the second day, and if you don’t find him and he started at hole ±1 then he must have gone to hole 0 for the second day and will be at hole ±1 on the third day. Check holes ±1 on the third day and you’ll find him.

    Suppose the groundhog started at hole -2 or hole 2 on the first day. By the fourth day (after you’ve taken care of the cases where he starts at -1, 0, or 1) he’ll be at an odd numbered hole from -5 to 5. Search holes ±5 on the fourth day and if he’s not found then he was in an odd numbered hole from -3 to 3 and will be in an even numbered hole from -4 to 4 on the next day. Check holes ±4 on the fifth day, then holes ±3 on the sixth day, etc. until you’ve taken care of all the cases where he started at hole -2 or 2.

    Suppose the groundhog started at hole -3 or hole 3, or in general hole -N or N where you’ve already taken care of all of the smaller numbers. If you’ve taken D days to search, then he must be in hole -(N+D) to (N+D), so search holes ±(N+D) and work your way inward.

    After taking care of that case, move on to the next higher N. No matter where he initially started, you’ll eventually find him.


  4. I'm afraid I might be missing something, because it seems like whenever you switch parity you end up losing all the ground you previously covered.

    Consider xp2008's solution...


    If you assume the initial parity is odd and you search (-5,-3),(-2,0),(1,3),(4,6), then where could the groundhog be on day 4 if he's not caught? If he started from hole -7 then he could have reached hole -4 by day 4, and he could be at hole +8 on day 4, or anywhere outside that range.

    If you then switch to cover the even parity case and search for four days, in the odd parity case the groundhog could have moved from hole -4 on day 4 to hole 0 on day 8, and could have moved from hole +8 on day 4 to hole +4 on day 8. So after you've searched both parities, now all you know for the odd parity case is that the groundhog is not in the range from hole 1 to hole 3. So when you resume your odd parity search on the next day, the groundhog could be in any odd hole. Have you really made any progress?

    Similarly for EventHorizon's first solution


    Take the case of having bounds of 0 and N (where N is odd) for an initial scan. If you assume initial even parity, then you could scan (0,2), (N,3), (0,4), (N,5), ... (0,N-1) and it would take you N-1 days. You could then re-scan the area covering the initial odd parity case, but after scanning for another N-1 days the groundhog could get anywhere within the even parity case again by the time you start the next scan.

    You could argue that if you start off covering a finite area, then cover a slightly larger area, then cover a slightly larger area, etc. then you will eventually catch the groundhog because the groundhog must be at some finitely numbered hole which you will eventually reach. My counterargument to that is:


    xp2008's strategy would cover holes -5 through 6 for the odd parity case and finish after 4 days. If you then cover the even parity cases, you could cover holes -6 through 5 for the even parity case and finish both the odd and even parity cases after 8 days.

    Similarly, it would cover holes -23 to 24 for the odd parity case over the next 16 days, so if you start doing that on day 9 (after finishing the odd and even parity cases for -6 to 6) then you would finish on day 24. Then you would cover the even parity cases for that range over the next 16 days and finish on day 40.

    If I'm a groundhog and I don't want to be caught, I start on hole +2 and move to the next higher hole every day. You'll never catch me.


  5. Only if they're imaginary stonenibblers.


    CaptainEd was on the right track. Using his notation, if one stonenibbler's probability of nibbling is p and the other's is q (so the probability of the first not nibbling is 1-p and the second not nibbling is 1-q), then the observed frequency of both, one, or neither nibbling at a time implies

    A) 0.17 = pq
    B) 0.38 = p(1-q) + q(1-p) = p + q - 2pq
    C) 0.45 = (1-p) (1-q) = 1 - p - q + pq

    Since pq = 0.17 based on equation A, plug that value into equation B and you have

    0.38 = p + q - 0.34

    So p+q must be 0.72. Since p+q = 0.72, you know q = 0.72-p. So substitute that for q in equation A and you have

    0.17 = p(0.72-p), which can be rearranged to
    p2 - 0.72p + 0.17 = 0

    And that's a quadratic formula that can be solved as (-b ± sqrt[b2-4ac]) / 2a. But the stuff in the square root is 0.5184 – 0.68, which is a negative number, so you can’t take its square root (at least not with real numbers).

    So the prisoners are up to something, and it's time for warden Betelfax to punish them with a logic puzzle that will grant them freedom if solved or instant death if flubbed.


  6. After more thought:


    My previous answer talked about finding a circle where the maiden could have a faster radial velocity than the ogre. She would get in as good of a position as possible within that circle and then make a straight dash for the exit.

    Now I think her best trajectory is not a straight dash, but one that bends away from the ogre’s current position a little. If M is the maiden's distance from the center of the lake and dM is the rate of change in M, and dA is the rate of change in the angle from the ogre to the center of the lake to the maiden, then the optimal path should be the one with the largest dM/dA ratio. Define angle B as the difference between the direction the maiden is traveling and a line straight out from the center. dM is f cos(B). dA is the ogre’s angular velocity minus the maiden’s angular velocity, so 1 – f sin(B)/M. In principle you could find the angle B that maximizes dM/dA = f cos(B) / (1 – f sin(B)/M) by setting the derivative with respect to B to zero. But that would tell you the best strategy if she can change direction instantaneously and I’m not yet sure how to incorporate her turning speed into that part of the answer.


  7. I'm pretty sure this isn't optimal, but it's a start.


    I think the solution for the previous problem (where the maiden could turn the boat instantaneously) came down to realizing that she could go in a circle of some radius R that’s smaller than the entire lake and be able to move at a radial speed faster than the ogre (she moves a number of degrees around that small circle that’s just slightly more than the number of degrees that the ogre can move around the edge of the lake in the same amount of time). As long as she can move around that inner circle faster than the ogre can move around the perimeter, she can set it up so she’s opposite the ogre when she makes a dash for the shore.

    If the maiden tries that same strategy in this problem, first she needs to find a circle of radius R where she’s moving at a radial speed that’s faster than the ogre. Define the lake’s radius as 1 and the ogre’s speed as 1, so it will take the ogre 2 pi time units to run around the lake. For the maiden to paddle around a circle of radius R she would need to make a 360 degree turn, and the amount of time it takes to rotate the boat 360 degrees is 1/g times the amount of time it takes the ogre to circle the lake, so the maiden spends (2 pi)/g time units turning. The amount of remaining time she has to move the boat forward is [the amount of time it takes for the ogre to circle the lake] – [the amount of time spent rotating the boat] = (2 pi) – (2 pi)/g = (2 pi) (g-1)/g time units to move forward. Her forward speed is f, so she’ll travel a distance of f(2 pi) (g-1)/g. That’s the circumference of the circle she can paddle around, and its radius R is that divided by 2 pi, so R = f(g-1)/g.

    She can position things however she likes within that circle, but then she’ll have to bolt for the shore. I suspect that just charging forward in a straight line is not optimal, but I’ll go ahead and solve for that strategy.

    Her boat won’t be pointing toward the shore when she decides to bolt, it will be pointing parallel to the edge of the circle where she’s paddling. If she’s at a distance R from the center of the lake and just paddles forward in the direction she’s facing, the distance until reaching the shore would be sqrt(1-R2), or sqrt(1-(f(g-1)/g)2). As long as the maiden bolts when her landing spot will be opposite to the ogre’s current position, the ogre will have to travel a distance of pi to reach the landing point. With that strategy, the maiden can be sure of safety if the distance she has to travel is less than f times the distance the ogre has to travel, so the condition for victory is
    sqrt(1-(f(g-1)/g)2) < f pi

    For the case of g=2,
    sqrt(1-(f/2)2) < f pi
    sqrt((4-f2)/4) < f pi
    sqrt(4-f2) < f 2 pi
    4-f2 < f2 4 pi2
    4 < f2 4 pi2 + f2
    4 < f2 (4 pi2 + 1)
    so f > sqrt(4 / (4 pi2 + 1)) or about 0.31435

    Kind of surprisingly, that strategy is only very marginally better than sitting in the center of the lake and rotating until she's facing away from the ogre and then taking off. With that strategy she would travel 1 lake radius and the ogre would have to run pi lake radii, so she wins if f > 1/pi or about 0.31831.

  8. I agree completely with EventHorizon, and will try to summarize in a way that addresses the OP and deconvolutes the paradox at its heart:


    If Plato were to pick a number, say 4, and decide that he would tell you "You rolled a 4" or "You didn't roll a 4", then Aristotle would actually be correct. There's an 11/36 chance that he would roll a 4, and among those outcomes there are 2 that sum to 7, so if Plato says "you rolled a 4" then there really is a 2/11 chance that the sum is 7. Alternatively, there's a 25/36 chance that he doesn't roll any 4s, and among those outcomes there are 4 that sum to 7, so if Plato says "you didn't roll a 4" then there's a 4/25 chance that the sum is 7. So Aristotle is slightly more likely to have rolled a 7 if Plato says he rolled a 4 (or any other number). The reason for this is that if Aristotle rolls doubles then it obviously won't sum to 7, and Plato is slightly less likely to say that Aristotle rolled any given number if he rolled doubles (1/6 chance of rolling the number Plato picked) than if he rolled two different numbers (1/3 chance of rolling the number Plato picked).

    On the other hand, if Plato picks one of the two numbers that are rolled and calls it out, the math is different. If Aristotle rolls two different numbers then there's a 1/2 chance that Plato will call out either of the two numbers, but if he rolls doubles then there's a 1/1 chance that Plato will call out that number. So there are 11 possible rolls that could lead to Plato calling out 4, but one of those possibilities (rolling double 4s) is twice as likely to lead Plato saying that he rolled a 4 as the others, so the odds of rolling a sum of 7 should be 2/12 instead of 2/11. This fits with our intuition that if Plato simply picks one of the numbers to call out then it shouldn't affect the probability of whether the sum is 7.

    The apparent paradox arises because you're doing the math assuming that Plato's acting as described in the first paragraph, but really he's acting as described in the second paragraph.


  9. 18 hours ago, EventHorizon said:


      Hide contents

    Instead of red and white, you could just use "the die Plato said was a 4" and "the other one."



      Hide contents

    First, Thalia just says the answer is 1/6 without the extra "i can tell you one die is X", so has nothing to do with 2/11.  I assume you mean Aristotle.

    But why does there need to be a normalization at all?  What went wrong such that it was necessary?

      Hide contents


    It is true that P(11)=P(12)=...=P(66).  Each possible dice roll can happen with equal probability.

    But once Plato says that "one die is a 4," it doesn't merely prune out the ones without 4's.  Using Bayes theorem we can see this.

    P(41 | one is 4) = P(one is 4 | 41) * P(41) / P(one is 4)

    Obviously P(41) is 1/36.  P(one is 4) and P(one is 4 | 41) need an assumption on how Plato decides which value to tell.  Assuming he would uniformly random choose a die to report on, we can see P(one is 4)=1/6 since all values are equally likely and P(one is 4 | 41)=1/2 since he has two options randomly chosen from.

    P(41 | one is 4) = (1/2) * (1/36) / (1/6) = 1/12

    This is the same for 42,43,45,46,14,24,34,54,64.

    But since 44 only has one value possible to report, the value is different.

    P(44 | one is 4) = 1 * (1/36) / (1/6) = 1/6.  So given that one is a 4, the roll 44 is twice as likely as the other 10 possibilities.

    To finish finding the answer...

    P(sum is 7 | one is 4) = P(34 | one is 4) + P(43 | one is 4) = 1/12 + 1/12 = 1/6.

    Of course, if Plato always decides to tell the smaller value shown on the dice or anything other than uniformly random, the probability distribution could be wildly different.



    The part that I turned red in the quote bugs me a little bit.


    If you're given that one of the numbers is four, then saying that the probability of rolling a four and a one (in that order) is 1/12 seems at odds with there being eleven possible rolls with a four. But it does make sense if you assume that Plato will randomly pick one of the two dice and announce its number, since he's twice as likely to say that you rolled a four if you rolled a double-four than if you rolled a four and any other number, so you can count that possibility twice and bring the denominator to 12.

    Suppose instead that Plato picked a number N before the dice were rolled and would plan to say either "You rolled an N" or "You didn't roll an N" as if he were in the Donny Hall puzzle?


  10. 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, 


    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.


  11. 9 hours ago, bonanova said:

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


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


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

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


    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.


    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.


    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.


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

  15. 10 hours ago, bonanova said:


      Hide contents

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


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


    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

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

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

  18. 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,

    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 ^_^

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

  20. This gets tricky with rolls like (1, 1, 6) that look isosceles but don't actually form triangles.

    How would you handle such rolls? Would you omit rolls that don't form a triangle from analysis (equivalent to saying that if you get a roll that doesn't form a valid triangle then roll again), or count them as a failure to form an isosceles triangle? And would you consider a "straight line" throw like (3, 3, 6) to be a valid triangle albeit with zero area or nah?

  • Create New...