1

I have got a question Which is as follow:

If there are n participants in a knockout tournament then prove that (n-1) matches will be needed to declare a champion.

If I prove this problem using knowledge of combinatorics then it is not so hard, but the question specifically asks to prove the question by use of principal of mathematical induction. I m stuck here, please help. Any suggestion is heartily welcome.

José Carlos Santos
  • 427,504
Vidyanshu Mishra
  • 10,143
  • 1
    We don't need induction for this: Each performed match will "knock out" exactly one participant. Therefore $n-1$ matches are necessary and sufficient to find a champion out of $n$ participants. – Christian Blatter Nov 10 '16 at 19:40
  • @ChristianBlatter, I know but the question specifically ask for a proof using induction. – Vidyanshu Mishra Nov 10 '16 at 19:42

2 Answers2

2

The base case is trivial.

Now assume that in a knockout tournament with $k$, $k \le n $ people, $k-1$ matches are needed to declare a champion. We now prove that if the tournament has $n+1$ people, $n$ matches are needed:

Say you are about to dispute the final. That is, 2 players, $A $ and $B $ are about to play the last match to determine the winner. Then we know that $A $ was the winner of some sub-tournament with $a, a \le n$ people and $B $ won a sub-tournament with $b, b \le n$ people. We also know that $a + b = n+1 \iff b = n+1-a$. But $A $ was declared victorious of his sub-tournament after $a-1$ games and $B $ of his after $b-1 = n+1-a-1$ games. That is, it took a total of $a-1+n-a = n-1$ games to determine the two contenders. We play one final match, and we get $n-1+1 = n $ matches to determine the winner.

RGS
  • 9,719
2

Yes, you can use induction on $n$ to prove:

$P(n)$: If there are $n$ participants in a knockout tournament, then $(n-1)$ matches will be needed to declare a champion.

Base case(s): Is $(P(1)$ true? Sure: $P(1)$ If there is only one team ($n=1$), then no matches are needed $(n-1 = 1-1=0),$ because by default, the one team that showed up for the tournament is the champion.

$P(2)$ : If there are $n=2$ teams, then ($(n-1)= 2-1 =1$) matches are needed to determine a champion. Of course, exactly one match (team A vs team B) is needed to determine the champion.

Assume $P(n)$ is true.

Now show that, given $P(n)$, $P(n+1)$ must therefore hold, meaning the following must be proven true, given $P(n):\;\;$

"If there are $n+1$ teams, then $((n+1) - 1)= n$ matches are needed to determine the champion.

amWhy
  • 209,954