Maths Olympiad Prep

Library / /681 of 740

, 2017

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

There are 12 students in a classroom; 6 of them are Democrats and 6 of them are Republicans. Every hour the students are randomly separated into four groups of three for political debates. If a group contains students from both parties, the minority in the group will change his/her political alignment to that of the majority at the end of the debate. What is the expected amount of time needed for all 12 students to have the same political alignment, in hours?

Solution

Solution:

When the party distribution is 66-66, the situation can change (to 33-99) only when a group of three contains three people from the same party, and the remaining three are distributed evenly across the other three groups (to be converted).

To compute the probability, we assume that the groups and the members of the group are ordered (so there are 12!12! ways of grouping). There are 22 ways to choose the party, 44 ways to choose the group, 6546 \cdot 5 \cdot 4 ways to choose the three members of the group, 9639 \cdot 6 \cdot 3 ways to place the other three members of the party, and 6!6! ways to fill in the members of the other party. The probability is then
246549636!12!=24654963121110987=1877 \frac{2 \cdot 4 \cdot 6 \cdot 5 \cdot 4 \cdot 9 \cdot 6 \cdot 3 \cdot 6!}{12!} = \frac{2 \cdot 4 \cdot 6 \cdot 5 \cdot 4 \cdot 9 \cdot 6 \cdot 3}{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7} = \frac{18}{77}
This means that the shift in distribution will happen in 7718\frac{77}{18} hours on average.

When the distribution is 33-99, the situation can change (to 00-1212) only when the three members of the minority party are all in different groups. Using the similar method as above, there are 129612 \cdot 9 \cdot 6 ways to place the three members and 9!9! ways to place the rest, so the probability is
12969!12!=1296121110=2755 \frac{12 \cdot 9 \cdot 6 \cdot 9!}{12!} = \frac{12 \cdot 9 \cdot 6}{12 \cdot 11 \cdot 10} = \frac{27}{55}
This means that the shift in distribution will happen in 5527\frac{55}{27} hours on average.

By linearity of expectation, we can add up the two results and get that the expected value is 7718+5527=34154\frac{77}{18} + \frac{55}{27} = \frac{341}{54} hours.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.