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 <tzs@stein2.u.washington.edu> 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