Tournament plan

Question

Last week, my math teachers and I were asked to solve a problem for a gym teacher. He has 12 sprinters and 3 lanes to run on. The problem is: How many runs do he has to do to guarentee that each sprinter competes at least once against every other sprinter?

But we (as mathmaticians) do not stop here, we asked 3 more generall problems:

(P1): You have $n$ sprinters and $1<m\le n$ lanes. How many rounds do we have to do to guarantee that each sprinter competes at least once against every other sprinter (you can leave lanes empty)?

(P2): How many rounds do we have to do to guarantee that each sprinter competes exactly once against every other sprinter (you can leave lanes empty)?

(P3): What if we add a fairness argument to (P1)/(P2): How does the minimum number of rounds changes if we want to guarantee that evere sprinter has to participate in the same number of rounds?

We worked (almost) the hole weekend for those problems. For the original 12&3 problem we got $25$ as the minimum number, by using simple graphs and basic combinatorics. But when we come to the generalisation (namely P1, P2, P3) we did not found a solution.

In each of those three problems $\frac{\left( n-1 \right) n}{2}$ is definitely an upper bound. Because if you only do 1 vs. 1 runs (leave the other lanes empty) the first sprinter has to do $n-1$ duels, afterwards the second sprinter only has $n-2$ duels left (because he has already run against sprinter 1), etc.: $\sum_{k=0}^{n-1}{k}=\frac{\left( n-1 \right) n}{2}$. But finding lower bounds is unfortunately not that easy.

And because the tactics for finding the minimum number of rounds get very complicated very fast (for (P1) and (P2)), we did not even managed it to think about (P3).

I hope you can help us!

Answer 1

I don't know how you got $25$ as the minimum for the original problem. Here is a plan with $24$ races. The race number is given first, with the three runners in parentheses.

1: (1, 2, 3)
2: (1, 2, 12)
3: (1, 4, 5)
4: (1, 6, 7)
5: (1, 8, 9)
6: (1, 10, 11)
7: (2, 4, 6)
8: (2, 5, 7)
9: (2, 8, 10)
10: (2, 9, 11)
11: (3, 4, 9)
12: (3, 4, 10)
13: (3, 5, 12)
14: (3, 6, 11)
15: (3, 7, 8)
16: (4, 7, 8)
17: (4, 11, 12)
18: (5, 6, 9)
19: (5, 6, 10)
20: (5, 8, 11)
21: (6, 8, 12)
22: (7, 9, 10)
23: (7, 11, 12)
24: (9, 10, 12)

To confirm that the conditions are satisfied, the next table lists, for every pair of runners, the races in which both compete. Six pairs of runners face each other twice, and the remainder face each other once.

1 2: 1 2 
1 3: 1 
1 4: 3 
1 5: 3 
1 6: 4 
1 7: 4 
1 8: 5 
1 9: 5 
1 10: 6 
1 11: 6 
1 12: 2 
2 3: 1 
2 4: 7 
2 5: 8 
2 6: 7 
2 7: 8 
2 8: 9 
2 9: 10 
2 10: 9 
2 11: 10 
2 12: 2 
3 4: 11 12 
3 5: 13 
3 6: 14 
3 7: 15 
3 8: 15 
3 9: 11 
3 10: 12 
3 11: 14 
3 12: 13 
4 5: 3 
4 6: 7 
4 7: 16 
4 8: 16 
4 9: 11 
4 10: 12 
4 11: 17 
4 12: 17 
5 6: 18 19 
5 7: 8 
5 8: 20 
5 9: 18 
5 10: 19 
5 11: 20 
5 12: 13 
6 7: 4 
6 8: 21 
6 9: 18 
6 10: 19 
6 11: 14 
6 12: 21 
7 8: 16 15 
7 9: 22 
7 10: 22 
7 11: 23 
7 12: 23 
8 9: 5 
8 10: 9 
8 11: 20 
8 12: 21 
9 10: 24 22 
9 11: 10 
9 12: 24 
10 11: 6 
10 12: 24 
11 12: 17 23

It's easy to see that $24$ races are necessary. To face the other $11$ runners, each runner must compete in at least $6$ races, and we have $$\frac{12\cdot6}3=24$$

Have I misunderstood something?