It’s time for another contest. There are no prizes this time, and the general concept is a bit different. If you wish to participate, please write a comment with your answer—they will not be posted until the contest ends on August 5, 2010. Comments containing questions will be published as soon as I can, along with an appropriate answer.
The Problem
Having failed to find the correct warehouse in the previous installment, the Evil Overlord is back with a new plan : he found out that a lamp post on a street corner in Arkansas is somehow imbued with mystical powers that could be harnessed to enslave mankind. Cue maniacal laughter.
However, Empress Bing, from Alpha Centauri, knows about the lamp post too. And she wishes to use it for her own mad schemes. The two masterminds cannot fight each other over the lamp post, because it would attract attention. And neither is willing to let go.
So they decide to randomly pick which one of them gets the lamp post.
You have been selected by the two masterminds to help pick one of them at random. They do not trust you, so you will have to actually prove that the process used to do the picking guarantees that each of them had a 50% chance to be picked. Neither is willing to reveal their location, so you can only communicate through an encrypted text channel — you can’t send them fair coins, dice or quantum states.
The Question
Propose a random selection process and prove why it’s fair. Remember that the two masterminds do not trust anything you say unless it’s purely deductive or they can verify it themselves.
Hi. I'm Victor Nicollet,
I got an idea of the top of my head, from what little I remember about crypto stuff.
EO being evil overlord, EB being empress Bing
1. EO sends you a multiplication of two huge prime numbers, say 128 binary digits each
you pass it along to EB
2. EB sends you a multiplication of two such huge primes as well, you pass it along to EO.
Neither EO nor EB knows the two factors of the multiplication he received, since it is extremely time consuming to find factors of such a huge number.
3. After both have both numbers, each of them sends one of his two factors to you.
4. You multiply EO’s factor by a certain huge prime and send the result to EB. –> EB still cannot factors EO’s huge prime.
You multiply EB’s factor by same huge prime and send it to EO.
5. Now take both EO and EB factors they sent you, if the sum of bits is even the EO wins, if its odd then EB wins. Since neither of them knows the other’s factor they can’t tell who won, nor can they affect their chances. You tell them who won, and proof it in step 6.
6. You send both that huge prime you used in step 4. At this point they can each find the factor they received in step 4 and verify that the winner announced in step 5 is indeed the winner. They can verify that what they received in step 4 was indeed a number devised before they sent their own info in step 4 as it is a factor of the number they received in step 1.
the less mathematical analogy of what I tried to implement is this:
1. EO locks a lock, sends it to EB, same flipped. They cannot deduce the key from the lock.
2. EO takes his key and sends it to you, you lock it in a box with a third key and send it to EB, same flipped. At this point you know who the winner is (XOR of both keys), but neither EO nor EB knows.
3. You send that 3rd key to EO and EB. They unlock the chest and find the other’s key inside. They can verify it is indeed a key that was devised before they sent their own key as it unlocks a lock from step one.
can we consider internet conection as “perfect”?
if it the case :
1 step: get this 2 creep on the same time (IE atomic time)
2 step: explain them the rules :
- the d,day : you will send an email at 10pm00min00sec to me and to the oponent with a single a single number : 1 or 2
- if one of the 2 email is off-time, it gave the victory to the other one
- if the two email are off-time, it result as a draw and the game will start with the same rules at D+1 day
- if the two mail are in time :
– if the two number are the same emperess bing win
– if the two number are different evil overlord win
Convoluted. As always. Oh God, it’s going to hurt…
Can bing and evil communicate directly?
@Lieven van der Heide: yes, they can communicate through a secret channel (that you cannot hear). All communication happens one-on-one.
Wait…
Is the Evil Overlord named… Gogl ? (or something that would be very similar?)
“Evil Overlord Wave” does have a certain feel to it