Problem:
Six men and some number of women stand in a line in random order. Let be the probability that a group of at least four men stand together in the line, given that every man stands next to at least one other man. Find the least number of women in the line such that does not exceed percent.
Solution:
Let be the number of women in the line. For every man to stand next to at least one other man, the men need to be grouped in one of the orders or .
The number of arrangements of the men and women in the line of the form can be counted by placing one woman between each of the groups of two men, and then placing the remaining women in any of the four positions around the men. Thus the number of arrangements of men and women for this grouping is .
The number of ways men and women can be arranged so that the men form two separate groups, that is, in the arrangements or , can be counted using the same technique by placing one woman between the two groups then placing the remaining women in any of the three positions around the men. Each of these three groupings results in arrangements.
Finally, the number of arrangements of men and women in the line where all six men stand together is , because there are that many positions in which to place the single group of men among the women.
Thus the probability that at least four men stand together
For this probability to be less than or equal to , the quadratic function must be nonnegative. It follows that the least number of women needed for not to exceed one percent is the least positive integer for which is positive. Because is a quadratic function which is negative at zero, the least for which is positive is the positive integer value at which changes from negative to positive. Note that , but . It follows that the answer is .
The problems on this page are the property of the MAA's American Mathematics Competitions