Waste less time on Facebook — follow Brilliant.
×

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
4 months, 2 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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? Indraneel Mukhopadhyaya · 4 months, 2 weeks ago

Log in to reply

@Indraneel Mukhopadhyaya 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? Deeparaj Bhat · 4 months, 2 weeks ago

Log in to reply

@Deeparaj Bhat Yes,definitely there is partial credit. Does my solution take into account,the crucial point you are talking about? Indraneel Mukhopadhyaya · 4 months, 2 weeks ago

Log in to reply

@Indraneel Mukhopadhyaya 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! Deeparaj Bhat · 4 months, 2 weeks ago

Log in to reply

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

Log in to reply

@Indraneel Mukhopadhyaya

Did you write the CMI exam? Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

Comment deleted 4 months ago

Log in to reply

@Indraneel Mukhopadhyaya Did you get the polynomial and sets question?

How many did you answer overall? Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat 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? Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya One more thing, there's no negative marking right? Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya 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. Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat The sets and polynomial question you mentioned,were they from objective section or subjective question? Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya Subjective, both. Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat 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)? Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya Last and first are true. The middle two, I don't remember the question. Could you state them? Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat 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. Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya My bad, third is true, fourth I don't remember. Second statement also said 'if is differentiable' if I remember, which is true. Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat Ok,thanks. Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya What was the fourth one though?

One more thing, no negative marks right? Deeparaj Bhat · 4 months, 1 week ago

Log in to reply

@Deeparaj Bhat 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. Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

@Indraneel Mukhopadhyaya Ok.

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

Log in to reply

@Deeparaj Bhat 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. Indraneel Mukhopadhyaya · 4 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...