Permutation and Combinations

[Tania123]

There are n players in a elimination type singles tournament. How many matches must be played( or defaulted) to determine the winner?

a) n+1
b) n-1
c) n-2
d) n+2
e) n

The answer is b) n-1

[Mauli]

In each match a player wins and the other loses. the losing player is out of the tournament. Thus eliminating one player in every match of the tournament. And the winner gets one step closer to win the tournament.
 just take an example. say n=3 and players are x, y z.

1st match : x and y              x wins , y loses and is out of the game
 2nd match: x and z             x wins , z loses.
 the winner of the tournament is x. When n=3. matches played are 2 ie:(n-1).
 

[Dr. Strange]

T(n)= no. of matches to be played for n players
T(1)= 0 ,T(2)=1,T(3)=2
T(2)-T(1)=1
T(3)-T(2)=1

Now if n is even, we can see
T(n) = n/2 + T(n/2)
Now if n is odd, we can see
T(n) = (n-1)/2 + T((n+1)/2)

Now we can prove by mathemathical induction that T(n)-T(n-1)=1

Suppose upto n-1 terms ,it follows that T(k)-T(k-1)=1  

If n is even =2k
T(n) - T(n-1)= n/2 + T(n/2) -[(n-2)/2 + T((n-1+1)/2)]      { since n is even,n-1 is odd }
= 1 always

If n is odd  =2k + 1
T(n) - T(n-1)= (n-1)/2 + T((n+1)/2) - [  (n-1)/2 + T(n-1/2)]    { since n is odd,n-1 is even}
=  T((n+1)/2)- T(n-1/2)
replacing n by 2k+1,
=T(k+1) - T(k)

since upto n-1 terms it follows T(k)-T(k-1)=1 and k<n-1   so T(k+1)-T(k)=1


Hence proved by mathematical induction that T(n+1) - T(n)=1

This is an AP with a=0 since T(1)=0
Hence T(n) = n-1