Suppose you are a time traveller--and specifically, you travel like the folks in the Terminator, so you don't get to bring anything back with you. When you arrive in 2006 (I'll start this business on 01 January, let's say), how do you prove that you are, in fact, from the future?
Well, this one's easy. It's just a formalization of checking the newspapers before you leave. Anyway, keep in mind that I keep a permutation H of the integers in my back pocket at all times (everyone should do this, I think; I have some hash functions and a few large primes back there, too), but it's a special permutation because no one knows how this permutation actually works. Meaning, if I give you a number n, H(n) just pops out, but knowing n, you can't predict what H(n) will be unless you try it.
Now, suppose that we take 01Jan2006 to be day 1, and on day x, we compute H(x) and publish the answer, doing this on each day of the year 2006. In particular, only one number is produced each day. And suppose your departure was on day n of 2007, arriving sometime earlier than day n-2. Then to prove you are from the future, in fact that you departed sometime after day n-1, all you need do is correctly tell us all what H(n-1) is going to be--you couldn't know that unless you'd seen it happen already, so you must be from the future. Note especially, that you only have to remember one number, assuming you're efficient about proving yourself when you get here.
---
Suppose you have a friend, Milton, who is blind, and you want to prove to him that the two marbles you are holding (let's assume you have a great love of marbles, for some reason, and for a sufficiently weak definition of "reason") are actually different colors, though they are in every other respect identical. Milton, however, knows that you are something of a fibber, and, apparently, kind of a dick, so he won't just believe you when you demand that they are blue and red, respectively, even when you hop around like a tyrant gnome and shout crazily. Assuming also that Milton actually wants to know if you're lying, whatever shall Milton do?
Well, first you have to give him the marbles. Sorry, no way around it, but assume he's more honest than he credits you for. You sit yourself down at the table, and there you will sit for the rest of the game. (Milton can hear you, so don't try to get away with anything.) Milton puts one marble in his pocket and the other on the table, and he asks you, "What color is this marble?" Naturally, you answer. He then takes that marble with him as he leaves the room, closing the door behind him. While he's out there, he flips a coin to decide whether or not to switch the marbles roles. He then returns and places the appropriate marble on the table, with the same query. And you answer.
If the marbles are actually different colors, then you'll have no trouble determining if he's switched them or not. You'll get it right unless something's wrong with you. On the other hand, suppose the marbles were actually the same color. Then, when the marble was placed on the table the second time, you could only guess randomly about whether or not the marbles had been switched. Hence, the probability that you get the answer right is only 0.5; in other words, with probability 0.5, he's caught you in the lie. That means, that if you guess correctly (so that he must believe that the colors are really different), the probability that he's been fooled is only 0.5. Of course, if you go through this game n times independently, the probability that Milton gets fooled every time is only (0.5)^n. When n is 10, the chance that he's been fooled is only about 1 in a 1000. He'd probably believe you then.
--
Coming soon: How to flip a coin over the telephone.
