CombinatoricsDifficulty 7.3National olympiad, round 2Prove it
A gambling student tosses a fair coin. She gains 1 point for each head that turns up, and gains 2 points for each tail that turns up. Prove that the probability of the student scoring [i]exactly[/i] n points is 31⋅(2+(−21)n).
Solution
1. Define the problem and initial conditions: - Let pn be the probability of scoring exactly n points. - Initial conditions: p0=1(no toss - certainty to get 0 points) p1=21(one fair toss of heads)
2. Establish the recurrence relation: - The probability of scoring n+2 points can be achieved by: - Scoring n+1 points and then getting a head (probability 21pn+1) - Scoring n points and then getting a tail (probability 21pn) - Therefore, the recurrence relation is: pn+2=21pn+1+21pn
3. Solve the characteristic equation: - The characteristic polynomial for the recurrence relation pn+2=21pn+1+21pn is: 2λ2−λ−1=0 - Solving this quadratic equation: λ=2a−b±b2−4ac=41±1+8=41±3 λ1=1,λ2=−21
4. Form the general solution: - The general solution to the recurrence relation is: pn=α⋅1n+β(−21)n=α+β(−21)n
5. **Determine the coefficients α and β:** - Using the initial conditions: p0=1⟹α+β=1 p1=21⟹α−21β=21 - Solving these equations: α+β=1(1) α−21β=21(2) - Multiply equation (2) by 2: 2α−β=1(3) - Add equations (1) and (3): α+β+2α−β=1+1 3α=2⟹α=32 - Substitute α=32 into equation (1): 32+β=1⟹β=1−32=31
6. **Write the final expression for pn:** - Substituting α and β back into the general solution: pn=32+31(−21)n - Simplifying: pn=31(2+(−21)n)
The final answer is 31(2+(−21)n)
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.