Author |
Topic: Round-robin Tournament (Read 340 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Round-robin Tournament
« on: Jul 18th, 2007, 2:35pm » |
 Quote  Modify
|
Jill plays in an all-play-all (once) tournament. In each game, a player earns 2 points for a win, 1 point for a draw, and none for a loss. After the tournament Jill tells Jack (who was not there) how many points she earned. If Jill scored m points and there were n players in the tournament (including Jill), find in terms of n and k the smallest value of m such that Jack can deduce that Jill scored more points than at least k other competitors.
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Round-robin Tournament
« Reply #1 on: Jul 19th, 2007, 2:34pm » |
Quote Modify
|
Numerical example: let there are 12 players in the tournament, including Jill. Prove that Jill must have earned at least 19 points if Jack can deduce that Jill scored more points than at least 8 other competitors.
|
| « Last Edit: Jul 19th, 2007, 3:42pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Round-robin Tournament
« Reply #2 on: Jul 19th, 2007, 2:58pm » |
Quote Modify
|
I'll go with m=(n*(n-1) -k*(k-1))/(n-k) for now.
To get as few people she beats as possible, you try to get as many as possible with the same score. But the 'loser section' can't have no points: they can't always lose, they play each other as well. k losers have at least k*(k-1) points together.
|
| « Last Edit: Jul 19th, 2007, 3:01pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Round-robin Tournament
« Reply #3 on: Jul 21st, 2007, 7:19pm » |
Quote Modify
|
Your expression simplifies to n+k-1, which is correct.
However, for a rigorous proof we must show that it is possible for Jill to score n+k-2 points while beating at most k-1 other competitors, and also that if Jill scores n+k-1 points then she must have scored more points than at least k other competitors.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print