• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

For those sporting programmers among you

 
HS Thomas
Ranch Hand
Posts: 3404
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1898
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If there are N players then N-1 matches will be required to find the winner.
 
HS Thomas
Ranch Hand
Posts: 3404
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic