Maths Olympiad Prep

Library / /414 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it

A gambling student tosses a fair coin. She gains 11 point for each head that turns up, and gains 22 points for each tail that turns up. Prove that the probability of the student scoring [i]exactly[/i] nn points is 13(2+(12)n)\frac{1}{3}\cdot\left(2+\left(-\frac{1}{2}\right)^{n}\right).

Solution

1. Define the problem and initial conditions:
- Let pn p_n be the probability of scoring exactly n n points.
- Initial conditions:
p0=1(no toss - certainty to get 0 points) p_0 = 1 \quad \text{(no toss - certainty to get 0 points)}
p1=12(one fair toss of heads) p_1 = \frac{1}{2} \quad \text{(one fair toss of heads)}

2. Establish the recurrence relation:
- The probability of scoring n+2 n+2 points can be achieved by:
- Scoring n+1 n+1 points and then getting a head (probability 12pn+1 \frac{1}{2} p_{n+1} )
- Scoring n n points and then getting a tail (probability 12pn \frac{1}{2} p_n )
- Therefore, the recurrence relation is:
pn+2=12pn+1+12pn p_{n+2} = \frac{1}{2} p_{n+1} + \frac{1}{2} p_n

3. Solve the characteristic equation:
- The characteristic polynomial for the recurrence relation pn+2=12pn+1+12pn p_{n+2} = \frac{1}{2} p_{n+1} + \frac{1}{2} p_n is:
2λ2λ1=0 2\lambda^2 - \lambda - 1 = 0
- Solving this quadratic equation:
λ=b±b24ac2a=1±1+84=1±34 \lambda = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \frac{1 \pm \sqrt{1 + 8}}{4} = \frac{1 \pm 3}{4}
λ1=1,λ2=12 \lambda_1 = 1, \quad \lambda_2 = -\frac{1}{2}

4. Form the general solution:
- The general solution to the recurrence relation is:
pn=α1n+β(12)n=α+β(12)n p_n = \alpha \cdot 1^n + \beta \left( -\frac{1}{2} \right)^n = \alpha + \beta \left( -\frac{1}{2} \right)^n

5. **Determine the coefficients α \alpha and β \beta :**
- Using the initial conditions:
p0=1    α+β=1 p_0 = 1 \implies \alpha + \beta = 1
p1=12    α12β=12 p_1 = \frac{1}{2} \implies \alpha - \frac{1}{2} \beta = \frac{1}{2}
- Solving these equations:
α+β=1(1) \alpha + \beta = 1 \quad \text{(1)}
α12β=12(2) \alpha - \frac{1}{2} \beta = \frac{1}{2} \quad \text{(2)}
- Multiply equation (2) by 2:
2αβ=1(3) 2\alpha - \beta = 1 \quad \text{(3)}
- Add equations (1) and (3):
α+β+2αβ=1+1 \alpha + \beta + 2\alpha - \beta = 1 + 1
3α=2    α=23 3\alpha = 2 \implies \alpha = \frac{2}{3}
- Substitute α=23 \alpha = \frac{2}{3} into equation (1):
23+β=1    β=123=13 \frac{2}{3} + \beta = 1 \implies \beta = 1 - \frac{2}{3} = \frac{1}{3}

6. **Write the final expression for pn p_n :**
- Substituting α \alpha and β \beta back into the general solution:
pn=23+13(12)n p_n = \frac{2}{3} + \frac{1}{3} \left( -\frac{1}{2} \right)^n
- Simplifying:
pn=13(2+(12)n) p_n = \frac{1}{3} \left( 2 + \left( -\frac{1}{2} \right)^n \right)

The final answer is 13(2+(12)n) \boxed{ \frac{1}{3} \left( 2 + \left( -\frac{1}{2} \right)^n \right) }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.