0

Here is the word problem:

There is a tournament where teams compete against each other exactly once, and determine the winner. Show that the teams can be lined up in such an order, that each won against its immediate neighbor on the right side.

My question is: does the following flowchart represent a valid solution?

Induction: if $n=1$ the sequence trivially has the desired property. Now assume, we have $n$ teams which already form a sequence with the desired property, and we also have the $(n+1)^{th}$ team at hand, then:

Induction via flowchart

And two questions with my attempts to answer them:

Is the sequence unique?

No. Counterexample: Say, we have 3 teams, and 1st won against the 2nd, 2nd won against the 3rd, 3rd won against the 1st. Then the sequence 1,2,3 has the desired property, and so does the sequence 3,1,2.

Does it represent a "fair" ranking?

I guess the question basically means whether the relationship "$a$ won against $b$" is transitive. And the answer is no. A counterexample would be 3,1,2 from the previous question.

Leo
  • 7,670
  • 5
  • 31
  • 63

1 Answers1

1

Your flowchart is correct (except that you have to put the $(n+1)^{th}$ on the left of the first not in front ;-). If you have to justify you can separate the cases where the $(n+1)^{th}$ become first or last (easy to show correct) and the case where he is inserted at the $i^th$ position (show it correct with the relation you know with i-1 and i+1.

Your counterexample is also correct.

And for the "fair" ranking, I'm not sure what it means ... But explanation make sense and your answer is again correct :)

wece
  • 2,732