3
$\begingroup$

An amateur football coach wants to train the players by dividing them into two team and having the teams play each other. However, because of time constraints, each player comes and leaves at a different (known in advance) point of time that day. The coach wants that at any point of time, the teams are of equal size, or when the number of players is odd, the sizes differ only by one. Is this always possible?

A player gets assigned a team immediately on arriving, and this assignment cannot be changed. Each player comes and leaves exactly once.

Example:
Player 1: 16:00–17:45
Player 2: 16:15–17:00
Player 3: 16:30–17:30
Player 4: 16:45–17:15
Assignment: Team 1: Players 1 and 4, Team 2: Players 2 and 3.
Then, at any point of time the difference in team sizes is at most one, so this is a correct assignment.

I have a solution for the puzzle, but it is fairly complicated; I guess it would take at least 5–10 minutes to verify that the solution is indeed correct. Since the puzzle seems simple, I'm looking for a simple solution that can be quickly seen to be correct. To make it a little more interesting, I'll not state what the correct answer is.

Minor hint:

It does not matter whether it is allowed that two players arrive at exactly the same point of time; the answer is the same.

$\endgroup$
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Oct 22 '17 at 1:29
  • $\begingroup$ The solution by Gareth McCaughan is correct but not as simple as I hoped, so I wanted to keep the question open for now. $\endgroup$ – Falk Hüffner Oct 22 '17 at 18:15
5
$\begingroup$

The answer is that it

is

always possible to assign teams as required. Explanation:

Call each arrival or departure an "event". Write down all the event times in chronological order. Whenever an even number of events has occurred, the team sizes are (1) of the same parity and (2) at most 1 apart, so they must be exactly equal. So if the two events between two of these times are both arrivals or both departures, they must happen from different teams; if they are one of each, they must happen to the same team.

Now

these constraints are the only ones: that is, if we can satisfy them then we are OK at all times (because at the intermediate times we have added or removed just one player, relative to a situation where both teams were of equal size).

So

draw a graph (in the "network" sense, not the "plot of a function" sense) with one vertex per player, and join two players' vertices by a red edge if as above their adjacency requires them to be on different teams, by a blue edge if their adjacency requires them to be on the same team, and otherwise don't join them at all. Every player arrives once and leaves once, and hence each vertex has degree 2. (In the degenerate case where a player arrives in event 2n+1 and leaves in event 2n+2, we have a single edge from that player's vertex to itself, which therefore has degree 2 despite only a single edge!) Such a graph necessarily consists of some number of cycles of various lengths.

In each of these

we can try to assign teams in the obvious way: pick a colour for one vertex and then walk around the cycle, changing colour when we traverse a red edge and not when we traverse a blue edge. Everything will work out if and only if the number of red edges in each cycle is always even. Must that be so? Well, now annotate the two ends of each edge with "A" or "D" depending on what the player at that end is doing in the corresponding event-pair. As we walk around our cycle, we encounter a sequence of As and Ds; across each vertex we switch from A to D or vice versa (because each player arrives once and departs once); along a red edge we have AA or DD; along a blue edge we have AD or DA. Clearly, going around the whole cycle we switch an even number of times. So the number of blue edges has the same parity as the number of vertices (because those are the things that make us switch). Since we have the same number of edges as vertices around a cycle, this means that the number of blue edges has the same parity as the number of edges, and hence the number of red edges is even, so we're done.

This all works but maybe it takes that same 5-10 minutes to verify that it's correct. It seems like it may be possible to streamline it; I will have a go and update this answer if I find a way to make it much neater.

$\endgroup$
  • $\begingroup$ I think this solution is already quite elegant (and maybe even a bit unexpected). The condition for a graph to be bipartite is for there not to be any odd cycles, so I don't think you can get away with not proving that (at least indirectly). Alternatively: every cycle has an even number of As and Ds - blue edges have one of each, so the reds also have to cover an equal number of each: this means for every AA red edge, there has to be a DD one. $\endgroup$ – ffao Oct 10 '17 at 1:06
  • $\begingroup$ This is basically the same solution that I have (drops.dagstuhl.de/opus/volltexte/2011/3041/pdf/49.pdf Theorem 2). It seems mathematically elegant, but hard to verify in particular for people not familiar with concepts like bipartite graphs. Since this is a constructive solution, I was in particular hoping there might be an easier nonconstructive argument for the existence of a solution. $\endgroup$ – Falk Hüffner Oct 10 '17 at 7:12
  • $\begingroup$ I'm not surprised to find that your solution is similar to mine. It seems like this is the "obvious" solution, meaning the one you get to if you just keep doing the simplest thing that might solve the problem, and while it still seems possible to me that there might be some slicker "team = parity of X" way to express the result I think any proof along these lines is going to be about this painful. (But yes, there could be a neater nonconstructive one.) $\endgroup$ – Gareth McCaughan Oct 10 '17 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.