Newsgroups: rec.puzzles
Subject: Re: Beating the fair coin flip over the phone
Summary: My method sucks, how 'bout yours?
Expires:
References: <2dvnsm$5ct@skates.gsfc.nasa.gov> <2e0b7h$pom@agate.berkeley.edu> <2e0f8k$ccc@news.u.washington.edu>
Sender:
Followup-To:
Distribution:
Organization: Princeton University
Keywords:
Cc:
In article <2e0f8k$ccc@news.u.washington.edu>,
Tim Smith wrote:
>
> I have a simpler solution. A picks two prime numbers, p and q, with
> p = 1 mod 4, and q = 3 mod 4. A tells B pq. B than says either "heads
> if p < q" or "heads if p > q". A reveals p and q, thus revealing whether
> B has heads or tails.
>
I've been wondering if solutions like these really are safe
from cheating. Does anyone have a proof that beating schemes like
these is hard [as hard as factoring, maybe]?
To support my distrust, I offer you a similar method. Have
A pick two prime numbers: p=4j+1, q=4k+3 as above. A tells B the
product pq. B then says either "heads if j+k is even" or "heads if
j+k is odd." A reveals p and q, thus revealing whether B has heads
or tails.
Anyone wanna bet with me some using this scheme? I'll play
the part of B. Sounds pretty fair, right? :-)
Well, I have a confession to make. I've rigged it so B can
win the coin toss 100% of the time. ObPuzzle: what's B's strategy?
[It's easy, but if for some reason noone gets it after a few days,
I'll post the answer.]
You can even vary my method a little. We could change the
method so that (for example) B says either "heads if j is even" or
"heads if j is odd" after he hears the product pq. Then B can still
win the toss every time. Etc. Blah blah blah.
Now, my point is this. What makes Tim Smith's method or
the rec.puzzles archive's method any safer than mine?
--------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu