Competition problem — Combinatorics

Library / /22 of 24

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Five guys join five girls for a night of bridge. Bridge games are always played by a team of two guys against a team of two girls. The guys and girls want to make sure that every guy and girl play against each other an equal number of times. Given that at least one game is played, what is the least number of games necessary to accomplish this?

Solution

Solution:

Answer: 25

Suppose that each guy plays each girl $t$ times. Since each guy plays against two girls in one game, the total number of games each guy plays is $\frac{5 t}{2}$ . Then the total number of games is $\frac{25 t}{4}$ , which is a multiple of $25$ and therefore at least $25$ .

To check that $25$ games is enough, we arrange the guys and girls in two circles. A good pair of guys is a pair of guys who are adjacent in the circle; a good pair of girls is defined similarly. There are $5$ good pairs of guys and girls—making each good pair of guys play each good pair of girls works.

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.