35
points
Questions
0
Answers
2
-
- 5710 views
- 3 answers
- 0 votes
-
Answer is “n-1”.
Assumption: question is to find the minimum matches to be played
How:for each match played one team is eliminated. thus in first round, n/2 matches are played.
in second round n/4 are played
.
.
process is continued still one team is left.
so total=n/2+n/4+n/8+….+1
=1+2+4+…+n/2
this is in geometric progression with a=1, r=2, no. of terms =??(say k)for each match played one team is eliminated. thus after first round, n/2 teams are left.
after 2nd round , n/4 teams are left
.
.
after ‘k’th round n/(2^k) teams are left
Now for n/(2^k)=1 team
=>n=2^k
=>k=log(n)
a=1,r=2,k=log n (base 2)total matches = a(r^n – 1)/(r-1)
=2^(log n) -1
=n-1- 8525 views
- 6 answers
- 1 votes