13 ms·

Show HN: I made a puzzle game that gently introduces my favorite math mysteries

1054 points by MCSP 2y ago

This is the first iteration of a short game I’m making that tries to interactively explain some of my favorite math questions / ideas. My goal is mostly to get the player curious and not necessarily to explain absolutely everything. There were a lot of fun technical parts to building this: - For implementation reasons, it’s much easier if the lines all have integer intersection points with each other. To do this, when a new line is added I “cheat” by rounding intersections to integers and then splitting the old lines at the intersection into new linds (with potentially different slopes) going through the rounded point - I had to draw semi accurate maps of actual places (UK, South America, US west coast) in the HTML canvas using just line segments. I tried a few different solutions, including using SVG data. I ended up using the topojson library to give nice line approximations to GeoJSON maps - I use a simple backtracking algorithm to handle the live coloring of graphs - I use turf.js’s polygonize function to handle finding polygons from line segments (very happy I didn’t have to implement this myself!) - I wanted to make the game as mobile friendly as possible (don’t think I’ve nailed this quite yet) There were also a few tradeoffs I made: - I wanted give links earlier in the game for players to learn more, but I decided to wait until the end to maintain the flow of the game - In order to make the game more mobile-friendly, I generally stuck to maps with a small number of regions (at least for maps people have to interact with them). So for the most part all of the instances in the game are “easy”

stop50 2y ago
Very nice. I had no problems playing it.
baruchel 2y ago
Hi, my two cents; you claim "Although mathematicians believe their proof is correct, it is too complex to verify without computer assistance", but I'm not sure "believe" is the correct verb since the proof has been formally verified (see for instance https://github.com/coq-community/fourcolor https://github.com/coq-community/fourcolor for a formal verification in Coq). I understand that you want to emphasize the fact that no human can understand the proof with a full overview, but I wonder whether the current sentence will not make people think mathematicians are not perfectly sure of the proof.
- MCSP 2y ago
  Good point! I'll try to think about a better way to phrase this (happy to hear suggestions)
  - lcnPylGDnU4H9OF 2y ago
    "Although mathematicians have been able to prove this, the proof is too complex to verify without computer assistance." Or some such.
  - valenterry 2y ago
    Nah, actually I agree with you. What counts as believe and what as fact is rather abitrary. Is 2+2=4 a fact? Is global warming a fact? What about man-made global warming? Ask 100 people whether something is a fact or a believe. To top that up, it's fact that there have been "proves" that were wrong (or maybe that's just my believe? :^]) even for a long time. Hence, I think we can say that there are 4 options for a theorem: 1) Some mathematician believes the theorem is correct (but can't prove it) 2) Some mathematician believes the theorem is incorrect (but can't prove it) 3) Some mathematician believes the proof of a theorem is correct 4) Some mathematician believes the proof of a theorem is incorrect Proving that a proof is correct is kind of meaningless. At that point it's all believe anyways.
    - konschubert 2y ago
      ^ Exhibit A why using "believe" is a bad choice of words. Mathematical poofs are either correct or false. There is no middle ground.
      - karmakurtisaani 2y ago
        Well.. there is. Middle ground being a very complex, but somehow convincing argument that no one can reasonably check. There was one of these cases in number theory some years ago, can't remember the details. Proofs can be only true or false, but accepting proofs is in the end a social process.
AndrewOMartin 2y ago
Can you add to the FAQ at the end an answer to the question "How do I know you're not just showing me two random colors?"? It's possible this is already addressed and I missed it.
- hcs 2y ago
  You do need to prove that you have assigned the colors before the choice of what to reveal is made, I think. Physically this is guaranteed by the presence of the colors under the post-its (barring dynamic e-paper or something). I'm not sure how it works with the example of the primes, I lost the link to the later pages of the game so I can't read over it again, but I think it's guaranteed because there's just one number encoding all the assignments and you just get to unlock a single pair with the key given in response to your choice. There's an assumption that there isn't enough information in the key to fake any response, it has to reveal something that was already in there.
  - MCSP 2y ago
    You're exactly right. The definition via primes ensures there is only one color consistent with each number (formally, this is called a perfectly binding commitment scheme). Also, here's the link if you want to go back: rahulilango.com/coloring/zk
    - hcs 2y ago
      Thanks! And this is a great exercise, thanks for sharing it.
- MCSP 2y ago
  Thanks for the feedback! As hcs suggests, this is part of the physical post-it assumption. I'll think about ways to make it more clear -- adding an FAQ is a good idea :)
  - gowld 2y ago
    All that's missing is more info in the answer to this question: > Question: How do you do this in the digital world, without post-it notes? Answer: "When I give you a map labelled with numbers for each region, the numbers are the "post-it notes", "covering" the list of factors (which encodes a color). You can't see the primes factors inside them, because, even though generating an multiplying large primes is easy for computers, factoring numbers is much, much harder.)" I think if, when the player checks "reply the demo, with numbers", you move the game down to where the prime number discussion is, it's easier to understand. Also, note that the digital versionis better than the physical version. In the physical version, you can't stop me from removing extra notes. (A better example might be to put each color in a locked box, each with a different lock/key.) In the digital version, the factor lists are the "keys".
zem 2y ago
great work!
chromy 2y ago
The Republic of Ireland (the west most region on the first page) isn't part of the United Kingdom. The term for the group of regions shown is 'the British Isles'. See https://qntm.org/uk https://qntm.org/uk While it seems like a trivial distinction the whole thing is somewhat fraught (https://en.wikipedia.org/wiki/The_Troubles https://en.wikipedia.org/wiki/The_Troubles).
- MCSP 2y ago
  Whoops! Switched to "British Isles" -- update should be percolating now
  - darajava 2y ago
    I prefer the term “Atlantic Archipelago”. The “British Isles” encompassing a non-british sovereign state is contentious. Other good terms are “Britain and Ireland” or the “British-Irish isles”
    - MCSP 2y ago
      Now switched to "Britain + Ireland," thanks!
    - card_zero 2y ago
      Yeah, "Britain and Ireland" is straightforward. "Atlantic Archipelago" makes me think you mean the Canary Islands.
    - bumbledraven 2y ago
      "British Isles" is the commonly-accepted term, and it doesn't seem to be particularly contentious outside of Ireland. As https://en.wikipedia.org/wiki/British_Isles https://en.wikipedia.org/wiki/British_Isles notes: > As a term, "British Isles" is a geographical name and not a political unit.
- romwell 2y ago
  It's about as "trivial" a distinction as considering Crimea (or the entirety of Ukraine, for that matter) a part of Russia. Many, many people have died for this triviality. "Somewhat fraught" is a very interesting choice of words, but then again, so is "The Troubles" (when the subject matter is decades of bombings and killings).
noodlesUK 2y ago
Just FYI the “map of the UK” includes the Republic of Ireland, which is very much not part of the UK. There’s not a 100% great term for the collective unit of land. Generally people go with “UK & Ireland” if they’re trying to be sensitive.
- MCSP 2y ago
  Thanks for pointing this out! Switched to "British Isles" -- update should be percolating now
  - messe 2y ago
    The British Isles is also a somewhat controversial term with colonial implications, and it's not used by the government of Ireland[1]. "Britain and Ireland" would be a safer bet, as the map doesn't include any other islands. https://en.wikipedia.org/wiki/Names_of_the_British_Isles https://en.wikipedia.org/wiki/Names_of_the_British_Isles
    - russellbeattie 2y ago
      Diving into Wikipedia, apparently variations of the name "Britain" have been in use since 30BC, and referred to the big island, with the smaller islands grouped with it, e.g. British Isles. The Irish may not like it, but they're fighting against two millenia of history.
      - messe 2y ago
        And it's use in English only comes from the mid 16th and 17th centuries, right around the time that much of Ireland was being colonized by the British. Frankly, I find the term offensive, and think it should be discouraged in much the same way people have shifted away from "the Ukraine" to simply Ukraine.
        returningfory2 2y ago
        Why is "the Ukraine" bad?
joshlk 2y ago
That was fun. On another note, I dislike how “Zero-Knowledge Proofs” are called proofs. It’s not a proof. You iteratively increase your belief that the result is true, like in experimentation, but that’s not a proof.
- tyilo 2y ago
  If someone has signed something cryptographically, wouldn't you say that the signature was a proof of someone with the private key signing it? (Even though it is possible to construct a valid signature without the private key - you just have to be very very very lucky) I guess you also don't like the name Proof of Work.
- hcs 2y ago
  It might help to think of the sense of "proof" that's synonymous with "trial", rather than a specific formal math sense of proving a theorem from axioms by formal transformations.
- fragmede 2y ago
  zero knowledge corroboration isn't the same thing as a zero knowledge proof. If the provided evidence isn't enough, then you keep iterating until it's proven.
sakras 2y ago
This was fun, I went into this thinking "Ha I already know this theorem" but came out learning something about zero knowledge proofs!
js98 2y ago
Nice work! I spent a bit too much time creating a map with 5 colors… ;)
franciscop 2y ago
[spoiler alert] I knew that 4 colours sufficed for any arbitrary map from back in the day when I learned this, but still I found it VERY rewarding by attempting to draw a map that needed 5 colors, and how intuitive this demo was for getting a "feel" for a thing that I knew only theoretically! Like I needed an impossible geometry to fit, either an area that stretched to a zero-width path (which would becomes a point, and thus 2 areas, so doesn't fit) or some other "impossible" geometry. Loved it, congrats on a really well executed idea!
- genewitch 2y ago
  there has to be a layman's explanation. I knew the easiest way to get four colors was to put a split square inside another split square "donut", but the reason you can't force 5 colors is that word "inside". There has to be a nice, tidy "verbal proof" that no matter what, one or more colors will be "trapped" inside at most 3 other colors.
  - waterproof 2y ago
    You would think. The easier, five-color theorem proof fits in a few paragraphs but the four-color theorem really resists a simple explanation. Even the simplified 1990s version of the proof (which came ~20 years after the original proof and 100 years after the 5CT proof) required enumeration of hundreds of individual cases. https://en.m.wikipedia.org/wiki/Four_color_theorem https://en.m.wikipedia.org/wiki/Four_color_theorem
- 8organicbits 2y ago
  It was really enjoyable to try. I got an optimal 4-color map on the first try, so I was over confident. My approach was something like: put a bunch of the 4-color maps next to a long Chile-like thing. When that didn't work I added borders until my device couldn't render it any longer. Very very fun.
OmarShehata 2y ago
I love this! I'd for this to be a more typical experience in math class (I bought Paul Lockhart's "measurements" but gave up because I felt like I needed a sandbox to play with and little hints. Like, I don't want to be told the answer but I want to know feedback exactly like this demo. Very simple: "this is not right" or "this is right, but can be done with fewer") (My dream is to have a little game jam where we make interactive versions of these concepts as puzzle)
dunefox 2y ago
In Android using Firefox the button to go to the next challenge doesn't seem to work.
- MCSP 2y ago
  Will look into this. Did it happen on the first page (map of Britain + Ireland)?
  - dunefox 2y ago
    Yes.
mbivert 2y ago
Enjoyed the tutorial very much, thanks. As a suggestion, I would dearly enjoy a follow-up rigorously connecting those visual, intuitive ideas to actual mathematics.
soneca 2y ago
Great job! I enjoyed going through the steps. The final though seemed like a huge leap for me, who don’t know anything about those math mysteries (which I assume is your target audience). First I was curious to learn how is the fast way to understand that 1, 2, or 4 colors suffice. And why finding out such a way for 3 is so hard. The zero-knowledge proof demonstration felt like “changing the subject”. Probably I missed the connection there.
- gowld 2y ago
  ZKP is the subject. The maps part is a helper lemma. It would help to clarify that in the beginning. The game is a bit of a shaggy dog tail. It would be good to give an outline and progress bar at the start (without spoilers)
windowshopping 2y ago
I went in skeptical and got completely hooked. Well played. Very neat thing to build. Wish more math were taught creatively like this.
deleted 2y ago
[deleted]
zamadatix 2y ago
Loved the interactions and flow overall but I'm a bit lost on the zero knowledge proof example. I'm familiar with the concept but I don't follow how the example is one. E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof? If I pick a hundred numbers it'll look like I just proved some black box function which happens to be Sin[n] + 0.999999999999 is always positive even though I'd be able to clearly show it negative with the knowledge of the function. It feels like something that got detached from the things that make it work during simplification. Or it could be that I just have a misunderstanding/oversight in the zero knowledge proof :). In an unrelated note: I colored the larger graph and it didn't even play along!
- esquivalience 2y ago
  I think the answer is that each time you reveal the colours, you observe that they are within the set of three colours illustrated at the beginning of the proof. Whichever you reveal, you never find a fourth colour. This confused me at first.
  - zamadatix 2y ago
    For anyone confused by this response I had edited my comment after reading https://news.ycombinator.com/item?id=40740557 https://news.ycombinator.com/item?id=40740557 but before equivalence had hit reply and now their reply is left hanging. Sorry esquivalience! To summarize the linked answer on trusting the second dot isn't just randomly assigned: keep the context as physical post-its. Barring something like a matter bending psychic you'd be able to tell the dot under the second post-it was swapped as you made your pick. That still leaves how to rely on chance of picks for a proof though.
    - romwell 2y ago
      It's the same thing as limits in spirit. It's not that the chances of lying are small, it's that they can be made arbitrarily small. Let's say my standards of "proof" are that there's only 0.1% chance that you're cheating. We play that game several times, and I'm satisfied. Next comes someone else whose standard is 0.001% chance of cheating. They simply play the game a few more times, and they're satisfied too. If they change their mind and decide that only 0.0000001% will make them happy, they simply tack on a few more rounds. The key here is that the probability that you can cheat for arbitrarily long is exactly zero — for the same reason that Zeno's paradox is resolvable (and limit of 1, 1/2, 1/4, 1/8, 1/16, ... is exactly zero, and not just a very small number).
sverona 2y ago
This is cute. You should flag the "I claim that three colors suffice" map if the user actually 3-colors it. At least, I think I did...
vavooom 2y ago
that was fun :)
SilasX 2y ago
Uh, when you draw the map that requires three colors, I couldn't figure out how to submit it to at least be told it's not good enough. Or if it automatically accepts for a 3-min [1], then it was too hard to make sure that the boundary reached the edge of the screen. (I thought I successfully drew five regions around a point.) [1] sorry, 3-chromatic or whatever
- MCSP 2y ago
  Hmm, my guess is you're trying to use the box's borders as lines (they don't count, only the lines you draw count). Let me know if that's not the issue. Also, I'll think about ways to make this more clear!
  - JoshTriplett 2y ago
    You could automatically "zoom out" what they draw if they get too close to the border. Alternatively, you could automatically "close" figures after they have at least three points, and give a hint of a handle that allows dragging a new point out of the middle of an existing side.
  - SilasX 2y ago
    Ah okay -- the second one had a map with the same shape as the border, which I think made me mentally lump the map's border with the box's borders and invalidate the claim that it's looking at the box's borders as part of the map. I also assumed you wouldn't possibly expect someone to have to explicitly draw all their borders when they can piggyback off the box. Entirely my mistake because I was kind of ignoring everything you said lol
gcyjjkjg 2y ago
[flagged]
trirpi 2y ago
There seems to be an error in the backtracking algorithm. E.g.: https://imgur.com/a/1miv1AK https://imgur.com/a/1miv1AK
- MCSP 2y ago
  Good catch -- I'll look into this!
andrei-akopian 2y ago
1. Nice site, bookmarked to give it to people. 2. You are a very bad and annoying person ;)
dcastm 2y ago
Thanks for sharing. This was instructive and fun in equal parts
gkoberger 2y ago
This was one of the cooler teaching examples I've ever played with... awesome job! Appreciate the warning that the 5 color map is "very difficult". It felt easy enough, and I would have spent an hour on it! This was so much cooler than just being told that 4 colors is enough for every map – this one will stick with me. It would be wonderful if schools taught a bit more like this – I almost felt like I discovered it myself!
ModernMech 2y ago
It's very fun! Only thing I would change is to make it so clicking on the picture doesn't trigger a text select, it was hard to play because a context menu kept popping up every time I changed map color.
neuron-enix 2y ago
There goes my 2hrs of sleep, trying to solve feeling that I was close to solving, only to see myself draw shapes that I have never seen or imagined in my life. Well in the end it was fun, but the warning is very misleading at least from a game perspective. I have played games at the same level but it certainly wasnt this hard, haha... But hey, saying that it was difficult, was the only thing that kept me going for 2hrs, only to be annoyed and have a face palm moment after seeing the answer. Nonetheless it's good post
umvi 2y ago
Seems easy to intuitively prove that 5 colors is impossible. In order to need 5 colors, you'd need to construct a graph with 5 nodes where each of the nodes connects to all other nodes, but without any edges crossing: https://imgur.com/U52SFSi https://imgur.com/U52SFSi You can just tell after playing around with the graph that it's impossible to move the nodes around on a 2d plane without an edge crossing; you need a 3rd dimension.
- SamBam 2y ago
  I've always found what happens in the third dimension weird. A 0-dimensional space needs up to: 1 color. A 1-dimensional space needs up to: 2 colors. A 2-dimensional space needs up to: 4 colors. A 3-dimensional space needs up to: ∞ colors. I can easily picture why a 3D space has no limit to the number of colors (personally I always imagine color blocks hanging in space connected to every other color block by bendable wires), but I don't quite understand why the pattern is that way.
  - Halfwhit 2y ago
    Imagine the colours of a hypercube in 4-dimensional space!
    - genewitch 2y ago
      A mantis shrimp told me, quote, "it's alright, i guess, if you're in to that sort of thing"
- tomsmeding 2y ago
  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 map you can draw that has five regions all bordering each other. This is not too difficult to prove, actually. Proving that 4 colours is enough is a whole different league! [1]: https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory) [2]: https://www.rahulilango.com/coloring/wus https://www.rahulilango.com/coloring/wus
teddarific 2y ago
Wow, this was a lot of fun. 3 was a lot harder than expected — a great exercise for anyone honestly. I'm a math nerd so this was cool visualized!
- genewitch 2y ago
  the easiest 3 is an equilateral triangle split in half with any shape containing it - for 4 split the container perpendicular to the split in the triangle. |-/|\-|
bgoated01 2y ago
I 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: https://mathworld.wolfram.com/TorusColoring.html https://mathworld.wolfram.com/TorusColoring.html Thanks for leading us down this mathematical rabbit hole today.
- enlyth 2y ago
  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, you'd most likely be satisfied.
  - Aardwolf 2y ago
    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.
- pwmtr 2y ago
  This video helped me a lot to understand the basics of zero knowledge proof: https://www.youtube.com/watch?v=fOGdb1CTu5c https://www.youtube.com/watch?v=fOGdb1CTu5c
  - wonger_ 2y ago
    Great video, thanks. My takeaways: - The physical demonstrations at 1:16 and 3:48 were helpful - thinking of proofs as between a prover and a verifier, not as classical deterministic proofs - insight into the name "zero-knowledge", as in "you can already predict the answer, so you're not gaining any knowledge from that interaction"
your_friend 2y ago
How cool! I didn’t expect it will end up with ZK proofs that I was curious about for a long time. (After reading it I still don’t quite get the details of how they are working tho)
jostylr 2y ago
That was enjoyable. You could submit this to the summer of math exposition: https://some.3b1b.co/ https://some.3b1b.co/
nirolo 2y ago
You might want to get into touch with some museums on science topics to see if they are up to show it. I live in Germany at the moment and know of at least two MINT focused museums that let visitors engage a lot with their (sometimes digital) exhibits and this here checks all the boxes to make a great exhibit. Very well done, I'll try to see if my children will enjoy that already too.
- wrsh07 2y ago
  Absolutely!! Talk to MoMath in NYC too I'm happy to find a contact there if you want
JohnMakin 2y ago
This gave me PTSD flashbacks to an extremely difficult computational geometry course I took once, but this is cool.
personjerry 2y ago
How does the zero-knowledge solution make sense? Can't you just cheat and show me two random different colors whenever I click two post-its?
- namjh 2y ago
  In reality, the entire map should be sent first to the verifier (with colors hid behind the post-it) so if it was a bogus randomly colored map, you may find two adjacent points having same color if you try extremely many(think hundreds or thousands in the website's case) times. If you sufficiently try many times and fail to find the adjacent points, you will convince that the prover have the map which is correctly 3-colored. Note that the entire map is sent again, shuffled its color each time after you choose the two points.
aib 2y ago
Ahh, very nice. It was fun to rediscover/relearn some of these things through this game. Very nice wording on the 5-color challenge! I think it was the perfect balance. One thing I was missing was the ability to move the points already on canvas. I assume you already considered, though. (As well as right-click-to-remove?)
NegativeLatency 2y ago
Something about 4 colors makes sense to me intuitively because you've got 0 or 1 color for each of the two cartesian axes (2 * 2 = 4). Not sure there's anything behind that though.
- zaik 2y ago
  Well it does not generalize into 3 dimensions: https://math.stackexchange.com/a/4767802 https://math.stackexchange.com/a/4767802
passwordoops 2y ago
So addictive! And it's great how you tie it in to the greater mathematical concept. I'm loving it!!
tzs 2y ago
> Step 1. I put a <purple circle>, <blue circle>, or <red circle> color dot on each region, but hide it under a post-it > Step 2. You click any two bordering regions, and I pull off their post-its > Step 3. You check that the revealed colors are different I would add explicitly in step 1 that you tell me what 3 colors you used, and in step 3 that I check that the revealed colors are different from each other and are both from that set of 3. Similar in the explanation of why this should convince me.
poopcat 2y ago
Had a great time with this! Great break to get my mental gears moving
sn41 2y ago
Just a quick note: Rahul Ilango is a phenomenal theoretical CS researcher who has made great progress towards understanding the "Minimum Circuit Size Problem" [MCSP], long believed to be, but not yet proven, NP hard. Needless to add, "the username checks out".
MrZander 2y ago
I know that it is impossible, but it was fun to try to make a 5 color map work. That being said, is this a bug? https://imgur.com/a/zbkYg9j https://imgur.com/a/zbkYg9j I can't seem to wrap my head around why this isn't 3 colors.
- deleted 2y ago
  [deleted]
barbariangrunge 2y ago
This is lovely. The Ux isn’t my favourite when it’s time to draw but it’s pretty great besides that
gpnt 2y ago
> 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.
- genewitch 2y ago
  well, i knew there was no answer and i still tried for 15 minutes. I think that's the point!
- zild3d 2y ago
  i appreciate the intention to let you struggle with it on your own for a bit, but not go crazy. a better experience might be having the warning reveal more after a few attempts, but I don't mind starting with a "warning it's surprisingly tricky"
- kzrdude 2y ago
  There'sa tidbit for you later if you continue (The "do you trust me")
next_xibalba 2y ago
Although I still didn't fully understand the relation between zero knowledge proofs and the post-it example, this game is just kind of fun in its own right!
namjh 2y ago
Great work! I really enjoyed the interactivity. Actually I already was aware of the concept of zero-knowledge proof from the wonderful article by ZCash(which is a privacy-oriented cryptocurrency) core developer Matthew Green, worth to check it out: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... My two cents of the ZKP illustration is that directly using hashes are more likely to convince "computer-friendly" people to introduce the commitment scheme.
- pontifier 2y ago
  I triggered a coloring bug as well during that stage.
Guvante 2y ago
Fun fact, one of the reasons the four color problem is hard to prove is there isn't an algorithm that can color a map in four colors. Well beyond effectively trivial ones where you try over and over again. But the algorithm for coloring with five is pretty easy (relatively speaking still involves fun graph theory)
ehershey 2y ago
Wow what a fun little interesting time. My wife and I made it to the end on mobile!
hgyjnbdet 2y ago
Spent way too long on the five colour thing refusing to skip. You always have to surround one colour which then protects it. You simply can't touch four colours at once. Then I skipped it and found out it was impossible, FML.
PUSH_AX 2y ago
Thanks for taking me on that journey!
snthpy 2y ago
Nice! I knew the 4-colour theorem but the zero knowledge proof illustration was great. I didn't get it initially but the FAQ cleared it up and I felt like I learned something as it wasn't obvious on the first look.
hooby 2y ago
So, there was this one question "Can every map be colored with just 4 colors?"... And there I sit, knowing that every map of CONTIGUOUS territories can be colored with 4 colors - but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough... So I pick the answer "NO". > you are wrong!!!!! every map can be colored with 4 colors! it has been proven!!!!!
- N0b8ez 2y ago
  >but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough... Can you give an example of one that can't be colored with 4 colors?
  - hooby 2y ago
    They all can be colored in 4 colors - if you don't care about giving the enclave the same color as the parent country. If you insist giving those little islands the same color as the country they belong to, then things get difficult. That's not always doable in 4 colors. see: https://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/4CT_Inadequacy_Example.svg/300px-4CT_Inadequacy_Example.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/4C...
yochem 2y ago
You mention that this problem has overlap with training neural nets. Could you link some further reading for this? :)
ceva 2y ago
Would be nice to Introduce another continent like Europe :) it looks really nice tho!
segfaltnh 2y ago
Well done, enjoyed this a lot.
gexaha 2y ago
Nice puzzle, congrats! I also like this part of maths, and there's a related concept of Snark graphs. https://en.wikipedia.org/wiki/Snark_(graph_theory) https://en.wikipedia.org/wiki/Snark_(graph_theory) First is that "One of the equivalent forms of the four color theorem is that every snark is a non-planar graph". Second, is as strengthened form of the four color theorem: "every snark has the Petersen graph as a minor", which is kind of proven (already 25 years ago), but still lacks 1 paper: https://thomas.math.gatech.edu/FC/generalize.html https://thomas.math.gatech.edu/FC/generalize.html https://math.stackexchange.com/questions/3692582/what-is-the-current-status-of-the-snark-theorem https://math.stackexchange.com/questions/3692582/what-is-the... And another related concept is of nowhere-zero flows, and even more stronger conjecture that "every bridgeless graph with no Petersen minor has a nowhere zero 4-flow". https://en.wikipedia.org/wiki/Nowhere-zero_flow https://en.wikipedia.org/wiki/Nowhere-zero_flow
AlexDragusin 2y ago
In the same vein: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
gsuuon 2y ago
This 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?
riffraff 2y ago
I 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.
williamDafoe 2y ago
I 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 https://www.cs.princeton.edu/people/profile/appel
Timwi 2y ago
It showed a complicated map and asked me if it was 3-colorable. Then it said it can convince me that it's 3-colorable without revealing the solution. But then it demonstrated this proof on a super simple map that we already knew to be 2-colorable, not the complicated one I was told to assess.
xg15 2y ago
(spoiler alert) Thanks a lot for the game. I really enjoyed it and it got me thinking about the coloring problem. I wonder if it could be interesting to also add some bits of the corresponding graph problem into the game. This might be able to make the coloring problem a bit less "mysterious", but not less interesting. Some shower thoughts: It's easy to see that if you start with an arbitrary "country map", you can easily convert it into a graph with the same coloring properties: Just draw a node into the center of each region, then, if two regions have a shared border somewhere, connect their nodes with an edge. The coloring problem is now the task of coloring all the nodes, so that no two nodes that are directly connected with an edge have the same color. The solution to that task is also easy to see: If you have n nodes where each nodes has edges to all the other nodes, then you need n colors. The more "missing" edges you have in the graph, the less colors you can get away with. (The location of the missing edges is important though: As soon as there a group of n fully connected nodes, you need at least n colors, no matter how many additional nodes and missing edges there are) Does that mean you can construct graphs that need 5 colors or more? Yes, just make the desired number of nodes and draw edges between all of them. So then, where does the limit of 4 come from? There it gets interesting: Because not every graph con be converted back into a country map: Only planar graphs, i.e. graphs where no edges cross if you lie it out on a plane have a corresponding country map, otherwise you'll get an "impossible geometry". So the coloring problem "really" shows that you can have at most 4 fully connected nodes in a planar graph - if you have graphs with more connections, you will always have at least two edges crossing, no matter how you arrange the nodes and edges on the plane. This might also explain why it is so hard to produce good visualisations for arbitrary graphs. An interesting question might be how the planar criterion works for other geometries, e.g. if you lay out the graph on a sphere or torus or multi-hole torus. Another aside: In real life, states are not always continous regions on a map. There are a lot of nations that have enclaves, oversea territories or for other reasons consist of more than one geographical region. So in theory, a "map of nation states" instead of a "map of regions" could represent a nonplanar graph and could have a coloring number greater than 4. I'm not sure if there is actually such a situation anywhere on the globe though.

1054 points by MCSP 2y ago

stop50 2y ago

Very nice. I had no problems playing it.

baruchel 2y ago

Hi, my two cents; you claim "Although mathematicians believe their proof is correct, it is too complex to verify without computer assistance", but I'm not sure "believe" is the correct verb since the proof has been formally verified (see for instance https://github.com/coq-community/fourcolor https://github.com/coq-community/fourcolor for a formal verification in Coq). I understand that you want to emphasize the fact that no human can understand the proof with a full overview, but I wonder whether the current sentence will not make people think mathematicians are not perfectly sure of the proof.

MCSP 2y ago
Good point! I'll try to think about a better way to phrase this (happy to hear suggestions)
- lcnPylGDnU4H9OF 2y ago
  "Although mathematicians have been able to prove this, the proof is too complex to verify without computer assistance." Or some such.
- valenterry 2y ago
  Nah, actually I agree with you. What counts as believe and what as fact is rather abitrary. Is 2+2=4 a fact? Is global warming a fact? What about man-made global warming? Ask 100 people whether something is a fact or a believe. To top that up, it's fact that there have been "proves" that were wrong (or maybe that's just my believe? :^]) even for a long time. Hence, I think we can say that there are 4 options for a theorem: 1) Some mathematician believes the theorem is correct (but can't prove it) 2) Some mathematician believes the theorem is incorrect (but can't prove it) 3) Some mathematician believes the proof of a theorem is correct 4) Some mathematician believes the proof of a theorem is incorrect Proving that a proof is correct is kind of meaningless. At that point it's all believe anyways.
  - konschubert 2y ago
    ^ Exhibit A why using "believe" is a bad choice of words. Mathematical poofs are either correct or false. There is no middle ground.
    - karmakurtisaani 2y ago
      Well.. there is. Middle ground being a very complex, but somehow convincing argument that no one can reasonably check. There was one of these cases in number theory some years ago, can't remember the details. Proofs can be only true or false, but accepting proofs is in the end a social process.

AndrewOMartin 2y ago

Can you add to the FAQ at the end an answer to the question "How do I know you're not just showing me two random colors?"? It's possible this is already addressed and I missed it.

hcs 2y ago
You do need to prove that you have assigned the colors before the choice of what to reveal is made, I think. Physically this is guaranteed by the presence of the colors under the post-its (barring dynamic e-paper or something). I'm not sure how it works with the example of the primes, I lost the link to the later pages of the game so I can't read over it again, but I think it's guaranteed because there's just one number encoding all the assignments and you just get to unlock a single pair with the key given in response to your choice. There's an assumption that there isn't enough information in the key to fake any response, it has to reveal something that was already in there.
- MCSP 2y ago
  You're exactly right. The definition via primes ensures there is only one color consistent with each number (formally, this is called a perfectly binding commitment scheme). Also, here's the link if you want to go back: rahulilango.com/coloring/zk
  - hcs 2y ago
    Thanks! And this is a great exercise, thanks for sharing it.
MCSP 2y ago
Thanks for the feedback! As hcs suggests, this is part of the physical post-it assumption. I'll think about ways to make it more clear -- adding an FAQ is a good idea :)
- gowld 2y ago
  All that's missing is more info in the answer to this question: > Question: How do you do this in the digital world, without post-it notes? Answer: "When I give you a map labelled with numbers for each region, the numbers are the "post-it notes", "covering" the list of factors (which encodes a color). You can't see the primes factors inside them, because, even though generating an multiplying large primes is easy for computers, factoring numbers is much, much harder.)" I think if, when the player checks "reply the demo, with numbers", you move the game down to where the prime number discussion is, it's easier to understand. Also, note that the digital versionis better than the physical version. In the physical version, you can't stop me from removing extra notes. (A better example might be to put each color in a locked box, each with a different lock/key.) In the digital version, the factor lists are the "keys".

zem 2y ago

great work!

chromy 2y ago

The Republic of Ireland (the west most region on the first page) isn't part of the United Kingdom. The term for the group of regions shown is 'the British Isles'. See https://qntm.org/uk https://qntm.org/uk While it seems like a trivial distinction the whole thing is somewhat fraught (https://en.wikipedia.org/wiki/The_Troubles https://en.wikipedia.org/wiki/The_Troubles).

MCSP 2y ago
Whoops! Switched to "British Isles" -- update should be percolating now
- darajava 2y ago
  I prefer the term “Atlantic Archipelago”. The “British Isles” encompassing a non-british sovereign state is contentious. Other good terms are “Britain and Ireland” or the “British-Irish isles”
  - MCSP 2y ago
    Now switched to "Britain + Ireland," thanks!
  - card_zero 2y ago
    Yeah, "Britain and Ireland" is straightforward. "Atlantic Archipelago" makes me think you mean the Canary Islands.
  - bumbledraven 2y ago
    "British Isles" is the commonly-accepted term, and it doesn't seem to be particularly contentious outside of Ireland. As https://en.wikipedia.org/wiki/British_Isles https://en.wikipedia.org/wiki/British_Isles notes: > As a term, "British Isles" is a geographical name and not a political unit.
romwell 2y ago
It's about as "trivial" a distinction as considering Crimea (or the entirety of Ukraine, for that matter) a part of Russia. Many, many people have died for this triviality. "Somewhat fraught" is a very interesting choice of words, but then again, so is "The Troubles" (when the subject matter is decades of bombings and killings).

noodlesUK 2y ago

Just FYI the “map of the UK” includes the Republic of Ireland, which is very much not part of the UK. There’s not a 100% great term for the collective unit of land. Generally people go with “UK & Ireland” if they’re trying to be sensitive.

MCSP 2y ago
Thanks for pointing this out! Switched to "British Isles" -- update should be percolating now
- messe 2y ago
  The British Isles is also a somewhat controversial term with colonial implications, and it's not used by the government of Ireland[1]. "Britain and Ireland" would be a safer bet, as the map doesn't include any other islands. https://en.wikipedia.org/wiki/Names_of_the_British_Isles https://en.wikipedia.org/wiki/Names_of_the_British_Isles
  - russellbeattie 2y ago
    Diving into Wikipedia, apparently variations of the name "Britain" have been in use since 30BC, and referred to the big island, with the smaller islands grouped with it, e.g. British Isles. The Irish may not like it, but they're fighting against two millenia of history.
    - messe 2y ago
      And it's use in English only comes from the mid 16th and 17th centuries, right around the time that much of Ireland was being colonized by the British. Frankly, I find the term offensive, and think it should be discouraged in much the same way people have shifted away from "the Ukraine" to simply Ukraine.
      - returningfory2 2y ago
        Why is "the Ukraine" bad?

joshlk 2y ago

That was fun. On another note, I dislike how “Zero-Knowledge Proofs” are called proofs. It’s not a proof. You iteratively increase your belief that the result is true, like in experimentation, but that’s not a proof.

tyilo 2y ago
If someone has signed something cryptographically, wouldn't you say that the signature was a proof of someone with the private key signing it? (Even though it is possible to construct a valid signature without the private key - you just have to be very very very lucky) I guess you also don't like the name Proof of Work.
hcs 2y ago
It might help to think of the sense of "proof" that's synonymous with "trial", rather than a specific formal math sense of proving a theorem from axioms by formal transformations.
fragmede 2y ago
zero knowledge corroboration isn't the same thing as a zero knowledge proof. If the provided evidence isn't enough, then you keep iterating until it's proven.

sakras 2y ago

This was fun, I went into this thinking "Ha I already know this theorem" but came out learning something about zero knowledge proofs!

js98 2y ago

Nice work! I spent a bit too much time creating a map with 5 colors… ;)

franciscop 2y ago

[spoiler alert] I knew that 4 colours sufficed for any arbitrary map from back in the day when I learned this, but still I found it VERY rewarding by attempting to draw a map that needed 5 colors, and how intuitive this demo was for getting a "feel" for a thing that I knew only theoretically! Like I needed an impossible geometry to fit, either an area that stretched to a zero-width path (which would becomes a point, and thus 2 areas, so doesn't fit) or some other "impossible" geometry. Loved it, congrats on a really well executed idea!

genewitch 2y ago
there has to be a layman's explanation. I knew the easiest way to get four colors was to put a split square inside another split square "donut", but the reason you can't force 5 colors is that word "inside". There has to be a nice, tidy "verbal proof" that no matter what, one or more colors will be "trapped" inside at most 3 other colors.
- waterproof 2y ago
  You would think. The easier, five-color theorem proof fits in a few paragraphs but the four-color theorem really resists a simple explanation. Even the simplified 1990s version of the proof (which came ~20 years after the original proof and 100 years after the 5CT proof) required enumeration of hundreds of individual cases. https://en.m.wikipedia.org/wiki/Four_color_theorem https://en.m.wikipedia.org/wiki/Four_color_theorem
8organicbits 2y ago
It was really enjoyable to try. I got an optimal 4-color map on the first try, so I was over confident. My approach was something like: put a bunch of the 4-color maps next to a long Chile-like thing. When that didn't work I added borders until my device couldn't render it any longer. Very very fun.

OmarShehata 2y ago

I love this! I'd for this to be a more typical experience in math class (I bought Paul Lockhart's "measurements" but gave up because I felt like I needed a sandbox to play with and little hints. Like, I don't want to be told the answer but I want to know feedback exactly like this demo. Very simple: "this is not right" or "this is right, but can be done with fewer") (My dream is to have a little game jam where we make interactive versions of these concepts as puzzle)

dunefox 2y ago

In Android using Firefox the button to go to the next challenge doesn't seem to work.

MCSP 2y ago
Will look into this. Did it happen on the first page (map of Britain + Ireland)?
- dunefox 2y ago
  Yes.

mbivert 2y ago

Enjoyed the tutorial very much, thanks. As a suggestion, I would dearly enjoy a follow-up rigorously connecting those visual, intuitive ideas to actual mathematics.

soneca 2y ago

Great job! I enjoyed going through the steps. The final though seemed like a huge leap for me, who don’t know anything about those math mysteries (which I assume is your target audience). First I was curious to learn how is the fast way to understand that 1, 2, or 4 colors suffice. And why finding out such a way for 3 is so hard. The zero-knowledge proof demonstration felt like “changing the subject”. Probably I missed the connection there.

gowld 2y ago
ZKP is the subject. The maps part is a helper lemma. It would help to clarify that in the beginning. The game is a bit of a shaggy dog tail. It would be good to give an outline and progress bar at the start (without spoilers)

windowshopping 2y ago

I went in skeptical and got completely hooked. Well played. Very neat thing to build. Wish more math were taught creatively like this.

deleted 2y ago

[deleted]

zamadatix 2y ago

Loved the interactions and flow overall but I'm a bit lost on the zero knowledge proof example. I'm familiar with the concept but I don't follow how the example is one. E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof? If I pick a hundred numbers it'll look like I just proved some black box function which happens to be Sin[n] + 0.999999999999 is always positive even though I'd be able to clearly show it negative with the knowledge of the function. It feels like something that got detached from the things that make it work during simplification. Or it could be that I just have a misunderstanding/oversight in the zero knowledge proof :). In an unrelated note: I colored the larger graph and it didn't even play along!

esquivalience 2y ago
I think the answer is that each time you reveal the colours, you observe that they are within the set of three colours illustrated at the beginning of the proof. Whichever you reveal, you never find a fourth colour. This confused me at first.
- zamadatix 2y ago
  For anyone confused by this response I had edited my comment after reading https://news.ycombinator.com/item?id=40740557 https://news.ycombinator.com/item?id=40740557 but before equivalence had hit reply and now their reply is left hanging. Sorry esquivalience! To summarize the linked answer on trusting the second dot isn't just randomly assigned: keep the context as physical post-its. Barring something like a matter bending psychic you'd be able to tell the dot under the second post-it was swapped as you made your pick. That still leaves how to rely on chance of picks for a proof though.
  - romwell 2y ago
    It's the same thing as limits in spirit. It's not that the chances of lying are small, it's that they can be made arbitrarily small. Let's say my standards of "proof" are that there's only 0.1% chance that you're cheating. We play that game several times, and I'm satisfied. Next comes someone else whose standard is 0.001% chance of cheating. They simply play the game a few more times, and they're satisfied too. If they change their mind and decide that only 0.0000001% will make them happy, they simply tack on a few more rounds. The key here is that the probability that you can cheat for arbitrarily long is exactly zero — for the same reason that Zeno's paradox is resolvable (and limit of 1, 1/2, 1/4, 1/8, 1/16, ... is exactly zero, and not just a very small number).

sverona 2y ago

This is cute. You should flag the "I claim that three colors suffice" map if the user actually 3-colors it. At least, I think I did...

vavooom 2y ago

that was fun :)

SilasX 2y ago

Uh, when you draw the map that requires three colors, I couldn't figure out how to submit it to at least be told it's not good enough. Or if it automatically accepts for a 3-min [1], then it was too hard to make sure that the boundary reached the edge of the screen. (I thought I successfully drew five regions around a point.) [1] sorry, 3-chromatic or whatever

MCSP 2y ago
Hmm, my guess is you're trying to use the box's borders as lines (they don't count, only the lines you draw count). Let me know if that's not the issue. Also, I'll think about ways to make this more clear!
- JoshTriplett 2y ago
  You could automatically "zoom out" what they draw if they get too close to the border. Alternatively, you could automatically "close" figures after they have at least three points, and give a hint of a handle that allows dragging a new point out of the middle of an existing side.
- SilasX 2y ago
  Ah okay -- the second one had a map with the same shape as the border, which I think made me mentally lump the map's border with the box's borders and invalidate the claim that it's looking at the box's borders as part of the map. I also assumed you wouldn't possibly expect someone to have to explicitly draw all their borders when they can piggyback off the box. Entirely my mistake because I was kind of ignoring everything you said lol

gcyjjkjg 2y ago

[flagged]

trirpi 2y ago

There seems to be an error in the backtracking algorithm. E.g.: https://imgur.com/a/1miv1AK https://imgur.com/a/1miv1AK

MCSP 2y ago
Good catch -- I'll look into this!

andrei-akopian 2y ago

1. Nice site, bookmarked to give it to people. 2. You are a very bad and annoying person ;)

dcastm 2y ago

Thanks for sharing. This was instructive and fun in equal parts

gkoberger 2y ago

This was one of the cooler teaching examples I've ever played with... awesome job! Appreciate the warning that the 5 color map is "very difficult". It felt easy enough, and I would have spent an hour on it! This was so much cooler than just being told that 4 colors is enough for every map – this one will stick with me. It would be wonderful if schools taught a bit more like this – I almost felt like I discovered it myself!

ModernMech 2y ago

It's very fun! Only thing I would change is to make it so clicking on the picture doesn't trigger a text select, it was hard to play because a context menu kept popping up every time I changed map color.

neuron-enix 2y ago

There goes my 2hrs of sleep, trying to solve feeling that I was close to solving, only to see myself draw shapes that I have never seen or imagined in my life. Well in the end it was fun, but the warning is very misleading at least from a game perspective. I have played games at the same level but it certainly wasnt this hard, haha... But hey, saying that it was difficult, was the only thing that kept me going for 2hrs, only to be annoyed and have a face palm moment after seeing the answer. Nonetheless it's good post

umvi 2y ago

Seems easy to intuitively prove that 5 colors is impossible. In order to need 5 colors, you'd need to construct a graph with 5 nodes where each of the nodes connects to all other nodes, but without any edges crossing: https://imgur.com/U52SFSi https://imgur.com/U52SFSi You can just tell after playing around with the graph that it's impossible to move the nodes around on a 2d plane without an edge crossing; you need a 3rd dimension.

SamBam 2y ago
I've always found what happens in the third dimension weird. A 0-dimensional space needs up to: 1 color. A 1-dimensional space needs up to: 2 colors. A 2-dimensional space needs up to: 4 colors. A 3-dimensional space needs up to: ∞ colors. I can easily picture why a 3D space has no limit to the number of colors (personally I always imagine color blocks hanging in space connected to every other color block by bendable wires), but I don't quite understand why the pattern is that way.
- Halfwhit 2y ago
  Imagine the colours of a hypercube in 4-dimensional space!
  - genewitch 2y ago
    A mantis shrimp told me, quote, "it's alright, i guess, if you're in to that sort of thing"
tomsmeding 2y ago
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 map you can draw that has five regions all bordering each other. This is not too difficult to prove, actually. Proving that 4 colours is enough is a whole different league! [1]: https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory) [2]: https://www.rahulilango.com/coloring/wus https://www.rahulilango.com/coloring/wus

teddarific 2y ago

Wow, this was a lot of fun. 3 was a lot harder than expected — a great exercise for anyone honestly. I'm a math nerd so this was cool visualized!

genewitch 2y ago
the easiest 3 is an equilateral triangle split in half with any shape containing it - for 4 split the container perpendicular to the split in the triangle. |-/|\-|

bgoated01 2y ago

I 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: https://mathworld.wolfram.com/TorusColoring.html https://mathworld.wolfram.com/TorusColoring.html Thanks for leading us down this mathematical rabbit hole today.

enlyth 2y ago
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, you'd most likely be satisfied.
- Aardwolf 2y ago
  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.
pwmtr 2y ago
This video helped me a lot to understand the basics of zero knowledge proof: https://www.youtube.com/watch?v=fOGdb1CTu5c https://www.youtube.com/watch?v=fOGdb1CTu5c
- wonger_ 2y ago
  Great video, thanks. My takeaways: - The physical demonstrations at 1:16 and 3:48 were helpful - thinking of proofs as between a prover and a verifier, not as classical deterministic proofs - insight into the name "zero-knowledge", as in "you can already predict the answer, so you're not gaining any knowledge from that interaction"

your_friend 2y ago

How cool! I didn’t expect it will end up with ZK proofs that I was curious about for a long time. (After reading it I still don’t quite get the details of how they are working tho)

jostylr 2y ago

That was enjoyable. You could submit this to the summer of math exposition: https://some.3b1b.co/ https://some.3b1b.co/

nirolo 2y ago

You might want to get into touch with some museums on science topics to see if they are up to show it. I live in Germany at the moment and know of at least two MINT focused museums that let visitors engage a lot with their (sometimes digital) exhibits and this here checks all the boxes to make a great exhibit. Very well done, I'll try to see if my children will enjoy that already too.

wrsh07 2y ago
Absolutely!! Talk to MoMath in NYC too I'm happy to find a contact there if you want

JohnMakin 2y ago

This gave me PTSD flashbacks to an extremely difficult computational geometry course I took once, but this is cool.

personjerry 2y ago

How does the zero-knowledge solution make sense? Can't you just cheat and show me two random different colors whenever I click two post-its?

namjh 2y ago
In reality, the entire map should be sent first to the verifier (with colors hid behind the post-it) so if it was a bogus randomly colored map, you may find two adjacent points having same color if you try extremely many(think hundreds or thousands in the website's case) times. If you sufficiently try many times and fail to find the adjacent points, you will convince that the prover have the map which is correctly 3-colored. Note that the entire map is sent again, shuffled its color each time after you choose the two points.

aib 2y ago

Ahh, very nice. It was fun to rediscover/relearn some of these things through this game. Very nice wording on the 5-color challenge! I think it was the perfect balance. One thing I was missing was the ability to move the points already on canvas. I assume you already considered, though. (As well as right-click-to-remove?)

NegativeLatency 2y ago

Something about 4 colors makes sense to me intuitively because you've got 0 or 1 color for each of the two cartesian axes (2 * 2 = 4). Not sure there's anything behind that though.

zaik 2y ago
Well it does not generalize into 3 dimensions: https://math.stackexchange.com/a/4767802 https://math.stackexchange.com/a/4767802

passwordoops 2y ago

So addictive! And it's great how you tie it in to the greater mathematical concept. I'm loving it!!

tzs 2y ago

> Step 1. I put a <purple circle>, <blue circle>, or <red circle> color dot on each region, but hide it under a post-it > Step 2. You click any two bordering regions, and I pull off their post-its > Step 3. You check that the revealed colors are different I would add explicitly in step 1 that you tell me what 3 colors you used, and in step 3 that I check that the revealed colors are different from each other and are both from that set of 3. Similar in the explanation of why this should convince me.

poopcat 2y ago

Had a great time with this! Great break to get my mental gears moving

sn41 2y ago

Just a quick note: Rahul Ilango is a phenomenal theoretical CS researcher who has made great progress towards understanding the "Minimum Circuit Size Problem" [MCSP], long believed to be, but not yet proven, NP hard. Needless to add, "the username checks out".

MrZander 2y ago

I know that it is impossible, but it was fun to try to make a 5 color map work. That being said, is this a bug? https://imgur.com/a/zbkYg9j https://imgur.com/a/zbkYg9j I can't seem to wrap my head around why this isn't 3 colors.

deleted 2y ago
[deleted]

barbariangrunge 2y ago

This is lovely. The Ux isn’t my favourite when it’s time to draw but it’s pretty great besides that

gpnt 2y ago

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

genewitch 2y ago
well, i knew there was no answer and i still tried for 15 minutes. I think that's the point!
zild3d 2y ago
i appreciate the intention to let you struggle with it on your own for a bit, but not go crazy. a better experience might be having the warning reveal more after a few attempts, but I don't mind starting with a "warning it's surprisingly tricky"
kzrdude 2y ago
There'sa tidbit for you later if you continue (The "do you trust me")

next_xibalba 2y ago

Although I still didn't fully understand the relation between zero knowledge proofs and the post-it example, this game is just kind of fun in its own right!

namjh 2y ago

Great work! I really enjoyed the interactivity. Actually I already was aware of the concept of zero-knowledge proof from the wonderful article by ZCash(which is a privacy-oriented cryptocurrency) core developer Matthew Green, worth to check it out: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... My two cents of the ZKP illustration is that directly using hashes are more likely to convince "computer-friendly" people to introduce the commitment scheme.

pontifier 2y ago
I triggered a coloring bug as well during that stage.

Guvante 2y ago

Fun fact, one of the reasons the four color problem is hard to prove is there isn't an algorithm that can color a map in four colors. Well beyond effectively trivial ones where you try over and over again. But the algorithm for coloring with five is pretty easy (relatively speaking still involves fun graph theory)

ehershey 2y ago

Wow what a fun little interesting time. My wife and I made it to the end on mobile!

hgyjnbdet 2y ago

Spent way too long on the five colour thing refusing to skip. You always have to surround one colour which then protects it. You simply can't touch four colours at once. Then I skipped it and found out it was impossible, FML.

PUSH_AX 2y ago

Thanks for taking me on that journey!

snthpy 2y ago

Nice! I knew the 4-colour theorem but the zero knowledge proof illustration was great. I didn't get it initially but the FAQ cleared it up and I felt like I learned something as it wasn't obvious on the first look.

hooby 2y ago

So, there was this one question "Can every map be colored with just 4 colors?"... And there I sit, knowing that every map of CONTIGUOUS territories can be colored with 4 colors - but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough... So I pick the answer "NO". > you are wrong!!!!! every map can be colored with 4 colors! it has been proven!!!!!

N0b8ez 2y ago
>but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough... Can you give an example of one that can't be colored with 4 colors?
- hooby 2y ago
  They all can be colored in 4 colors - if you don't care about giving the enclave the same color as the parent country. If you insist giving those little islands the same color as the country they belong to, then things get difficult. That's not always doable in 4 colors. see: https://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/4CT_Inadequacy_Example.svg/300px-4CT_Inadequacy_Example.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/4C...

yochem 2y ago

You mention that this problem has overlap with training neural nets. Could you link some further reading for this? :)

ceva 2y ago

Would be nice to Introduce another continent like Europe :) it looks really nice tho!

segfaltnh 2y ago

Well done, enjoyed this a lot.

gexaha 2y ago

Nice puzzle, congrats! I also like this part of maths, and there's a related concept of Snark graphs. https://en.wikipedia.org/wiki/Snark_(graph_theory) https://en.wikipedia.org/wiki/Snark_(graph_theory) First is that "One of the equivalent forms of the four color theorem is that every snark is a non-planar graph". Second, is as strengthened form of the four color theorem: "every snark has the Petersen graph as a minor", which is kind of proven (already 25 years ago), but still lacks 1 paper: https://thomas.math.gatech.edu/FC/generalize.html https://thomas.math.gatech.edu/FC/generalize.html https://math.stackexchange.com/questions/3692582/what-is-the-current-status-of-the-snark-theorem https://math.stackexchange.com/questions/3692582/what-is-the... And another related concept is of nowhere-zero flows, and even more stronger conjecture that "every bridgeless graph with no Petersen minor has a nowhere zero 4-flow". https://en.wikipedia.org/wiki/Nowhere-zero_flow https://en.wikipedia.org/wiki/Nowhere-zero_flow

AlexDragusin 2y ago

In the same vein: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

gsuuon 2y ago

This 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?

riffraff 2y ago

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

williamDafoe 2y ago

I 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 https://www.cs.princeton.edu/people/profile/appel

Timwi 2y ago

It showed a complicated map and asked me if it was 3-colorable. Then it said it can convince me that it's 3-colorable without revealing the solution. But then it demonstrated this proof on a super simple map that we already knew to be 2-colorable, not the complicated one I was told to assess.

xg15 2y ago

(spoiler alert) Thanks a lot for the game. I really enjoyed it and it got me thinking about the coloring problem. I wonder if it could be interesting to also add some bits of the corresponding graph problem into the game. This might be able to make the coloring problem a bit less "mysterious", but not less interesting. Some shower thoughts: It's easy to see that if you start with an arbitrary "country map", you can easily convert it into a graph with the same coloring properties: Just draw a node into the center of each region, then, if two regions have a shared border somewhere, connect their nodes with an edge. The coloring problem is now the task of coloring all the nodes, so that no two nodes that are directly connected with an edge have the same color. The solution to that task is also easy to see: If you have n nodes where each nodes has edges to all the other nodes, then you need n colors. The more "missing" edges you have in the graph, the less colors you can get away with. (The location of the missing edges is important though: As soon as there a group of n fully connected nodes, you need at least n colors, no matter how many additional nodes and missing edges there are) Does that mean you can construct graphs that need 5 colors or more? Yes, just make the desired number of nodes and draw edges between all of them. So then, where does the limit of 4 come from? There it gets interesting: Because not every graph con be converted back into a country map: Only planar graphs, i.e. graphs where no edges cross if you lie it out on a plane have a corresponding country map, otherwise you'll get an "impossible geometry". So the coloring problem "really" shows that you can have at most 4 fully connected nodes in a planar graph - if you have graphs with more connections, you will always have at least two edges crossing, no matter how you arrange the nodes and edges on the plane. This might also explain why it is so hard to produce good visualisations for arbitrary graphs. An interesting question might be how the planar criterion works for other geometries, e.g. if you lay out the graph on a sphere or torus or multi-hole torus. Another aside: In real life, states are not always continous regions on a map. There are a lot of nations that have enclaves, oversea territories or for other reasons consist of more than one geographical region. So in theory, a "map of nation states" instead of a "map of regions" could represent a nonplanar graph and could have a coloring number greater than 4. I'm not sure if there is actually such a situation anywhere on the globe though.