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.

## 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? – Indraneel Mukhopadhyaya · 1 year, 1 month ago

Log in to reply

Btw, is there partial credit? – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

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! – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

Hey, @Indraneel Mukhopadhyaya when is your interview for ISI? – Deeparaj Bhat · 1 year ago

Log in to reply

@Indraneel Mukhopadhyaya

Did you write the CMI exam? – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

Log in to reply

How many did you answer overall? – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

No.I could not solve that.My overall performance was not satisfactory.I could solve 8 objective questions.In the subjective section,I could solve first 3 questions completely and first two parts of the fourth question.How was your performance?Log in to reply

– Deeparaj Bhat · 1 year, 1 month ago

One more thing, there's no negative marking right?Log in to reply

– Deeparaj Bhat · 1 year, 1 month ago

I solved all except the two I've already mentioned. I've solved the third sub question on the sets one, and half of the second sub division of the sets one.Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

The sets and polynomial question you mentioned,were they from objective section or subjective question?Log in to reply

– Deeparaj Bhat · 1 year, 1 month ago

Subjective, both.Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

Ok.Could you tell me the answer of the "set" question (the one which had slopes of tangents and secants)in the objective part (true-false)?Log in to reply

– Deeparaj Bhat · 1 year, 1 month ago

Last and first are true. The middle two, I don't remember the question. Could you state them?Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

Second statement said that 'set of slopes of secants' is a subset of 'set of slopes of tangents'.Third statement said that if 0 and 1 are present in set of slopes of secants,then every number between 0 and 1 should also be present in the set of slopes of secant.How did you get the last statement true?I got it false.Log in to reply

– Deeparaj Bhat · 1 year, 1 month ago

My bad, third is true, fourth I don't remember. Second statement also said 'if is differentiable' if I remember, which is true.Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

Ok,thanks.Log in to reply

One more thing, no negative marks right? – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

The fourth statement said that if tangents and secants of any possible real slope can be drawn to f,then f must be differentiable everywhere.As for negative marking,I think there is no negative marking as nothing about it was mentioned in the instructions.Log in to reply

Then, why'd you leave some objective questions?? – Deeparaj Bhat · 1 year, 1 month ago

Log in to reply

– Indraneel Mukhopadhyaya · 1 year, 1 month ago

As I said I have done 8 objective questions.I have left only one question (it had integer answer and I did not know the correct answer),the other one was true-false that I have attempted,(simply for the sake of not leaving it) and do not know if it is correct.Log in to reply