I came across a scenario in class today that I think makes for an interesting math problem.
There were 16 students in class and each of us was asked to find a partner for a particular hour of the day. For example, I might pair with Janet at 12 p.m., with Armando at 1 p.m., with Kelly at 2 p.m., and so on. I found at the end of the activity that I had one slot left (at 3 p.m., say) but no one else had that slot free. As such, I was unable to complete the assignment. This got me wondering how this generalizes into a problem, which I've stated below.
Problem
There are 16 students in a class. Can they be paired (forming groups of 2 students) over 12 time slots such that they meet the following requirements?
- Every student has a partner for each of the 12 time slots.
- No student pairs with the same student twice.
To be clear, it is not necessary that every student pairs with every other student, only that no student pairs with another student more than once.
Proposed Solution
My suspicion is that as long as there is at least one more student then there are time slots (16 students for 12 time slots, for example), then I think that this should be possible. My reasoning is as follows:
There are 120 ways to form pairs from 16 distinct people ($C_{16,2}$). There are 192 total time slots $(16 \cdot 12 = 192)$. Each time a pair is made, two of these slots are filled. So, we essentially have 96 $(192 \div 2 = 96)$ time slots to fill with 120 potential pairs. So we should have pairings left over, which would mean that the problem should be solvable.
I'm ignoring cases with an odd number of students since that would guarantee that (at least) one person was left out for each time slot.
Questions
Is my reasoning sound? Is there a clearer way to think about this? And if this is solvable, why didn't I end up without a partner at 3 p.m.?
Best Answer
I wouldn't exactly say your reasoning is sound, but you are on the right track. You say that as long as there are more student than there are time slots, it should be possible, but what you've really argued is the reverse; it is impossible if there are not more students than time slots.
A clearer way to think about it may be a round-robin tournament with $2n$ players and $2n-1$ rounds, each consisting of $n$ matches. In a round-robin, each player plays each of the other competitors exactly once. If you think of the players as students, the rounds as times slots, and the matches as pairing, you see that the problems are really exactly the same.
It has been known since the $19$th century that a round robin as described above can be scheduled for any even number of players. See this scheduling algorithm.
As to your last question, just because a schedule is possible, it doesn't mean that every attempt will succeed. Indeed, if that were true, there would be no need for an algorithm.