Re: permutation mappings

From: David Eather (eather_at_tpg.com.au)
Date: 09/28/04 

Date: Wed, 29 Sep 2004 03:01:49 +1000

Peter Pearson wrote:
> duffman wrote:
>
>> Let PI be a permutation of the integers 0,1,2,3...2^(n-1)
>> ...
>> ... Show the somewhat unexpected result that over 60% of mappings
>> will have at least one fixed point.
>>
>> any ideas?
>
> Is this a homework assignment?
>
> In a mathematical games column long ago, this problem was
> presented in another form: what are the odds of winning a
> game in which Alice and Bob shuffle decks of cards, then
> reveal cards simultaneously. If ever two cards match, Alice
> wins, but if they get through the decks without encountering
> a match, Bob wins.
>
> There's a quick and erroneous analysis that gets the right
> answer. The only correct derivation I've seen was not quick.
>
> - Peter Pearson

They should get just one match