71–80 of 177 posts
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.
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.
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.
Earlier quoted context omitted.
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 th…
^ Exhibit A why using "believe" is a bad choice of words. Mathematical poofs are either correct or false. There is no middle ground.
Earlier quoted context omitted.
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 r…
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).
3 was a lot harder than expected — a great exercise for anyone honestly. I'm a math nerd so this was cool visualized!
Thanks for leading us down this mathematical rabbit hole today.
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.
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!
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…
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.