A Probability Puzzle from Facebook
Share:Puzzle. There are 100 cards with integers from 1 to 100. You have three possible scenarios: you pick 18, 19, or 20 cards at random. For each scenario, you need to estimate the probability that the sum of the cards is even. You do not need to do the exact calculation; you just need to say whether the probability is less than, equal to, or more than 1/2.
Sanandan Swaminathan:
For the scenario where we randomly pick 19 of the 100 cards, we can quickly see that the probability of getting an even sum is exactly 1/2. There are 50 odd cards and 50 even cards. To get an odd sum, an odd number of the 19 cards we picked should be odd cards. The number of samples containing 0 odd cards is the same as the number of samples containing 0 even cards, i.e. 19 odd cards. Similarly, the number of samples containing 1 odd card = number of samples containing 18 odd cards. And so on. Across all possible samples, we have an equal split between the number of samples containing an odd number of odd cards and the number of samples containing an even number of odd cards. Hence the probability of getting an even sum should be 1/2 when the number of cards picked is 19.
22 December 2023, 6:25 pmAndrew:
18: less. 19: 50%. 20: more.
Symmetry: we can relabel every card in the deck so that each even card becomes an odd and vice versa (for example, swap cards 1 and 100, 2 and 99, 3 and 98, etc.).
If you draw an odd number of cards, relabeling will swap the parity of the final result (if you had 9 even + 10 odd, which is even, then after relabeling you have 10 even + 9 odd, which is odd). There’s an even result for every odd result, so the two are equiprobable.
If you take an even number of cards, then there’s a possibility that you draw an equal number of evens and odds. These combinations pair with themselves under relabeling, so they’re over-represented.
If the number of cards you took is a multiple of 4, then “equal evens and odds” means the number of odd cards in your hand is a multiple of 2, so the sum is even.
If the number of cards you took is = 2 (mod 4), then “equal evens and odds” means an odd number of odd cards, and an odd sum.
23 December 2023, 1:24 amLazar Ilic:
A simple pairing argument works. The answers respectively are less, equal, and more. Consider the 50 buckets [1,2], [3,4], …, [99,100]. Then for each subset we may find the minimum bucket which contains 1 out of 2 elements in our subset. There is a paired subset where instead of that element from the bucket we had instead selected the other one. These pair off nicely to form odd and even summed subset pairs. The only exceptional case is if there did not exist any such bucket. Then each bucket must have contained 0 or 2 elements from our subset. And in particular for 18 and 20 this would logically imply there were 9 and 10 full buckets of odd sum meaning a slightly higher probability of odd and even sums respectively. To precisify further, for example in the 18 case, the probability of an odd sum is 1/2+[[50 choose 9]/2]/[100 choose 18] = 6119601330/12239202659 ~ 0.500000000040852334415128667737505105396915219099486…
23 December 2023, 6:19 amRoman:
Hi Tanya, nice puzzle. Here’s my solution: https://ro-che.info/articles/2023-12-23-random-cards-puzzle
23 December 2023, 7:57 amTheo:
Sanandan’s comment explains that for any off number N of random draws, the probability of getting an odd sum is exactly 1/2: the probability of drawing M odd cards is the same as the probability of drawing N-M odd cards.
Let’s inspect the distribution of possible M’s in more detail. It will depend on N mod 4: let me set N = 4K+1. The number M of odd cards should be distributed very close to a bell curve centred at 2K + 1/2. Condition on M being odd. There are more odd numbers, and they occur with higher rates, in the range 2K+1,…,4K+1 than there are in the range 0,…,2K. So you should expect that more than half of the cards are odd.
Mutatis mutandis conditioning on the total sum, equivalently M, being even: you expect that more than half of the cards drawn have the same parity as the total sum.
You get the opposite expectation if N = 4K-1.
Now, suppose I want instead to draw 4K cards. I’ll do this by drawing 4K+1 cards, and then picking on of my drawn cards at random to return into the pile. I expect my returned card to have the same parity as my sum before returning the card. So I expect my sum after returning the card to be even.
If I want to draw 4K+2 cards, I’ll draw 4K+1 cards, and then draw one more. I expect fewer than half of the remaining cards to have the same parity as my sum of 4K+1 cards, since more than half of my drawn cards have that parity. So I expect the 4K+2th card to have a different parity, so I expect that after pulling it, my total sum is odd.
The only not-fully-justified step in my logic was my guess that the distribution of possible values of M is close to a bell curve. Actually, what I need is just that M=2K+J, for J>0, occurs more often than M=2K-J. I do know that M=2K-J occurs with the same probability as M=2K+J+1. So I’m equivalently asking: can I know that M=2K+J occurs more often than M=2K+J+1 (when J>1)?
Suppose M > N/2 of my N cards are odd. To produce a hand with yet another odd card, I need to select an even card from my hand and return it, and draw an odd card from the deck. There are N-M 100-M cards. So there are more than 100M – M^2 choices. So there are more ways to reduce my number of odd cards — to move closer to an equally-split hand — than there are to increase my number of odd cards. So indeed a more-equal split occurs with slightly higher probability than a less-equal split.
23 December 2023, 9:51 amGuido:
Say that we have a deck of cards made of n zeros and n ones from which we pick the first k cards.
The sum of the k cars has the same parity as the number i of the ones picked. Now we carry out a little counting exercise
Number of ways of picking i ones, (n choose i) = Binomial[n,i]
Number of ways of picking k-i ones, (n choose k – i) = Binomial[n,k-i]
Number of ways of picking k cards, (2n choose k) = Binomial[2n,k]
with 0 <= i <= k.
The frequency of picking i ones is
h(i|n,n,k) = (n choose i) * (n choose k – i) / (2n choose k)
This is the Hypergeometric distribution that’s symmetric (and sharply peaked).
If k is odd, there are as many odd values of i as even values and, by symmetry, the frequency of an even sum is ½.
If k is even, the central value, h(k/2|n,n,k), stands alone: so, if k/2 is odd, an odd sum is more frequent while if k/2 is even, an even sum is more frequent.
For the three scenarios, the frequency of an even sum is (1-h(9|50,50,18))/2 ≈ 39,8 %, ½ = 50 %, and (1+h(10|50,50,20))/2 ≈ 59.8 % respectively
As we know nothing about the position of the zeros and ones in the deck we can assign those values as probabilities following the Principle of Indifference.
24 December 2023, 4:04 am