Timeline for Optimal schedule for a soccer tournament
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2023 at 17:11 | comment | added | David E Speyer | @HenrikRüping Nice! You should post that as an answer. | |
| Apr 25, 2023 at 15:47 | comment | added | HenrikRüping | By the way, the analogous strategy for even $n$ gives ga maximal waiting time of $n+O(1)$. Here you pick one of the $2k+2$ players that always plays against the one sitting at the end of the table. Then just play all games in one round from one end of the table to the other and repeat with the next round. | |
| Apr 25, 2023 at 15:03 | comment | added | Peter Taylor | Aha! Looking at the deltas for each team there's a fairly straightforward pattern. Need to prove it works, but empirically it gives a solution for odd $n$ up to $n=25$. | |
| Apr 25, 2023 at 14:02 | comment | added | Peter Taylor | Odd $n$ seems to be harder because there's less margin between min and max. Up to relabelling of the teams there's one solution for $n=3$ and two each for $n \in \{5, 7\}$. If there's a pattern which can be extrapolated to larger odd $n$ then I haven't yet seen it, but feel free to try. Data at gist.github.com/pjt33/b055e3d5c87478d73bde7b5199b9f91a | |
| Apr 25, 2023 at 13:27 | history | edited | David E Speyer | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 25, 2023 at 13:25 | comment | added | David E Speyer | @HenrikRüping Yup, that's how I visualized it! But, in the chess setting, it makes sense to play $k$ games at once. In this problem, you have to figure out which order the $k$ games should be played in for each seating. My intuition is that, if you are smart about this, you can get the longest wait to be $k+O(1)$, but I always wound up with a $2k$ wait somewhere, so I decided to just post what I had. | |
| Apr 25, 2023 at 12:13 | comment | added | HenrikRüping | This strategy can be visualized quite beautifully by turning the soccer tournament to a chess tournament. Suppose you have a long table with k chessboards. Then the 2k+1 players are placed around the table, the one extra player sits at the end of the table. Then after each round everybody gets up and moves one board to his/her left. When all players are back in their starting positions, everybody has played everybody else exactly one. | |
| Apr 25, 2023 at 11:16 | history | answered | David E Speyer | CC BY-SA 4.0 |