adityamukerjee.net
Flipping a Coin Over the Phone | /var/blog
Last week, a friend and I had to arrange an in-person meeting after work, by email. He's based on the Upper East Side, and I'm in Chelsea. Neither one of us wanted to make the trek to the other's office, and there was no logical place "in between" where we'd have a quiet space. The obvious solution would be to flip a coin, which he suggested. But how do we know that the other is telling the truth? The procedure for having Alice and Bob flip a coin over the phone is actually fairly simple. (Conveniently, my friend's name begins with a 'B', so I'll make him Bob, and I'll be Alice). First, Alice flips a coin, but keeps the result of the coin flip secret. Let's say that 'H' is 1, and 'T' is 0. Then, Alice finds a book - (almost) any book will do, as long as Bob has a copy of the book as well. She picks an arbitrary page in the book. If the coin flip was H (1) she should pick an odd page; otherwise,