Received this in the mail...
I'm not sure if this should be posted here but would like to see if one of our speedy mathematician's come up with the same answer as I:

There are 100 golfers in the local tournament. If a player loses a match, he is immediately eliminated from the contest.

How many matches will be played to determine one winner?

Please show winners by each round.

99.

You don't mention it in your question, but I'm assuming that each match is 1 on 1, right? Otherwise, you can have only 1 match with all 100 players, and the lowest scorer will be the only winner.

It doesn't matter how each round is arranged. If there are 100 players then in order to have one winner, there have to be 99 losers. Since each player is kicked out after losing only once, that's one loss for each loser (i.e. no loser can come back and lose a second time). Hence, 99 losers = 99 losses = 99 games played.
***************************************************
06-15-03, 07:49 PM
Di
Right, one on one. But- How many rounds total and how many winners in each of them???

06-15-03, 09:34 PM
maiku
FH's method was ingenious. If you work it out by hand, you get 50 players remaining after the first round, then 25, 12 (13), 6(7), 3(4), 2, 1, for a total of seven rounds with the winners (including necessary byes after each round) as above.

Here is a more formal way of stating the problem, assuming the 1-1 matching. For any number of original players, n, the number of matches is n-1, as in FH's approach above. The number of rounds necesssary will be the number of times n is divisible by 2 with a remainder greater than or equal to 1, and this can be expressed (where R is rounds and [x] is the so-called ceiling function, that is, the integer x if x is an integer and x+1 where it is not) as:

R = [log2 n]

The number of winners in each round, i, is given by

W(i) = [n/(2i)]

06-15-03, 10:49 PM
maiku
Correction: I misstated the definition of the ceiling function above. Where x is an integer, then éxù (which is the notation I should have used in the first place for this ceiling function) is the integer x. Where x is not an integer, what I meant to say was that éxù is the integer part of x plus 1.

With reference to the problem you gave, Di, that means that, for a tournament with 100 players, the number of matches is 99, as before, and the number of rounds is 7, since this is equal to the ceiling function of log2 100 (approximately 6.64).

A more familiar application of all of the above has to do with the NCAA Basketball tournament, to which, in the past, exactly 64 teams were invited. Since 64 is a power of 2 (26, in fact), the ceiling function can be dropped from the equations I gave above, and there do not need to be any byes in the matches. There are 63 of these, in 6 rounds, with the winners after each round being 32, 16, 8, 4, 2, and 1, a fact which is familiar to everyone.

[This message was edited by maiku on 06-15-03 at 11:15 PM.]

06-16-03, 01:17 PM
FlyingHellfish
Maiku gave an excellent mathematical analysis of how to determine the number of rounds that need to be played, which in this case is 7. Note that it would require only 7 rounds with anywhere from 65 to 127 entries, and only 8 rounds from 128 to 255 entries. Assuming there is at most 1 bye per round (which only occurs if there is an odd number of players remaining), then Maiku's analysis will always be correct.

06-16-03, 03:28 PM
Di
Here's what I came up with:

Round 1 50 matches to get 50 winners

Round 2 25 matches to get 25 winners

Round 3 12 matches for 12 winners, one person would have to wait to play again.

Round 4 12 matches for 6 winners

Round 5 3 matches for 3 winners

Round 6 2 matches for 2 winners - the player left out of Round 3 would play to make it even.

Round 7 2 players left would play for the championship.

50+25+12+6+3+2+1 = 99
Round


06-17-03, 08:30 PM
gerry
FH's answer was an incredible accomplishment. Maiku's was super-genius. But all in all, I like Di's the best, just crunch it out the old fashioned way!

06-17-03, 10:02 PM
Di
Right Gerry- I won't even try to compete with Maiku or Flyinghellfish!

More work but I do tend to go for the old fashioned system. Thanks

06-18-03, 02:22 AM
maiku
Please note, Di and gerry, that in my first reply to Di's question I calculated the answer using the very same method she did, with identical results.

I went on to derive the equations I did only for the sake of formalizing the algorithm which she herself used, and generalizing it, so that it could be made to apply to any number of entrants in a tournament of the sort her question presupposes.

FH's approach was truly insightful, and I didn't see it at first myself. My own "analysis," as FH called it, very far from being "super-genius," was just the quite ordinary, work-a-day thing that a mathematician does when he (or she) attempts to formalize and generalize some calculation process. Wink

06-18-03, 02:39 AM
Di
Hi Maiku-
I understand that, no problem. I broke it down as I did as with an accounting background I'm just used to showing all the little detail work.

This message has been edited. Last edited by: DorianGreyed,