Skip to main content

Birthdays and Celebrations (Quick Notes)

Given N people, what is the number of birthday celebrations on average in a year?

Solution

The quick solution is: the probability of having a celebration in a particular day is 1 - (364/365)^N. So the average is 365(1 - (364/365)^N).  (Linearity if expectation)

I wonder if someone tries to solve this problem directly, i.e. compute the number of ways to assign birthdays to N people to have k celebrations, call this B(N, k), then the average number of celebrations = sum k B(N, k).

Turns out B(N, k) is very similar to something called Stirling number of second kind, which computes the number of ways to partition N labelled objects into k non-empty unlabelled groups. One can come up with the recurrence relation quite easily, but to directly compute it is interesting and relies on principle of exclusion and inclusion.

The PIE for B(N, k) goes like this: let A_d be the set containing all assignments of birthdays where birthday d is unused. Then the answer is k^N - | A_1 union A_2 union ... union A_k |, which can be computed by PIE.





Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

2n+1 3n+1 squares then 5n+3 not prime

Problem: Prove that if \( 2n+1 \) and \( 3n+1 \) are both squares, then \( 5n+3 \) is not a prime. Solution: Proof by contradiction. Suppose that there is n such that 5n+3 is prime. Note that \( 4(2n+1) - (3n+1) = 5n+3 \). Let \( 2n+1 = p^2 \) and \( 3n+1 = q^2 \), where \( p, q > 0 \). We have \( (2p-q)(2p+q) = 5n+3 \). Since RHS is a prime, we must have \(2p - q = 1 \) and \( 2p + q = 5n+3 \). Solving for \( q \) we get \( 2q = 5n + 2 \). Substituting, we get \( 2q = q^2 + 2n + 1 \), or \( -2n = (q-1)^2 \). Since RHS is \( \geq 0 \), we can only have equality when \( n= 0 \) and \( q = 1 \). In this case, we have \( 5n + 3 = 8 \) not a prime. QED.
Post a Comment
Read more

12 coins

Problem: There are 12 identical coins. There might be one that is a counterfeit, which is either heavier or lighter than the rest. Can you identify the counterfeit (if any) using a balance at most 3 times? Solution: I think this is one of the most difficult variations of the coins weighing problem. The main idea is to "mark" the coins after weighing them. Step 1. Divide the coins into groups of 4. Weigh the first two. If they have the same weight, go to step 4. Otherwise, mark the coins belonging to the heavier group 'H', lighter group 'L', and the unweighted ones 'S'. We know that the counterfeit is either in L or H. Step 2. Now we have 4 Hs, 4 Ls, and 4 Ss. We now form 3 groups: HHL, LLH, and HLS. Step 3. Weigh HHL against HLS. Case 3.1: HHL is lighter than HLS. Then either the L in HHL or the H in HLS is the counterfeit. Simply weigh one of them against S and conclude accordingly. Case 3.2: HHL is heavier than HLS. Then the counterfeit ...
Post a Comment
Read more