# 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
2 years, 6 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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?

- 2 years, 6 months 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?

- 2 years, 6 months ago

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

- 2 years, 6 months 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!

- 2 years, 6 months ago

- 2 years, 5 months ago

Did you write the CMI exam?

- 2 years, 6 months ago

Comment deleted May 19, 2016

Did you get the polynomial and sets question?

How many did you answer overall?

- 2 years, 6 months 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?

- 2 years, 6 months ago

One more thing, there's no negative marking right?

- 2 years, 6 months 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.

- 2 years, 6 months ago

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

- 2 years, 6 months ago

Subjective, both.

- 2 years, 6 months 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)?

- 2 years, 6 months ago

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

- 2 years, 6 months 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.

- 2 years, 6 months ago

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

- 2 years, 6 months ago

Ok,thanks.

- 2 years, 6 months ago

What was the fourth one though?

One more thing, no negative marks right?

- 2 years, 6 months 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.

- 2 years, 6 months ago

Ok.

Then, why'd you leave some objective questions??

- 2 years, 6 months 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.

- 2 years, 6 months ago