At my local squash club, there is a ladder which works as follows.
- At the beginning of the season we construct a table with the name of each member of the club on a separate line.
- We then write the number of games won and the number of games played next to each name (in the form: player wins/games).
Thus at the beginning of the season the table looks like this:
Carol 0/0 Billy 0/0 Alice 0/0 Daffyd 0/0
Any two players may play a match, with one player winning. If the player nearest the bottom of the table wins, then the position of the players is switched. We then repeat step 2., updating the number of wins and games next to each player. For example, if Alice beats Billy, we have
Carol 0/0 Alice 1/1 Billy 0/1 Daffyd 0/0
These matches go on throughout the season and eventually result in players being listed in approximate strength order.
Unfortunately, the updating happens in a rather haphazard way, so mistakes are made. Below are some examples of invalid tables, that is, tables which could not be produced by correctly following the above steps for some starting order (we have forgotten the order we used at the beginning of the season) and sequence of matches and results:
Alice 0/1 Billy 1/1 Carol 0/1 Daffyd 0/0 Alice 2/3 Billy 0/1 Carol 0/0 Daffyd 0/0 Alice 1/1 Billy 0/2 Carol 2/2 Daffyd 0/1
Given a table, how can we efficiently determine whether it is valid? We could start by noting the following:
The order of the names doesn't matter, since we have forgotten the original starting order.
The total number of wins should be half the sum of the number of games played. (This shows that the first example above is invalid.)
- Suppose the table is valid. Then there is a multigraph - a graph admitting multiple edges but no loops - with each vertex corresponding to a player and each edge to a match played. Then the total number of games played by each player corresponds to the degree of the player's vertex in the multigraph. So if there's no multigraph with the appropriate vertex degrees, then the table must be invalid. For example, there is no multigraph with one vertex of degree one and one of degree three, so the second example is invalid. [We can efficiently check for the existence of such a multigraph.]
So we have two checks we can apply to start off with, but this still allows invalid tables, such as the third example. To see that this table is invalid, we can work backwards, exhausting all possible ways the table could have arisen.
I was wondering whether anyone can think of a polynomial time (in the number of players and the number of games) algorithm solving this decision problem?