I have just started with mathematical induction please help me to understand in easy way : There are $n$ players in a match. How do I prove that total number of knockout matches will be $n-1$ to decide the winner.Or help me to understand following attachment.enter image description here

  • $\begingroup$ "knockout matches" implies to me an elimination tournament system. In which case the number of knockout matches will be $ log_2(n) $ $\endgroup$ – Q the Platypus Apr 1 '16 at 3:33
  • 1
    $\begingroup$ @QthePlatypus that is not true. in any tournament, if there is one winner, then $n-1$ players must be eliminated, and since no two players can be eliminated in the same match, there must be $n-1$ elimination matches $\endgroup$ – ASKASK Apr 1 '16 at 4:00

I have no idea how mathmatical induction comes into play here.

To answer your question though, if you consider $n$ player it will take $n-1$ matches for a tournament in elimnation style (only the winner keeps playing) because one person looses the tournament per match played.

If just one person wins you need the other $n-1$ to loose one match and therefore it takes $n-1$ matches to be played in total.

Maybe you could do it the following way:

$A(n)$: For a elimination tournament with $n$ players you need $n-1$ matches ; $n \in \mathbb{N}$ and $n \geq 2$

Induction Base: we show $A(2)$ which is trivial because 2 players need to play 1 match and therefore $A(2)$ holds.

Induction step: we consider $A(n)$ holds for one $n \in \mathbb{N}$. Now we look at the case $A(n+1)$ - The torunament follows the same rounds as in $A(n)$ - the new player will need to loose one match before he drops out, if he never does one of the other $n$ players will loose it - for both cases we need to have one more match. Therefore the ammount of matches is $(n-1)+1=n$

But this seems way too inconsistent for me - i am curious if there is a better way too show it through mathmatical induction although the idea above makes a alternate proof pretty short.

  • $\begingroup$ Now I have added solution form book, help me to understand this. $\endgroup$ – mnulb Apr 1 '16 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.