Probability
Jane Stree Real numbers: P1
Puzzle:
- You are dogsitting for 5 nights.
- Dog will wake you up each night with probability 2/3
- What's the probablity of you being able to sleep for at least 2 full nights without being woken up by the dog?
Solution
- Each night prob of waking up is 2/3
- Each night is an independent event
- 5 nights
P(>=2) = 1 - [P(==0) + P(==1)]
P(==0) means you didn't get even a single night's full sleep. ie, dog woke you up on 5 days.
P(==1) means you were able to sleep well on one day, but the dog woke you up on the other 4 days.
P(==0) = 5C5 * (2/3)⁵
Number of sleepless nights = 5 days
5 days can be chosen in 5C5 ways
--
P(==1) = 5C4 * (2/3)⁴ * (1/3)
Number of sleepless nights = 4 days
5 days can be chosen in 5C4 ways
Therefore,
P(>=2) = 1 - [P(==0) + P(==1)]
= 1 - [(2/3)⁵ + 5*(1/3)*(2/3)⁴]
= 0.54
Info
Generally,
- P(A ∩ B) = P(A) + P(B) - P(A ∪ B)
- P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
Independent events:
- P(A ∩ B) = P(A) * P(B)
- P(A ∪ B) = P(A) + P(B)
Dependent events:
- P(A ∩ B) = P(A)*P(B/A)
- P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
Independent events and disjoint events are not same
- Disjoint events: Events that cannot happen together
- Eg: A single die showing 1 and 2 at the same time
- Eg: A coin being head and tail at once
- Independent events: Events occurring independent of each other
- When 2 coins are flipped together, result of each coin is independent of the other.
- In a chess game, each move is dependent on the previous moves.
If two events are disjoint, they are dependent unless one of the event is of zero probability.
A coin fip and a die roll simultaneously:
- Coin flip and die roll are independent events
- Result of coin flip has no effect on result of die roll
Example:
P(coin=H ∧ die=1)
= P(coin=H)* P(die=1)
= 1/2 * 1/6
= 1/12
---
P(die=3 ∨ die=5)
= P(die=3)+ (die=5)
= 1/6 + 1/6
= 1/3
—
Probability of event union for non-disjoint events:
P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
P(coin=H) and P(die=1) in our example are not disjoint events.
∵ Coin can be head while die shows 1.
P(coin=H ∨ die=1)
= P(coin=H) + P(die=1) - P(coin=H ∧ die=1)
= P(coin=H) + P(die=1) - [P(coin=H) * P(die=1)]
= (1/2) + (1/6) - (1/2)*(1/6)
= (4/6) - (1/12)
= 7/12
Could also be done like:
P(coin=H ∨ die=1)
= 1 - P(¬(coin=H ∨ die=1))
= 1 - P(¬(coin=H) ∧ ¬(die=1))
= 1 - [P(¬(coin=H)) * P(¬(die=1))]
= 1 - [1 - P(coin=H)] * [1 - P(die=1)]
= 1 - [1 - (1/2)] * [1 - (1/6)]
= 1 - [1/2] * [5/6]
= 1 - [5/12]
= 7/12
P(A ∧ ¬A) = 0
Dependent events.
P(A ∩ ¬A)
= P(A) * P(¬A/A)
= P(A) * 0
= 0
—
P(A ∨ ¬A) = 1
Dependent events.
P(A ∪ ¬A)
= P(A) + P(¬A) - P(A ∩ ¬A)
= x + (1-x) - 0
= 1
HMMT 2023: Q1
Puzzle:
Four people are playing rock-paper-scissors. They each play one of the three options (rock, paper, or scissors) independently at random, with equal probability of each choice. Compute the probability that someone beats everyone else.
Solution:
Scissor
∧ ∨
Stone < Paper
Observe that:
- Move doesn't matter.
- A particular move can be beaten by only a specific move
—
Let player 1 choose a particular move => 1/3
The other 3 players have to choose the same move and there is only one such move => (1/3)³
There are 4 players and player-1 can start with one of 3 possible moves
P = 4*3 * (1/3 * (1/3)³)
= 12/81 = 4/27
—
Related:
- https://old.reddit.com/r/learnmath/comments/199d063/question_when_you_play_rockpaperscissors_with_3/
- https://math.stackexchange.com/questions/3998809/probability-that-you-win-in-rock-scissors-paper-with-3-players
- https://math.stackexchange.com/questions/3144669/probability-of-one-person-winning-in-a-four-way-game-of-rock-paper-scissors
Jane Stree Real numbers: P2
Puzzle
- 6 cars parked in a row
- Prob that a car is taxi (independently) is 1/2
- What is the prob that there are 3 consecutive taxis among the 6 cars?
Solution
4.1 of Green book: Coin toss game
Puzzle:
- A has n+1 coins
- B has n coins
- All coins are fair
- When all coins are tossed, whats the probability that A has more heads than B?
Solution:
Combinatronics
Number of trailing zeros in n!
General forumla:
∞ │ n │
Σ │───│
i=1 │ 5ⁱ│
└ ┘
—
Example: 100!
100/5 + 100/5² + 100/5³ + ....
= 20 + 4
= 24
So, there are 24 trailing zeros in 100!
—
An easier way: Keep dividing recursively to get the numbers and sum up.
100/5 = 20
20/5 = 4
4/5 = 0
─────
24
ie, f(n) = n/5 + f(n/5)
—
Consider 25!.
25/4 is 5
- ∵ 5, 10, 15, 20, 25
- But not that 25 has actually two 5
- 5, 10, 15, 20, 5*5
- So need to consider all powers of 5
Likewise 4 consists of two 2s too. But we needn't care in this case, because number of 5s will always be lesser than that of 2s.
See:
- https://math.stackexchange.com/questions/1806642/find-the-number-of-trailing-zeros-in-n
- https://math.stackexchange.com/questions/286947/number-of-zero-digits-in-factorials
- https://math.stackexchange.com/questions/975539/how-do-you-find-the-number-of-multiples-of-a-given-range-of-numbers
Minimum cut
See:
Logic
Cheryl's birthday
(Heard from CakeML chat)
Q
Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is.
Cheryl gives them a list of 10 possible dates:
- May 15, May 16, May 19
- Jun 17, Jun 18
- Jul 14, Jul 16
- Aug 14, Aug 15, Aug 17
Cheryl then tells Albert and Bernard separately the month and the day of her birthday respectively.
- Albert: I don't know when Cheryl's birthday is, but I know that Bernard doesn't know too.
- Bernard: At first I did't know when Cheryl's birthday is, but I know now.
- Albert: Then I also know when Cheryl's birthday is.
So when is Cheryl's birthday?
A
- A knows month
- B knows day
> Albert: I don't know when Cheryl's birthday is, but I know that Bernard doesn't know too.
Bernad doesn't know means the day repeats in the list of 10 dates.
That means one of:
- Jul 14, Aug 14
- May 15, Aug 15
- May 16, Jul 16
- Jun 17, Aug 17
> Bernard: At first I did't know when Cheryl's birthday is, but I know now.
Coins
(Heard from CakeML chat)
Q
How do you give change worth £1.5? Use two UK coins. One coin must not be 50p.
For context: UK coins are £2, £1, 50p, 20p, 10p, 5p, 2p, 1p.
A
Facts
- Number of leaves in a complete binary tree of height H:
2^H