Scheduling players in a team so that every player plays the same amount of time

Question

I've been asked the following question:

You are a basketball team manager, and the team consists of $8$ players. Every moment, exactly $5$ players have to be on the field. Given that a game duration is $40$ minutes, design a scheduler so that every player plays the same amount of time.

My approach is the following: we know that each player has to play exactly $\dfrac{5 \cdot 40}{8} = 25$ minutes.

Thus I could match players to the minutes they play using graph-matching. In this case, there are $8$ nodes for the players and $40$ nodes for the minutes. Every player node has an edge to all the minutes nodes with capacity of $1$. the capacity from the source to the player nodes is $25$. The capacity from the minutes nodes is $5$.

I think my solution works for this case, however if I change the parameters of the problem, I may not find a solution using graph matching. The downfall might be in the distribution of time, i.e. looking at the time in a different resolution, e.g. $10$ seconds instead of minutes. In this case I'd have $6\cdot40=240$ time nodes. Is there another algorithm for this problem, or how could I find the right time resolution?

Answer 1

Here there is a straightforward solution:

Player 1 plays 0-25minutes Player 2 plays 0--20 minutes and comes back in at 35 minutes Player 3 plays 0--15 minutes and comes back in at 30 minutes Player 4 plays 0--10 minutes and comes back in at 25 minutes Player 5 plays 0--5 minutes and comes back in at 20 minutes Player 6 plays 5--30 minutes Player 7 plays 10--35 minutes Player 8 plays 15--40 minutes

Check to see that 5 players start and every 5 minutes one person comes out and another comes in.

In general, if you want to construct a bipartite graph with $M$ vertices $x_0,\ldots, x_{M-1}$ on left side, $N$ vertices $y_0,\ldots, y_{N-1}$ on the right, with $M|N$, and where every vertex on the left has degree $k$ and every vertex on the right has the same degree, put an edge between $x_i$ and every vertex of the form $y_{\frac{N \times i}{M} + j}; \ j=0,1,\ldots, k-1$; arithmetic done mod $N$.

Getting back to your problem: Here the number $M=8$ of players divides $N=40$ the number of minutes. This would hold even if you insisted on 5-minute intervals where there would be $N'=\frac{40}{8}$ 5-minute intervals; here $M|N'$ still.

1. Can you generalize to 48-minute games with 12 players.

2. What if: Instead you had instead 12 players and 40 minutes [12 doesn't divide 40]. Could you break into $40 \times 3$ 20-second intervals.

Answer 2

Use eight consecutive $5$-minute periods instead of $4$ quarters and choose any five-player team $K_1$. List all $8$ players as vertices of a regular octagon and to period $i+1$ assign the team $K_{i+1}$ obtained by rotating team $K_{i}$ by $45$ degrees.