×

# Need some help with this.

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.

Note by Deeparaj Bhat
10 months, 2 weeks ago

Sort by:

I 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? · 10 months, 2 weeks ago

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? · 10 months, 2 weeks ago

Yes,definitely there is partial credit. Does my solution take into account,the crucial point you are talking about? · 10 months, 2 weeks ago

Yeah, it does. Only after you gave your proof did I realise that I was pretty close to the actual proof.

Once again, thanks for the proof! · 10 months, 2 weeks ago

Hey, @Indraneel Mukhopadhyaya when is your interview for ISI? · 9 months, 3 weeks ago

Did you write the CMI exam? · 10 months, 1 week ago

Comment deleted 10 months ago

Did you get the polynomial and sets question?

How many did you answer overall? · 10 months, 1 week 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? · 10 months, 1 week ago

One more thing, there's no negative marking right? · 10 months, 1 week 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. · 10 months, 1 week ago

The sets and polynomial question you mentioned,were they from objective section or subjective question? · 10 months, 1 week ago

Subjective, both. · 10 months, 1 week 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)? · 10 months, 1 week ago

Last and first are true. The middle two, I don't remember the question. Could you state them? · 10 months, 1 week 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. · 10 months, 1 week ago

My bad, third is true, fourth I don't remember. Second statement also said 'if is differentiable' if I remember, which is true. · 10 months, 1 week ago

Ok,thanks. · 10 months, 1 week ago

What was the fourth one though?

One more thing, no negative marks right? · 10 months, 1 week 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. · 10 months, 1 week ago

Ok.

Then, why'd you leave some objective questions?? · 10 months, 1 week ago