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.
No comments:
Post a Comment