This one was from the very first USA Math Olympiad. I thought it was rather easy compared to the other ones on the test, which goes to support the conjecture that, being the very first exam the problem writers had to create, they had trouble establishing a difficulty level. Anyway, here it is:
A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after 
I stole those latex images from AoPS, teehee. Hopefully they don't mind.
Anyway, we want the probability that after n selections, we have at least one factor of 2 and at least one factor of 5. So, just to clarify, we want at least one number of each set:
{2, 4, 6, 8} , {5}
The "at least" should be the tip off that instead you'll count the complement and subtract from the total number, which is 9^n . In case you couldn't tell, I'm just going for the counting approach.
Call the sets the (E)ven set and the (F)ive set. Or E and F for short. We want to count the number of sequences {a_n} such that it has either no elements of E or no elements of F. We can easily count these using PIE.
The number of sequences which have no elements of F is 8^n.
The number of sequences which have no elements of E is 5^n.
However, we overcounted the number of sequences which have neither elements of E or F, as it appears in both of our previous two sequences. Thus, we subtract it once.
The number of sequences which have no elements of E AND no elements of F is 4^n.
Thus, the total number of sequences such that the sequence does not contain an element from both sets E and F is 5^n + 8^n - 4^n.
We subtract this from our total number, 9^n. Thus, the total number of sequences with at least one element from both E and F is:
9^n - 5^n - 8^n + 4^n.
We divide this by the total number, 9^n, to get our probability, which is:
1 - (5/9)^n - (8/9)^n + (4/9)^n
USAMO 1972 - Combinatorics
Posted by Lord of Lawl at 21:38
Labels: Combinatorics, USAMO
0 Comments:
Post a Comment