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.
On
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.
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.