2

Well it's a problem me and my friend had thought of, and well, haven't come up with anything to solve the following problem(I'll try to phrase it in the best way I can):

Given that there are n number of teams, and the number of matches each team has played, and that no team can play more than 2 matches with any other team, predict if the distribution of matches played by each team is possible.

P.S. : I am a Python Programmer, so (if possible) post only python code for explaining..

pradyunsg
  • 245
  • 2
  • 12
  • What tournament format? Single elimination, double elimination, Round Robin? – John R. Strohm May 04 '13 at 15:55
  • @JohnR.Strohm Round-Robin if you notice, the conditions are like that of [IPL](http://en.wikipedia.org/wiki/Indian_Premier_League) – pradyunsg May 04 '13 at 15:58
  • The input is only the number of games played by each team? No info about the opponent? Is there any condition about the teams having to play all at a certain time simultaneously (like on Saturdays)? – Thomas May 04 '13 at 17:47
  • @Thomas Yes, only 1 input. No info. No, in fact I was also thinking that if the combination is possible, generating a schedule for 1 match a day could be possible, but that's for my next question.. – pradyunsg May 04 '13 at 18:10

1 Answers1

1

This is a nice exercise in constraint propagation and combinatorics. Here are some ideas:

  • Clearly there are result distributions which are impossible. For instance, the total number of of wins must equals the total number of losses, and the total number of draws must be an even number.
  • If you draw up some example distributions by adding up actual results, you will start noticing more regularities. Each of those is another criterion for proving that a given distribution is impossible.
  • Showing that a distribution is possible is a little harder. The most direct proof is to give a concrete example of results which would result in the distribution you are given..
  • If you can't manage to construct one, the most straightforward algorithm to decide if there is one is to enumerate all possible pairings and see whether they fit. For instance, starting with the top-ranked team, you can conduct a complete search: have they won, lost, tied, or not yet played against the second-ranked team? (You said that there are return games, so this decision has to be made twice, but that doesn't change the basic idea of a complete search.) Either you find a matching configuration of results, or you have proved that there isn't one.
  • A complete search is expensive, but there are various constraints that you can use to prune the search space. For instance, you cannot assume more wins for a team than the input said they have, and the assumption of how A played against B must confirm to what you assume about B vs. A.
Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • We don't know how many matches a team has won/lost/drawn, and we don't care about it, it is just that the team has played `x` matches.. || Given the number of matches each team has played, determine if that combination is possible.. || – pradyunsg May 04 '13 at 18:08