So i was given this question. There are 11 teams in a league. Each team can play against the other team only once. Show that there are always two teams who played exactly the same number of games.

My attempted solution. (based it off an example that was different but also slightly similar)

In a league with two divisions of 11 teams each there is no schedule with each team playing a game with each team in each division. In the language of graph theory, the scheduled games can be viewed as edges with 11 vertices. We are asking for a graph that is regular of degree 11, but we are also asking for the subgraph induced by the 11 teams in one division to be regular of degree 1. Since 1 and 11 are both odd, this is impossible, because every graph has an even number of vertices of odd degree.

We are working on graph theory but I have an assumption that this can be done by pigeon hole principle. I'm slightly confused on how to go about the graph theory method

  • $\begingroup$ Hmmm, there is a lot of confusing language in your solution. Some examples are 1) "In a league with two divisions of 11 teams": why do you think there are 22 teams in a league? 2) "edges with 22 vertices": no, an edge has 2 vertices, you probably mean "edges on a graph with 22 vertices". 3) "regular of degree 11": not true, you were probably misled by "only once", which means "$\le 1$", not "$= 1$". $\endgroup$ – Erick Wong Mar 22 '16 at 16:04

There is only one division.
The possible numbers of opponents is $0,1,2,3,4,...,10$. Can the eleven numbers all be different?

  • 1
    $\begingroup$ Yep, 10 and 0 are incompatible! $\endgroup$ – Darío G Mar 22 '16 at 16:05
  • $\begingroup$ like @Wore said so we can conclude just based off that assumption that there are always two teams that have played the same number of games? $\endgroup$ – Donald Mar 22 '16 at 16:06
  • $\begingroup$ @Michael so just use pigeon hole, state the fact that you and wore presented and conclude that it is possible that always two teams played same number of games? $\endgroup$ – Donald Mar 22 '16 at 16:50
  • $\begingroup$ @Donald This is rather a setup for a contradiction. Suppose that all teams played a different number of games, and you run into a contradiction. Therefore, there must always exist two teams who played the same number of games. $\endgroup$ – Manuel Lafond Mar 22 '16 at 20:08
  • 1
    $\begingroup$ @Donald First, let $m_1,\ldots,m_{11}$ be the list of the number of games played by each team. Note that it is impossible that 0 and 10 are both numbers in the list (because that would mean that there is a team that does not play, and another team that play against everybody, but both things cannot happen at the same time!). So, we have two cases depending on whether 10 appears on the list or not, but in any of the cases we have that $m_1,\ldots,m_{11}$ is a list of 11 numbers (pigeons) each of which can take one of 10 values (holes). $\endgroup$ – Darío G Mar 22 '16 at 21:39

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.