Skip to main content

Principle of Symmetry (Quick Note)

Pick n random points on the line (0, 1). This creates n+1 segments on the line. What is the distribution of length of the k-th segment?

Journey:
1. Try solving for the first segment.
2. Argue that the last segment has the same distribution as the first segment, by symmetry.
3. Surprise: the distribution is the same for all segments. Way to see this: instead of line, think of a circle, and argue by symmetry.


The interesting things to note:
Sometimes we can solve for simpler / extremal case, and then extend it to other cases by symmetry argument.


Application
How many cards on average need to be drawn from the deck to get an Ace?

The short answer:
Mark the top of the deck with a Joker card and arrange them in a circle. The 4As + Joker forms 5 segments on the circle. By symmetry, the length of the segments follow the same distribution and have the same average. The averages must add up to 53. So answer is 53/5.

The long answer, if we don't realise the symmetry:
Let F(t) be the probability of having to draw at least t cards from the deck before getting an Ace. Then F(t) = C(53-t, 4) / C(52, 4).

Let f(t) be the probability of having to draw exactly t cards. Then f(t) = F(t) - F(t+1).

Add t*f(t) up and telescoping we will get the answer C(53, 5)/C(52, 4) = 53/5.


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

sum of 3 out of 5 is divisible by 3

Problem: Among 5 integers, there are always 3 with sum divisible by 3. (From Problem Solving Strategies, Arthur Engel) Solution: Proof by Pigeon Hole Principle. An integer is either 0, 1 or 2 \( \pmod 3 \). Imagine placing 5 integers into those 3 boxes. If we have at least one in each, then we can pick one from each, with sum divisible by 3. Otherwise, we'll have at least 3 integers in one of the boxes. Pick those 3. 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