The coin toss over the telephone

How can you toss a coin over the telephone in such a way that both sides are happy that nobody cheated?

So here's the scenario. A couple of weeks ago I called my pal Alice on the telephone to tell her there was a great Black Sabbath tribute band playing in town on Saturday night and would she like to come with me. "Actually" she said "I don't care for them too much. But there's an ABBA tribute band on that night at another club in town"

"Okay" I replied "then why not toss a coin to see which one we go to". "Sounds good" she said "Okay I'm tossing the coin now" (I heard a faint metallic ping at the other end of line) "Is it heads or tails?"

"Heads" I guessed. "Sorry" she laughed "It's tails. Better get brushing up on the lyrics for Mama Mia"

Well, I trust Alice, so my Saturday night was spent singing along to Waterloo etc. But this weekend when I called to tell her there was an AC/DC tribute band on and she told me that she would rather go to a Robbie Williams tribute act that night, my heart sank.

"We'll do a coin toss again" she said "but this time I thought of a way that you be absolutely 100% sure I'm not cheating". "One small problem" I said "We can't do video calling because I'm on the landline because my mobile battery is flat. So I can't see the coin. We can only do a voice conversation. How am I going to know if you are telling the truth or not?"

"Well in that case, we can't do an actual coin toss" she mused "but that doesn't matter. All we really need to do is emulate a situation which has exactly a 50:50 chance of you being correct, and one which you can check for yourself whether or not you were right or not. Give me a couple of minutes while I grab a pen and a scrap of paper and you grab a pen and paper too"

I got a pad and pen off the coffee table and sat there for about 30 seconds and then Alice spoke again. "Okay then!" she said "I am going to ask you a question and you have just THREE seconds to answer it so you are going to have to take a total guess between the two possibilities I am going to give you. Each of the possibilities has a 50% chance of being the right one. Are you ready for your question"

"I'm ready"

"Listen carefully. Write this eight digit number down on your notepad: 19,603,897. I got that number by multiplying two primes together. Now tell me - does the HIGHER of those two prime factors start with an ODD number or an EVEN number? In 3...2...1....."

"An odd number!" I guessed.

"Sorry, it's an even number" Alice replied. "You can check for yourself now so you can see I wasn't lying. The higher number is 4987 and the lower number is 3931"

"Where did you get that idea?"

"From the P versus NP problem. It was easy for me to multiply the two numbers together but there was no way in three seconds you could unfactorise it. Of course, given a bit more time, you could have gone online to try and get the answer, but to get round that I would just make my prime numbers bigger. It would still be easier for me to multiply two huge numbers than it is for you to try and reverse-engineer the process"

"Well, learning that has made up a bit for the outcome" I said philosophically.

"I'm only teasing you" Alice laughed. We did ABBA last week, so this week let's both go and see AC/DC. And don't worry if it takes you ages to understand the P versus NP problem - it's a long way to the top if you want to rock and roll."