Author |
Topic: Card throwing probability (Read 772 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Card throwing probability
« on: Dec 29th, 2005, 2:43pm » |
 Quote  Modify
|
Not sure if this has been asked before...
Anyway, here goes:
p is an odd prime number. You have 2 decks of p cards each, each deck having cards numbered 1 to p, the numbers being written on the front face of the cards. You throw the cards up and they randomly fall to the floor. You now sum up the numbers on the cards which have fallen face up.
What is the probability that this sum is divisible by p?
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Card throwing probability
« Reply #1 on: Jan 3rd, 2006, 10:10pm » |
Quote Modify
|
What is wrong with this one? too easy/hard... seen it before?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Card throwing probability
« Reply #2 on: Jan 3rd, 2006, 10:47pm » |
Quote Modify
|
I would say not too easy, and not seen this before. 
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Card throwing probability
« Reply #3 on: Jan 4th, 2006, 6:04am » |
Quote Modify
|
Well, since I'm more of an experimentalist than an analyst, I thought I'd investicate a few small cases:
p = 3: 24 / 26 ~ 1 / 2.66667
p = 5: 208 / 210 ~ 1 / 4.92308
p = 7: 2344 / 214 ~ 1 / 6.98976
p = 11: 381304 / 222 ~ 1 / 10.9999
p = 13: 5162224 / 226 ~ 1 / 13.0000
That should give you analytical types something to work with. 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Card throwing probability
« Reply #4 on: Jan 4th, 2006, 8:00pm » |
Quote Modify
|
Nice problem!
We need to count the number of subsets whose sum is divisible by p. Hint: I expected this to be roughly 4p/p. Of course it can't be exactly, but it's reasonable to assume that the solution will include a combinatorial proof that (4p-4)/p is an integer. I only know the one, so...
| hidden: | Clearly there is 1 subset with 0 cards, and 1 with 2p cards.
Now consider taking any subset of k cards, and adding 1 to each card (mod p), increasing the sum by k. If we do this p times, and k is relatively prime to p, then we get a cycle of p subsets, exactly one of which will have sum 0 mod p. This partitions the subsets of size other than 0, p, or 2p, of which there are 22p-1-(2pCpp)-1, and we count exactly 1/p-th of them.
Now consider a subset of size p. If it is not all from a single deck, then we can similarly cycle just the cards from the second deck, changing the sum by a number relatively prime to p each time. Thus we count exactly 1/p-th of these (2pCp)-2 possibilities, together with 2 ways of taking all p cards from a single deck.
Altogether, we have
2 + [ 22p - 2 - (2pCp) ]/p + [ (2pCp) - 2 ]/p + 2 = [ 4p + 4(p-1) ]/p. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Card throwing probability
« Reply #5 on: Jan 4th, 2006, 10:32pm » |
Quote Modify
|
Excellent! Well done Eigenray.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Card throwing probability
« Reply #6 on: Jan 5th, 2006, 4:37pm » |
Quote Modify
|
here is another solution which uses generating functions...
Let P(z) = ( (1+z)(1+z2)...(1+zp) )2
We are looking for sum of coefficients of zkp where k starts at 0 and goes on...
Set Q(z) = P(z) + P(wz) + P(w2)+... + P(wp-1z)
where w is a pth root of unity.
We see that we are looking for Q(1)/p.
It is easy to see that P(wm) = 4 for 0 < m < p (Consider H(z) = zp -1 = (z-w)(z-w2)...(z-wp) and set z = -1)
|
| « Last Edit: Jan 5th, 2006, 6:07pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print