Fairy Tale
In a certain tsardom, in a certain land, there lived a Tsar who loved mathematics. If you think this is a good thing, you are mistaken. The Tsar began arresting mathematicians to play riddles with them. Those he released, he would arrest again. Then he turned his attention to students and computer scientists. The physicists conferred on what to do and came up with a plan.

One day, two wise men in robes and long beards came to the Tsar. They said they were sent by spirits. The Tsar laughed, "There are no gods, no spirits. The universe obeys only mathematical formulas!"

The wise men said that the spirits were angered by such arrogance. Mathematics is contradictory, but the spirits keep this contradiction as a sacred thing. They know how to arrange numbers in a 3x3 table so that the product in each row is positive, but in each column, it is negative.

The Tsar pondered. This is impossible!

The wise men said they were merely conveying the words of the spirits.

The Tsar, of course, knew about zero-knowledge proofs, and the wise men easily explained this scheme to him—they would go to different rooms, and the Tsar would ask one of them to reveal a random column and the other a random row. If the product in the row is not positive, or in the column not negative, or if the number at the intersection of the row and column does not match, the Tsar can do as he pleases with the wise men.

The Tsar realized that if the wise men used a deterministic strategy, there would be potential answers for the first wise man when asked to present the first, second, and third rows. In other words, there is a table that he keeps in mind. Similarly, the second wise man also has a table. If these tables match, one of the rows or columns does not satisfy the condition, and with a probability of 1/3, the Tsar will notice the trick. If the tables do not match, there is a 1/9 chance that the Tsar will guess the coordinates of the mismatched cell.

The Tsar conducted this experiment 100 times, and all 100 times the wise men passed the test. The Tsar was astonished and frightened by the result, but he noticed that before each answer, the wise men would break a crystal. He asked what this crystal was. The wise men said that even they did not know all the numbers of the magic square and that the spirits communicated with them through the crystals. The Tsar suspected that these crystals contained a random number generator.

But probabilistic strategies are no better. Suppose the wise men's answers are a function of their random environment and the Tsar's question. Then one can fix the probabilistic space for the environment and say that for each environment (we'll clone the wise man twice), there are answers to questions about the first, second, and third rows. Then for each environment, the probability of an error is at least 1/9, and thus on average, there will be a probability of error of at least 1/9 (the tale would cease to be a tale if I mentioned "Fubini's Theorem," so let's just say that the Tsar double-checked this reasoning multiple times and became even more convinced of it).

The Tsar thought long and hard about how the wise men could have deceived him. He did not want to admit that it was indeed done by spirits, but doubt and fear had already crept into his heart. He gathered his best viziers. They speculated—maybe the second wise man predicted which question the Tsar asked the first wise man through micro-movements. Maybe there was a transmitter in the crystals. Then the Tsar said he would send the wise men to different cities in his tsardom, so far apart that even a radio wave would take three days to travel from one city to the other. His loyal servants would come up with random numbers from one to three and record the results. The wise men asked how many times they would be questioned. "A thousand," replied the Tsar. The wise men requested time to prepare a thousand crystals and at the appointed hour, they departed to their respective cities.

Needless to say, they passed this test as well. The Tsar began to doubt his previous beliefs and realized that the world was much more complex than he had thought. He was truly frightened. He conducted another test, then another, and with each test, he became more and more afraid. Finally, he asked what the spirits wanted from him.

The wise men said that the spirits wanted nothing more than for him to let mathematicians work in peace and to stop his riddles. The Tsar did as they asked and turned his attention to governing his tsardom, which had accumulated many problems during his obsession with mathematics. Under his wise leadership, the tsardom flourished and prospered. And until the Tsar's death, the physicists kept the secret of quantum mechanics, which had allowed them to outwit the wisest of tsars.