wood burning stoves
The moose likes Programming Diversions and the fly likes For those sporting programmers among you Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of OCA Java SE 8 Programmer I Study Guide this week in the OCAJP 8 forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "For those sporting programmers among you" Watch "For those sporting programmers among you" New topic

For those sporting programmers among you

HS Thomas
Ranch Hand

Joined: May 15, 2002
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.)
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1889
If there are N players then N-1 matches will be required to find the winner.

HS Thomas
Ranch Hand

Joined: May 15, 2002
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.
[ August 22, 2003: Message edited by: HS Thomas ]
HS Thomas
Ranch Hand

Joined: May 15, 2002
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.
Gary Mann
Ranch Hand

Joined: Jun 05, 2003
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

Joined: Nov 09, 2000
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.
I agree. Here's the link: http://aspose.com/file-tools
subject: For those sporting programmers among you
It's not a secret anymore!