MOVES Puzzle-Solving Meet-Up
Solution to Peter’s Puzzle
It’s useful, for solving this puzzle, to be able to compute the number of (unordered) pairs of elements that can be drawn from a set of size N. There are N ways to draw the “first” element of the pair and N-1 ways to draw the “second,” thus N(N-1) ways to pick an ordered pair. Since there are two ways to order any pair, the number of unordered pairs is only N(N-1)/2, known as “N choose 2.”
Back to the puzzle. On any day, either there are three breakout rooms of size 4, or four of size 3. In the former case, 3 x (4 choose 2) = 18 pairs of students are together; in the latter, 4 x (3 choose 2) = 12 pairs. There are 12 choose 2 = 66 pairs of students altogether, so Ms. Gonzalvez needs to make up 66 by adding some 18s and some 12s. It is not hard to see that there are just two ways to do this: 66 = 18 + 18 + 18 + 12 or 66 = 18 + 12 + 12 + 12 + 12. The first way requires three days split into breakout rooms of size 4, and one with breakout rooms of size 3; the second, one day with breakout rooms of size 4 and four with size 3.
The first of these is impossible; even two days with breakout rooms of size 4 causes some pair of students to be together twice. The reason: one of the second day’s breakout rooms would have to contain two students (or more) from a first-day breakout room.
Thus Ms. Gonzalvez’ schedule must run five days, one with breakout rooms of size 4, the rest size 3.
Those who don’t trust the puzzle poser will want to be assured that there actually is a schedule with the required property. There are many; here’s one:
Day 1: ABCD EFGH IJKL
Day 2: AEI BFJ CGK DHL
Day 3: AFK BEL CHI DGJ
Day 4: AGL BHK CEJ DFI
Day 5: AHJ BGI CFL DEK
(Thanks to Mind-Benders subscriber Tom Tsao for suggesting the idea of a puzzle based on scheduling breakout rooms!)