Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

rahulilango.com

Post reply on HN
Print view View original

131–140 of 177 posts

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

#131

Post by nroets »

ianseyer wrote: post #91
bgoated01 wrote: post #76

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: h…

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…

But it's a simplification: One iteration is enough to detect lying.

In a real ZK proof the probability of the prover lying reduces after each iteration but never reached 0.

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

#133

Post by guyomes »

bgoated01 wrote: post #76

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: h…

And it turns out that on the Klein bottle, the maximum is 6 colors. More generally, this number depends directly on the number of holes of the surface [1].

[1]: https://en.wikipedia.org/wiki/Heawood_conjecture

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

#134

Post by dmurray »

raincole wrote: post #60
zamadatix wrote: post #29

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 fu…

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,…

I think you're right, and integer-factorization is often used in these examples as a process that is hard to do but easy to verify. There are plenty of other processes that could be substituted in, e.g. reversing SHA256 hashes, that would likely be even less tractable to the target audience.

However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and therefore no zero knowledge proofs exist.

Actually, that's not true either. It requires the definition that all polynomial-time algorithms run quickly and all superpolynomial ones run slowly. This is not an accurate definition for all practical problem sizes and this is where the analogies all break down. Polynomial vs nonpolynomial is more interesting to complexity theorists than "how many years would this actually take with a fast computer".

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

#135

Post by ncruces »

spencerflem wrote: post #74
ncruces wrote: post #64

Earlier quoted context omitted.

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

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.

You're right. That does cover it. I was playing with my kid and I didn't get it at first.

I might use smaller factors then.

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

#136

Post by dmurray »

bgoated01 wrote: post #76

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: h…

Four colours also isn't enough for some real-world country maps. Countries with enclaves (like Alaska, Kaliningrad or Sint-Maarten, though only the last actually makes 4- colouring impossible) change the topology: you can think of what shape the earth would have if there was also a tunnel connecting Alaska and New York.

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

#137

Post by isaacfung »

ianseyer wrote: post #91
bgoated01 wrote: post #76

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: h…

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…

How do I know if it is the original "Where's Waldo" under the paper?

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

#138

Post by [deleted] »

nroets wrote: post #131
ianseyer wrote: post #91

Earlier quoted context omitted.

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…

But it's a simplification: One iteration is enough to detect lying. In a real ZK proof the probability of the prover lying reduces after each iteration but never reached 0.

[deleted]

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

#139

Post by romwell »

zamadatix wrote: post #113
romwell wrote: post #41

Earlier quoted context omitted.

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 th…

Great description in that "proof" in this context is more referring to the limiting behavior and being able to get to your desired level of arbitrary happiness than necessarily providing a traditional "proof" about it being a certainty within a finite amount of estimation. Thanks.

Thanks for the feedback, glad my comment was helpful!

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

#140

Post by bumbledraven »

darajava wrote: post #49
MCSP wrote: post #13

Earlier quoted context omitted.

Whoops! Switched to "British Isles" -- update should be percolating now

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”

"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 notes:

> As a term, "British Isles" is a geographical name and not a political unit.

Post reply on HN