[HN Gopher] Show HN: I made a puzzle game that gently introduces...
___________________________________________________________________
Show HN: I made a puzzle game that gently introduces my favorite
math mysteries
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"
Author : MCSP
Score : 478 points
Date : 2024-06-20 15:45 UTC (7 hours ago)
(HTM) web link (www.rahulilango.com)
(TXT) w3m dump (www.rahulilango.com)
| stop50 wrote:
| Very nice. I had no problems playing it.
| baruchel wrote:
| 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 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 wrote:
| Good point! I'll try to think about a better way to phrase this
| (happy to hear suggestions)
| lcnPylGDnU4H9OF wrote:
| "Although mathematicians have been able to prove this, the
| proof is too complex to verify without computer assistance."
|
| Or some such.
| valenterry wrote:
| 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 wrote:
| ^ Exhibit A why using "believe" is a bad choice of words.
|
| Mathematical poofs are either correct or false. There is no
| middle ground.
| karmakurtisaani wrote:
| 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.
| unclad5968 wrote:
| A convincing argument that cannot be checked is not a
| proof. If you want to extend the definition of proofs
| you're welcome to do that, but for academic mathematics
| the meaning of proof doesn't contain a middle ground.
| valenterry wrote:
| Why would it not be a proof?
|
| What is your criteria of "can be checked then"? If a
| proof for "sqrt(2) is not a rational number" can't be
| checked by a 5yo, it's still a proof no?
| nhatcher wrote:
| A couple come to mind
|
| * The proof of the classification of simple groups[0]
|
| * The work on topological four manifolds by M. Freedman
| [1]
|
| [0]: https://en.m.wikipedia.org/wiki/Classification_of_fi
| nite_sim...
|
| [1]: https://news.ycombinator.com/item?id=28471159
| konschubert wrote:
| > Proofs can be only true or false
|
| Yes.
|
| The fact that we don't know the truth doesn't mean there
| isn't one.
| blowski wrote:
| Brilliant episode of the BBC's In Our Time that goes down
| this rabbit hole. https://www.bbc.co.uk/programmes/b04v59gz
| ifdefdebug wrote:
| s/believe/know
| gergo_barany wrote:
| That Coq proof is not "without computer assistance". No Coq
| proof is, as Coq is literally an "assistant" that runs on a
| computer.
|
| And those many jobXtoY.v and taskXtoY.v files sure look like
| they also do the same as the Appel and Haken proof, namely
| enumerate lots and lots of cases that are then machine-checked.
| So I don't think the computerized Coq proof is really
| qualitatively different from other computerized proofs that
| enumerate so many cases that a manual check would be
| impractical.
| TheNewAndy wrote:
| I would consider a proof to be a "repeatable argument". One you
| could show to someone and expect them to be convinced by it. I
| think it is a defensible viewpoint that a proof in coq is not
| 100% convincing. If you think otherwise, then how can you
| reconcile the existence of falso (a coq verified proof of
| "false")?
|
| https://github.com/clarus/falso
|
| Proof and belief I think are pretty strongly intertwined, but
| I'm not going to pretend to have a particularly rigorous
| philosophy on the matter. Similarly, when the proof of Fermat's
| last theorem was published, I don't know if I should consider
| that to be a proof because it is well beyond my comprehension.
| I have no reason to question it, but should I consider it a
| proof? I know that people smarter than me (e.g. Wiles) thought
| the original version of it was a proof, but it had a subtle
| error in it which required a fix. While I haven't looked at the
| proof and revision, I would be surprised if I could look at the
| two versions as labelled and tell which one is the correct
| version.
| AndrewOMartin wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Thanks! And this is a great exercise, thanks for sharing
| it.
| MCSP wrote:
| 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 wrote:
| 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 wrote:
| great work!
| chromy wrote:
| 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
| While it seems like a trivial distinction the whole thing is
| somewhat fraught (https://en.wikipedia.org/wiki/The_Troubles).
| MCSP wrote:
| Whoops! Switched to "British Isles" -- update should be
| percolating now
| darajava wrote:
| 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 wrote:
| Now switched to "Britain + Ireland," thanks!
| card_zero wrote:
| Yeah, "Britain and Ireland" is straightforward. "Atlantic
| Archipelago" makes me think you mean the Canary Islands.
| romwell wrote:
| 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).
| djeastm wrote:
| Naming things is hard
| noodlesUK wrote:
| 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.
| HeatrayEnjoyer wrote:
| 'British Isles' identify the geographic islands.
| gilleain wrote:
| If anyone is unsure, please refer to this simple diagram:
|
| https://en.wikipedia.org/wiki/Terminology_of_the_British_Isl.
| ..
|
| Obvious, really! :)
| messe wrote:
| It's not a popular term in Ireland. Britain and Ireland is
| often preferred, and has less colonial implications.
| MCSP wrote:
| Thanks for pointing this out! Switched to "British Isles" --
| update should be percolating now
| messe wrote:
| 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
| russellbeattie wrote:
| 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 wrote:
| 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 wrote:
| Why is "the Ukraine" bad?
| JoshTriplett wrote:
| https://en.wikipedia.org/wiki/Ukraine#Etymology_and_ortho
| gra...
|
| It's the difference between a descriptive name for a
| region and a proper noun for a country.
| returningfory2 wrote:
| Sure, but more recent history should have a higher
| weight. It is reasonable that our names for things
| reflect recent history and current affairs more than
| ancient history.
|
| Two thousand years ago Britain and Ireland were
| ethnically and linguistically pretty similar (I believe).
| Since then they have diverged in many ways - most
| significantly during the Reformation period when people
| in Britain largely left Catholicism, but people in
| Ireland remained Catholic. Changes like this and the
| legacy of colonialism this have ultimately resulted in
| Ireland having distinctly non-British identity. It is
| reasonable that our naming for things reflect this
| current state of affairs.
|
| As always, it useful to consider other examples to
| clarify the point. For example, by the same argument,
| should we deprecate the phrase "Latin America"? After
| all, Latin Europeans only arrived in the Americas 500
| years ago and the continent has had people for 10
| thousand years before that. Are people who include a
| European adjective in the name of this cultural area
| "fighting against ten millenia of history"?
| gowld wrote:
| Safest to just remove Ireland from the map. It's not needed
| for the demo.
| MCSP wrote:
| Switched to "Britain + Ireland"!
| sakras wrote:
| This was fun, I went into this thinking "Ha I already know this
| theorem" but came out learning something about zero knowledge
| proofs!
| js98 wrote:
| Nice work! I spent a bit too much time creating a map with 5
| colors... ;)
| joshlk wrote:
| 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 wrote:
| 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 wrote:
| 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.
| franciscop wrote:
| [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!
| OmarShehata wrote:
| 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 wrote:
| In Android using Firefox the button to go to the next challenge
| doesn't seem to work.
| MCSP wrote:
| Will look into this. Did it happen on the first page (map of
| Britain + Ireland)?
| dunefox wrote:
| Yes.
| mbivert wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| I went in skeptical and got completely hooked. Well played. Very
| neat thing to build. Wish more math were taught creatively like
| this.
| zamadatix wrote:
| 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 wrote:
| 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 wrote:
| For anyone confused by this response I had edited my comment
| after reading 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 wrote:
| 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).
| MCSP wrote:
| Very glad you enjoyed it!
|
| For the ZK example, the math behind it is this: if there are m
| bordering regions and I am lying, you have a 1/m chance of
| catching me each time. Thus after k repetitions the chance you
| haven't caught me is (1-1/m)^k \approx e^{-k/m} which is
| extremely small for k sufficiently larger than m.
|
| Now, you may rightfully say: hey that's still not a "proof,"
| you could still be lying! There are two responses to this:
|
| 1. The probability can be made _incredibly_ small, like smaller
| than the the chance, say, your computer got hit by a gamma ray
| burst that would flip bits from 0 to 1 (I really have no idea
| if this actually happens but people have said it to me).
|
| 2. It turns out it is mathematically impossible to get the zero
| knowledge property if you want true proofs (i.e., no
| probability of being wrong). So, there's a trade off: if you
| want zero knowledge, you have to accept some (small) failure
| probability
|
| P.S. Adding an easter egg for coloring the larger graph is on
| the todo list :)
| xg15 wrote:
| Yeah, I got tripped up by that formulation as well and it's
| actually something that annoys me with a lot of algorithms
| that have some properties proven in a limit: It's "easy" (or
| at least possible) to mathematically prove that in the limit
| of some variable, the property will hold: If you repeat the
| challenge increasingly often, the probability of being lied
| to will get arbitrarily close to zero; for sufficiently large
| input sizes, some algorithm runs in linear time; with
| sufficiently large amounts of training data and iterations,
| some prediction error will become arbitrarily small, etc etc.
|
| But none of that is telling you _how much_ is "sufficient",
| or even which order of magnitude we're talking about. If the
| quantity has a real life cost, this would result in enormous
| practical differences.
|
| (With the formula you have given for the ZK proof, we're at
| least one step further: You can start with the desired
| probability, e.g. the gamma ray burst und calculate the
| required minimum k from that - also, it's easy to see that
| the color problem lends itself well to such proofs because
| the probability of failure drops exponentially quickly with
| growing k, so the actual k you choose can be relatively
| small. But if all you have is a proof in the limit, that's
| not possible)
| ncruces wrote:
| The problem with doing this on a computer is getting us to
| believe you didn't just make up the colors as we tell you to
| reveal them (after being "dishonest" before).
| spencerflem wrote:
| That's the idea at the end about presenting the "sticky
| notes" as products of primes. Assuming you can't factor the
| primes yourself, you can be given the whole grid of those
| products and then interactively ask for the factors or a
| pair of them. The requestor can't give an alternative
| factorization (ie. make up a color on the spot) since each
| number can only be factored one possible way and its easy
| to verify.
| karmakaze wrote:
| I really liked this part that shows all the numbers up
| front, and none of them change during the reveal step.
|
| I think it would present better if introduced as "To show
| that there's no cheating going on behind the scenes, we
| will..."
| raincole wrote:
| I've got another problem about this zero knowledge proof. The
| digital version doesn't make a lot of sense to me. It depends
| on the fact we don't have a fast integer factorization
| algorithm. But integer factorization is not proven to be NP-
| complete, and 3-coloring is NP-complete.
|
| So isn't it possible that there is a polynomial time algorithm
| for integer factorization, but no polynominal time algorithm
| for 3-coloring, and therefore the "zero knowledge proof"
| actually reveals the answer?
| sverona wrote:
| 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 wrote:
| that was fun :)
| SilasX wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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
| trirpi wrote:
| There seems to be an error in the backtracking algorithm. E.g.:
| https://imgur.com/a/1miv1AK
| MCSP wrote:
| Good catch -- I'll look into this!
| andrei-akopian wrote:
| 1. Nice site, bookmarked to give it to people. 2. You are a very
| bad and annoying person ;)
| dylanjcastillo wrote:
| Thanks for sharing. This was instructive and fun in equal parts
| gkoberger wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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
|
| 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 wrote:
| 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 wrote:
| Imagine the colours of a hypercube in 4-dimensional space!
| tomsmeding wrote:
| 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)
|
| [2]: https://www.rahulilango.com/coloring/wus
| umvi wrote:
| "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 requiring 5 colours doesn't have to
| have a 5-clique exactly, but it needs something that is
| either a 5-clique or can be simplified to a 5-clique.
|
| I'm not a graph theory expert, so I'm assuming the complexity
| of the colors proof comes from the difficulty of being able
| to simplify complex graphs into simple atoms/cliques.
| teddarific wrote:
| 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!
| bgoated01 wrote:
| 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
|
| Thanks for leading us down this mathematical rabbit hole today.
| enlyth wrote:
| 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.
| pwmtr wrote:
| This video helped me a lot to understand the basics of zero
| knowledge proof: https://www.youtube.com/watch?v=fOGdb1CTu5c
| wonger_ wrote:
| 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"
| ianseyer wrote:
| The best analogy of zk-proofs I've heard is to suppose you have
| found Waldo in "Where's Waldo," and want to prove that you have
| done this without revealing the location.
|
| You could take a piece of paper (much larger than the
| picture/book), and cut out a waldo-shaped hole it and position
| the paper such that he is shown in the hole. Then, when you
| show it to the challenger, they know that you have found him
| without you revealing where he is.
| armchairhacker wrote:
| Here's my explanation of the ZKP:
|
| First, both you and the oracle know what the uncolored map
| looks like, and what the 3 colors are.
|
| Step 1: The oracle sends the _entire_ 3-colored map, but
| asymmetrically encrypted. So you can 't see the map, but the
| oracle can't "un-send" it. If no 3-coloration of the map
| exists, the oracle has to send you _something_ , and because
| you know what the map and colors look like, the only thing they
| can send is a map where some two adjacent regions have the same
| color.
|
| Steps 2&3: You randomly pick two adjacent regions and ask the
| oracle for their decryption keys, so you can see their colors.
| When you initially received the encrypted map, you could not
| know whether it had two same-colored adjacent regions. But, if
| you happen to randomly choose the same-colored regions, the
| oracle has no way of not telling you. If the oracle refuses to
| send the decryption keys for those regions, or sends ones that
| don't successfully decrypt, you'll know something is up, and
| can assume the regions are the same color. And the only keys
| that successfully decrypt the regions' colors, decrypt into
| their original colors; so the regions will only decrypt into
| different colors, if they were different colors in the
| encrypted map the oracle originally sent.
|
| To further illuminate: the "random pick after the map is
| received" ensures that the oracle must send you a map where all
| adjacent regions have different colors, even though you can't
| see all the colors yourself. Otherwise, the oracle can't
| guarantee that you won't ask for the two regions with different
| colors (because they sent the map before you randomly pick),
| and if you do ask for those regions, they can't respond in a
| way that re-assures you the colors are different (because the
| only way to do so is send keys that decrypt the regions into
| separate colors, and since they decrypt into the same color,
| such keys don't exist).
|
| Step 4: Repeat steps 1-3 an unbounded number of times. This is
| necessary because in a single iteration, there's a chance that
| the oracle sends a map with two adjacent same-colored regions,
| but you pick two different regions; so the map is
| un-3-colorable, but you don't find out. In fact, this is a very
| high chance if it's a large map and only a single pair of
| adjacent regions have the same color. But more iterations
| increase the probability that you do find out indefinitely;
| with enough iterations, the probability that _one_ of them you
| get lucky and select the same-colored region is 99.999...%.
|
| Also, each time you repeat steps 1-3, the oracle sends the map
| with a different coloration. Otherwise, you'd slowly reveal the
| colors to get the fully-colored map, so it wouldn't be a zero-
| knowledge proof (two colors in each of two maps with different
| colors doesn't give you any more information than two colors in
| one map, so even with unbounded iterations the original
| coloration isn't revealed). If the map isn't 3-colorable, the
| randomization doesn't affect the probability: when the oracle
| randomizes the map, they could choose an entirely different
| coloration and give two different adjacent regions the same
| color, but the probability of you randomly choosing those two
| regions stays the same, so the probability of "getting lucky"
| in one of enough iterations also stays the same, at 99.999...%.
| your_friend wrote:
| 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 wrote:
| That was enjoyable. You could submit this to the summer of math
| exposition: https://some.3b1b.co/
| nirolo wrote:
| 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 wrote:
| Absolutely!! Talk to MoMath in NYC too
|
| I'm happy to find a contact there if you want
| JohnMakin wrote:
| This gave me PTSD flashbacks to an extremely difficult
| computational geometry course I took once, but this is cool.
| personjerry wrote:
| 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?
| aib wrote:
| 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 wrote:
| 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.
| passwordoops wrote:
| So addictive! I'm loving it!!
| tzs wrote:
| > 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 wrote:
| Had a great time with this! Great break to get my mental gears
| moving
___________________________________________________________________
(page generated 2024-06-20 23:00 UTC)