Mathematical Induction on sports

69 Views Asked by At

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

1

There are 1 best solutions below

1
On

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.