In the same vein: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Show HN: I made a puzzle game that gently introduces my favorite math mysteries
161–170 of 177 posts
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#162Earlier quoted context omitted.
You might want to colour the exclave the same colour as the rest of its country, even though no connection can exist between them on the plane.
It seems like you're using "enclave" and "exclave" interchangeably, which is causing confusion. What you're referring to is an exclave; an enclave is when one region is completely surrounded by another, like Lesotho or Vatican City.
You're right, my first post should say exclaves and the three examples I gave are all exclaves.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#163I showed this to my two kids, and we all three enjoyed it. The zero knowledge proof portion didnt really click for me, but we liked the four color map theorem stuff. This led me to download some maps for my kids to attempt coloring on paper, and also got me wondering about how this holds or doesn't on non-euclidian spaces. Turns out the maximum is four colors on a sphere, but 7 colors on a torus! More details here: h…
Regarding the zero knowledge proof, there'd be a chance that the two random ones you reveal are the same color, if three weren't enough. So by doing this over and over again, if the two you choose are always different colors, you approach a 100% certainty that it's legit. You never really get a 100% proof but the more times you repeat the closer you are to being sure. At 99.999999% after repeating this enough times,…
When I read the zero knowledge proof part the first time, my thought was:
The person can just always give two different colors (and never two same colors) when you reveal two post it notes, so you could never proof them false.
Only after re-reading I realized _all_ the colors are to be hidden under the post it notes _beforehand_, not at the time you choose two post it notes.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#164I showed this to my two kids, and we all three enjoyed it. The zero knowledge proof portion didnt really click for me, but we liked the four color map theorem stuff. This led me to download some maps for my kids to attempt coloring on paper, and also got me wondering about how this holds or doesn't on non-euclidian spaces. Turns out the maximum is four colors on a sphere, but 7 colors on a torus! More details here: h…
Does the torus one apply to a wrap-around 2D map then? So if the edges don't wrap, the max amount of colors needed is 4, but if the edges do wrap, you could make a map requiring 7 colors?
EDIT: yep looks like it, the leftmost picture under 'snapshots' here is a 2D map of what's on the torus and looking at e.g. the blue band, it touches all 6 others (just barely the cyan and yellow ones with a few pixels of its tips when wrapping between top/bottom): https://demonstrations.wolfram.com/SevenColoringOfATorus/
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#165Earlier quoted context omitted.
Why would it be necessary for a graph requiring 5 colours to have a 5-clique (as it's called [1])? The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours. (Try drawing out the incidence graph of the faces, i.e. a vertex is a US state and an edge is two states bordering. Lots of 3-cliques (triangles), but no 4-clique!) Side note: indeed, 5-cliques are not planar : that is to say, there is no m…
"The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours." It has something very similar to a 4-clique that can be simplified to a 4-clique for the purposes of the coloring exercise: https://imgur.com/a/oRJBkFp Or more generally, if you have any hub-and-spoke topology with an odd number of spokes, it can be simplified to a 4-clique and have the same properties. So I concede that a graph requir…
Impressive deduction from someone not into graph theory, but what you're saying is actually known as the Hadwiger conjecture. It says that if a graph isn't t-colorable, then it must have K_t as a minor, where the concept of minor is what you mean (perhaps) with "simplified to".
It so happens that planar graphs are K_5 minor free.
This is touching in on extremely deep theory in the graph theory field.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#166I loved this, and, like others, walked through it with my two kids (7,9). They have up at the last page but they seemed to enjoy the process nonetheless!
Good job, would love to see more.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#167This is awesome and I hope in-general that a lot more education is done this way, especially with complicated concepts. I wonder if this sort of interactive toy explanation is currently used in classrooms?
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#168> Warning: very difficult! Skip after trying a lot. I think "very difficult" is misleading here. It implies there is an answer if you try hard enough.
There'sa tidbit for you later if you continue (The "do you trust me")
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#169I remember when our neighbor Ken Appel proved the 4-color theorem (together with help from Arnand Haken). He had help from his teenage kids (Andrew, Laurel, & Peter) who helped him to check the output of the computer program that generated more than 1,000 different patterns and colorings to ensure that they could all be colored with only 4 colors. Andrew (son of Ken Apple) today teaches at Princeton University. https://www.cs.princeton.edu/people/profile/appel
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#170Earlier quoted context omitted.
I think that conveys what a zero knowledge proof achieves but it doesn't really correspond to any real zero knowledge proof algorithms. You can't do that over the phone, which is kind of the whole point.
no, that's not even close to the whole point. the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution the paint-mixing analogy of diffie-hellman also can't be done over the phone, but it helps people understand how a shared secret can be established even if all communication is intercepted
It is the whole point. ZKPs are useless if you can't do them remotely.
> the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution
Yes that's what I said.