Grandma's Tweetin'
Siuan's grandmother recently signed up for a twitter account. She only follows five people - her five grandchildren. Each day, each of her grandchildren make two tweets and at the end of the day Siuan's grandmother gets an e-mail that lists all ten tweets in chronological order. If the times of each grandchild's tweets are random, the probability that no consecutive pair of tweets in the e-mail are by the same person can be expressed as b a where a and b are coprime positive integers. What is the value of a + b ?
The answer is 182.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
The question is equivalent to asking if we arrange 5 pairs of identical items in a row, what is the probability that no consecutive pair is identical. The total number of such arrangements is 2 ! 2 ! 2 ! 2 ! 2 ! 1 0 ! = 1 1 3 4 0 0 . We will use the principle of inclusion and exclusion to count the number of configurations that have at least one consecutive pair.
If we choose k of the pairs of identical items, the number of ways that these k pairs can be arranged together is ( 2 ! ) 5 − k ( 1 0 − k ) ! . The numerator comes from grouping together each identical pair and treating them as a single item. The denominator comes from the other 5 − k pairs still having two identical items. Since for any k subsets this formula holds, the P.I.E. tells us that there will be ∑ k = 1 5 ( − 1 ) k + 1 ( k 5 ) ( 2 ! ) 5 − k ( 1 0 − k ) ! orderings where at least one pair is consecutive. This evaluates as 1 1 3 4 0 0 − 5 0 4 0 0 + 1 2 6 0 0 − 1 8 0 0 + 1 2 0 = 7 3 9 2 0 .
Thus, the probability that some consecutive pair is identical is 1 1 3 4 0 0 7 3 9 2 0 = 1 3 5 8 8 . The probability that no consecutive pair is identical is 1 − 1 3 5 8 8 = 1 3 5 4 7 , and a + b = 4 7 + 1 3 5 = 1 8 2 .
Nice!
Deeparaj Bhat, I did it by recursion: if she has m grandkids who each tweet once, and n grandkids who each tweet twice, the number of ways that satisfy the "no consecutive" requirement is:
N ( m , n ) = m N ( m − 1 , n ) + n [ N ( m + 1 , n − 1 ) − N ( m , n − 1 ) ]
where N ( m , n ) = 0 if m or n is negative and N ( 0 , 0 ) = 1 .
Is P.I.E the only method though?
Log in to reply
Depends on what you mean by "only method". It is the best/most straightforward IMO.
Of course, we could always list out the probability tree and then slowly check all of these events.
First, we will find the probability of at least one grandchild making consecutive tweets by using the inclusion-exclusion principle, and then subtract the result from 1.
From the inclusion-exclusion principle,
P(at least one grandchild makes consecutive tweets)
= (5 choose 1)P(a specified grandchild makes consecutive tweets) - (5 choose 2)P(two specified grandchildren makes consecutive tweets) + (5 choose 3)P(three specified grandchildren makes consecutive tweets) - (5 choose 4)P(four specified grandchildren makes consecutive tweets) + (5 choose 5)P(all five grandchildren makes consecutive tweets).
For 1 <= k <= 5, we need to find the probability that k specified grandchildren (and possibly others) make consecutive tweets. There are 10! permutations of all 10 tweets. Think of arranging k "blocks" of two tweets each, and (10 - 2k) single tweets. There are (10 - k)! ways of arranging these (10 - k) items, and 2 ways of arranging the two tweets within each of the k blocks. So (10 - k)!(2^k) of the 10! permutations result in k specified grandchildren (and possibly others) making consecutive tweets. So the probability that k specified grandchildren (and possibly others) make consecutive tweets is (2^k)/[10 9 ...*(10 - k + 1)].
Therefore, we have P(at least one grandchild makes consecutive tweets) = 5(2/10) - 10(4/(10 9)) + 10(8/(10 9 8)) - 5(16/(10 9 8 7)) + 1(32/(10 9 8 7 6)) = 1 - 4/9 + 1/9 - 1/63 + 1/945.
So the probability of no grandchild making consecutive tweets is 1 - (1 - 4/9 + 1/9 - 1/63 + 1/945) = 4/9 - 1/9 + 1/63 - 1/945 = 47/135. so the ans is 47+135=182
First, we have to find the probability of at least one grandchild making consecutive tweets by using the inclusion-exclusion principle, and then subtract the result from 1.
From the inclusion-exclusion principle,
P(at least one grandchild makes consecutive tweets)
= {(5 choose 1)P(a specified grandchild makes consecutive tweets) - (5 choose 2)P(two specified grandchildren makes consecutive tweets)} + {(5 choose 3)P(three specified grandchildren makes consecutive tweets) - (5 choose 4)P(four specified grandchildren makes consecutive tweets)} + (5 choose 5)P(all five grandchildren makes consecutive tweets).
For 1 <= k <= 5, we need to find the probability that k specified grandchildren (and possibly others) make consecutive tweets. There are 10! permutations of all 10 tweets. Think of arranging k "blocks" of two tweets each, and (10 - 2k) single tweets. There are (10 - k)! ways of arranging these (10 - k) items, and 2 ways of arranging the two tweets within each of the k blocks. So (10 - k)!(2^k) of the 10! permutations result in k specified grandchildren (and possibly others) making consecutive tweets. So the probability that k specified grandchildren (and possibly others) make consecutive tweets is (2^k)\frac {[10 * 9* ... * (10 - k + 1)]}.
Therefore, we have P(at least one grandchild makes consecutive tweets) = 5( \frac {2} {10} ) - 10( \frac {4} {(10 * 9)}) + 10(\frac {8} {( 10 * 9 8 )}) - 5(\frac {16} {(10 9 8 7)}) + 1(\frac {32} {(10 9 8 7 6)}) = 1 - \frac {4} {9} + \frac {1} {9} - \frac {1} {63} + \frac {1} {945}.
So the probability of no grandchild making consecutive tweets is 1 - (1 - \frac {1} {9} + \frac {1} {9} - \frac {1} {63} + \frac {1} {945}) = \frac {4} {9} - \frac {1} {9} + \frac {1} {63} - \frac {1} {945} = \frac {47} {135}. so,a=47 and b=135 and (a+b)=182
We use the principle of inclusion-exclusion to count the number of ways that at least one pair of consecutive tweets are by the same person. First count the number of ways to have one pair of consecutive tweets by the same person, as follows. There are five ways to choose the person tweeting the pair, two ways to permute the consecutive tweets, and then (considering the pair of tweets to now be a single unit), 9! ways of permuting all the tweets. The product is 5 * 2 * 9! = 3628800.
But this double-counts the cases where two pairs of consecutive tweets are by the same person, so we have to subtract those away. By similar reasoning, there are 10 ways to choose the two people tweeting the pairs (5 choose 2), 2 * 2=4 ways to permute the consecutive tweets, and then (considering each pair of tweets to now be a single unit), 8! ways of permuting all the tweets. This product is 10 * 4 * 8! = 1612800.
Continuing in a similar vein and using PIE, we now add the cases where three pairs of consecutive tweets are by the same person (numbering 10 * 8 * 7! = 403200), subtract the cases where four pairs of consecutive tweets are by the same person (numbering 5 * 16 * 6! = 57600), and finally add the cases where five pairs of consecutive tweets are by the same person (numbering 1 * 32 * 5! = 3840). Getting out my calculator, I obtained 3628800-1612800+403200-57600+3840 = 2365440 for the number of ways that at least one pair of consecutive tweets are by the same person.
The total number ways the ten tweets can be received is 10! = 3628800. So the number of ways of having no pair of consecutive tweets by the same person is the difference 3628800-2365440 = 1263360, and the probability that no pair of consecutive tweets are by the same person is the fraction 1263360/3628800, which reduces to 47/135. Hence the answer to the problem is 182.