How do we solve the following problem?

There are \(n\) players participating in a sports tournament. Each player plays with every other player and each game ends in a win for one of the players (no draws). Prove that the players can be arranged in the following sequence: \[P_1, P_2, P_3, \ldots , P_n\] where, player \(P_i\) has beaten the player \(P_{i+1} (i=1,2,3, \ldots , n-1)\) in at least one game.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI think, I have got a reasonable proof.I will be using induction.Consider the base case of two players.In two players, there will be a winner and a loser, so we can definitely form the sequence.Now,assume that we can form the given sequence for k players.So, we have the sequence P1,P2,P3,.........,Pk.We must now show that it is always possible to insert P (k+1) somewhere between the gaps of Pi (i=1,2,3.......,k).We know that P (k+1) will play exactly k games with each of P1,P2,......Pk.So,there will be k outcomes,where each of outcome is win (W) or lose (L).So,we consider the string of k letters where each letter is L or W.If at,say r(th) position,there is W,then it means that P (k+1) defeated Pr.Now,if first letter of the string is W,then P (k+1) will precede P1.Now,consider that the first letter of the string is L.If second letter is W,then P (k+1) comes between P1 and P2.Suppose second letter is L.Now,if third letter is W, then P (k+1) comes between P2 and P3.This logic can be extended,so as to get that,we can always find a consecutive L and W, if not, every letter of the string will be L.In that case P (k+1) will succeed Pk.So,it has been shown that it is always possible to form a sequence with (k+1) players.So,the question has been proved using induction.Does this solution seem fine?

Log in to reply

Hmm... This seems fine. It resembles the proof I'd written in the exam very much (but I missed one crucial point in my written proof 😣).

Btw, is there partial credit?

Log in to reply

Yes,definitely there is partial credit. Does my solution take into account,the crucial point you are talking about?

Log in to reply

Once again, thanks for the proof!

Log in to reply

@Indraneel Mukhopadhyaya

Did you write the CMI exam?

Log in to reply

Hey, @Indraneel Mukhopadhyaya when is your interview for ISI?

Log in to reply