Extension of a Previously Asked Induction Proof

119 Views Asked by At

This is a very interesting question that I would like to expand on. Induction Proof: Round Robin

It exhibits a proof that shows in certain cases of a tournament where each team plays all others, there is a way of labelling the teams such that we can show Team A beat Team B, Team B beat Team C, and so on.

Say we are now given a /specific/ number of teams to analyze in a tournament, where Team A beating Team B is shown as A -> B.

How would we go about proving that a scenario must exist in which we can number teams such that Team 2 -> Team 3, and Team 1 -> Team 2 & Team 3... and so on. (This clearly depends on the number of teams to begin with). The example in the linked question only addresses the cases of individual matches.

The pattern I have noticed is that we can number these teams in the new method mentioned here for up to the square root of our total teams, subtracting one. So for example, if there are 16 teams, we should be able to guarantee this pattern for at least 3 teams, where Team 2 -> Team 3, and Team 1 -> Team 2 & Team 3...

I believe this is a combination of induction and pigeonhole, but I am not exactly sure where to begin or if the pattern I am observing is incorrect.