programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# For those sporting programmers among you

HS Thomas
Ranch Hand
Posts: 3404
A sports club arranges a knockout table tennis competition with 37 entrants. How many matches will have to be played to find a winner ?
First problem : How many matches need to be played.
The volunteer programmer was asked to design an algorithm allocating
players to matches.
An algorithm is needed in case the programmer leaves for paid work elsewhere.
So the number of entrants, x, can vary. (37 was chosen to test the solution as the previous year a statistician calculated the correct number of matches required.)
regards

Arjun Shastry
Ranch Hand
Posts: 1906
1
If there are N players then N-1 matches will be required to find the winner.

HS Thomas
Ranch Hand
Posts: 3404
Can you explain that,though, by way of an algorithm.
The manager isn't going to accept a law of the Universe unless it is backed up by an algorithm. He doesn't believe in common sense either. He has too much riding on that championship and wants everything to go smoothly.
You are correct though. Well done!
You see, the second part of the problem is that if players drop out before their matches are played, matches have to be re-scheduled and entrants have to be matched by their past scores (seeding) which may include matches already played in the championship. A new ruling for knockout championships.
regards
[ August 22, 2003: Message edited by: HS Thomas ]

HS Thomas
Ranch Hand
Posts: 3404
Knockout competitions (process of elimination) work out by powers , in this case, of two.
Taking 37 matches, 5 matches are required for elimination rounds eliminating 5 players to leave 32 players( the closest power of 2) who play 16 matches, 16 who play 8 matches and so on.
5 + 16 + 8 + 4 + 2 + 1 = 36 matches.
I am not sure the above theory works for elimination rounds of 3 people
(powers of 3 ? ).
So Cap, you were right that N players needed N-1 matches.
( Like E=mc2; but bet that bugged some people no end).
I thought it'd be interesting to see it broken down.
regards

Gary Mann
Ranch Hand
Posts: 37
I think you're being too complex with the explanation. If there are N players and only 1 winner, then N-1 players must be knocked out. As 1 player per match is knocked out, N-1 is the answer.

Jason Menard
Sheriff
Posts: 6450
"Gray Man",
Welcome to JavaRanch. We don't have many rules here, but one we do have that we try to enforce is a naming convention. Please change your display name in order to comply with this policy. Thank you very much for your cooperation and enjoy your time here at the Ranch.

 Consider Paul's rocket mass heater.