One of the most beautiful and surprising results in mathematics is that I actually CAN convince you that three colors suffice without giving away the solution!
I'll illustrate on a (very simple) example:
This is an example of a "zero-knowledge proof," which proves something is true while somehow also not revealing anything. Surprisingly, zero-knowledge proofs exist for any mathematical statement and have many real-world applications.
You may have a few questions. Learn more by clicking on these:
Answer: Each time I color the map, I will randomly swap all the colors. This way, each time we do all the steps, you will just see two random colors. Thus, there is nothing consistent to piece together, or anything to learn from.
In more detail, there is (surprisingly) a mathematical definition by Goldwasser, Micali, and Rackoff of "revealing nothing." Goldreich, Micali, and Wigderson showed that the process above meets this definition.
Answer: If three colors do not suffice, then there will always be one pair of touching regions with the same color. You have a small chance of picking this pair each time. By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning.
Answer: As part of the physical post-it setup, we assume one cannot add/change the color under a post-it. But to understand how this works without this assumption, see the question about doing this without post-it notes.
Answer: As mentioned before, many tasks are just the 3-coloring question in disguise. It turns out one can transform any mathematical proof into a map that has a 3-coloring and then run this procedure.
Answer: Instead of using post-it notes, we can instead encode each color using numbers in an unusual way. For example (slightly simplifying), we can randomly pick a number with a certain amount (depending on the color) of prime numbers that divide it:
(Don't worry if you don't remember what a prime number is. All you need to know is that table assigns a unique color to every number.)| Color | Encoding: a Number with __ Primes Dividing It | Example |
|---|---|---|
| ● | 2 or fewer | 10 = 2 x 5 |
| ● | Exactly 3 | 30 = 2 x 3 x 5 |
| ● | 4 or more | 60 = 2 x 2 x 3 x 5 |
There are three important properties of this encoding.
1) Revealability. If I give you a number and the list of primes dividing it, you can easily tell its color. For instance, 13793561 = 293 x 263 x 179, has three prime divisors, so it encodes ●.
2) Hiding. If I give you just the number (without the list of prime divisors) like 33793561, it is hard to tell what color it is.
3) Unique Decoding. Every number corresponds to a single unique color.
Hit this checkbox to see this method in action on the example above:
