I can't think of one but I also can't think of a reason why such a puzzle can't exist. Jim On Sat, Mar 14, 2020 at 9:14 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Consider the set of all vectors that look like (-1, -1, 1), surrounded by zeros, and rotations of this. Each such vector corresponds to a hop.
Then if I understand you correctly, a fractional solution would be one that writes the difference between the initial and final states as a linear combination of these vectors with nonnegative coefficients, and a real solution is one where these coefficients are all 0 or 1. (We also need to be able to order these so that no coordinate ever becomes less than 0 or more than 1.)
Can you think of a Hi-Q puzzle that has a fractional solution but no real solution?
- Cris
On Mar 14, 2020, at 1:25 PM, James Propp <jamespropp@gmail.com> wrote:
Thanks, Cris. I didn’t know that it was NP complete (it’s possible that I once knew and then forgot).
What if one allows fractional moves? Equivalently, what if one is allowed to have multiple pegs occupying the same spot, and at any stage you’re allowed to replace every remaining peg by n pegs, for whatever n you choose? That might make the puzzle more tractable.
Alternatively one might allow “negative pegs”.
If one allows fractional *and* negative pegs, then the puzzle just becomes linear algebra and surely is in P, but this variant doesn’t seem to be very playable, at least not with the original physical instantiation of the puzzle.
Another direction might be to pick a cute mathematical structure and then choose the rules of play accordingly. That’s what I did when I designed Swine in a Line:
https://www.google.com/amp/s/mathenchant.wordpress.com/2017/07/17/swine-in-a...
I’m reminded of Lights Out, which also uses linear algebra, but over the field with two elements.
Any thoughts?
Jim
On Sat, Mar 14, 2020 at 1:57 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
I’m sure you know that on general board’s it’s NP-complete. On one-dimensional boards (which most children would probably find boring) it’s in P (see a paper by David Eppstein and me).
My favorite thing to do was play it backwards… you can also do a two-player version where the first person to get stuck loses.
- Cris
On Mar 14, 2020, at 11:53 AM, James Propp <jamespropp@gmail.com>
wrote:
I bought a vintage Hi-Q set for my family a few weeks ago:
https://en.wikipedia.org/wiki/Peg_solitaire
Now that I'll be spending lots of time at home with my kids, I'm
thinking
that there should be some good activities we could do with it.
Any ideas?
I know that Berlekamp-Conway-Guy has a section on this, and maybe it even explains how to win, but I don't want to just see the answer; I'd like a "curriculum" that'll Socratically guide me and my kids towards the solution. (Or is it the sort of puzzle where you basically need to use a brute-force approach?)
I kind of like the fact that I don't know the solution; it puts me and my kids more on the same level.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun