Author |
Topic: tennis competition (Read 970 times) |
|
gert1
Guest
|
Please help and my collegue with this puzzle:
[b][/b]You are asked to make a tennis match schedule for 9 persons. They play doubles, so each round one person is spare for fetching balls. The first round may be: 1-2 vs 3-4 and 5-6 vs 7-8. There is one problem: every round you have to switch partners and opponents, so that every combination occurs only once and every opponent is only met twice during the tournament of 9 rounds. E.g. If you are player 1 you play with nr 2 once and against him twice (with different partners).
The question is: can you make the schedule or prove that this is impossible. What is then a sub-optimal schedule (best mix of opponents)?
Next question: expand to 12 players (with 11 rounds), 13, 16, 17 (17 rounds) players and so on.
|
| « Last Edit: Jan 29th, 2004, 4:53pm by Icarus » |
 IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Re: new riddle: tennis competition
« Reply #1 on: Jan 28th, 2004, 11:35pm » |
 Quote  Modify
|
I don't think it's possible for 9 players in 9 rounds.
Here's a solution for 8 players in 7 rounds:
Round 1 -- 1 and 2 vs 3 and 4 5 and 6 vs 7 and 8
Round 2 -- 1 and 3 vs 5 and 7 2 and 4 vs 6 and 8
Round 3 -- 1 and 4 vs 5 and 8 2 and 3 vs 6 and 7
Round 4 -- 1 and 5 vs 2 and 6 3 and 7 vs 4 and 8
Round 5 -- 1 and 6 vs 3 and 8 2 and 5 vs 4 and 7
Round 6 -- 1 and 7 vs 4 and 6 2 and 8 vs 3 and 5
Round 7 -- 1 and 8 vs 2 and 7 3 and 6 vs 4 and 5
And for 12 players in 11 rounds, each round containing 3 matches:
[ab | ce] [hi | kd] [jg | lf]
[ac | df] [ij | le] [kh | bg]
[ad | eg] [jk | bf] [li | ch]
[ae | fh] [kl | cg] [bj | di]
[af | gi] [lb | dh] [ck | ej]
[ag | hj] [bc | ei] [dl | fk]
[ah | ik] [cd | fj] [eb | gl]
[ai | jl] [de | gk] [fc | hb]
[aj | kb] [ef | hl] [gd | ic]
[ak | lc] [fg | ib] [he | jd]
[al | bd] [gh | jc] [if | ke]
The above are examples of 'Balanced Incomplete Block Designs' (BIBDS).
Search for Block Design at http://mathworld.wolfram.com/ for a somewhat technical explanation.
In the second, v = 12, k = 4, lambda = 3, b = 33, and r = 11.
Similar block designs exist for v = 4n, k = 4, lambda = 3, r = 4n - 1, and b = n(4n - 1) for all positive n.
Hence a solution should also exist for 16 players (v = 16).
|
| « Last Edit: Jan 29th, 2004, 5:25pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Quetzycoatl
Newbie
Gender:
Posts: 46
|
|
Re: new riddle: tennis competition
« Reply #2 on: Jan 29th, 2004, 8:03am » |
Quote Modify
|
on Jan 28th, 2004, 11:35pm, THUDandBLUNDER wrote:
Similar block designs exist for v = 4n, k = 4, lambda = 3, r = 4n - 1, and b = n(4n - 1) for all positive n.
|
|
I think v = 9 may work. v = 5 works and, unless I am misunderstanding, it does not fit the criteria described above.
12 v 35 4 sits out
13 v 54 2 sits out
14 v 23 5 sits out
15 v 24 3 sits out
25 v 34 1 sits out
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: new riddle: tennis competition
« Reply #3 on: Jan 29th, 2004, 10:45am » |
Quote Modify
 Remove
|
I think Thudandblunder wasn't taking into consideration that one player sits out. I don't have a solution yet, but here's a fairly simple suboptimal way to solve it.
Arrange nine points around a circle and connect them with straight lines in every possible way to make the pairings. The simultaneous pairings are denoted by all parallel lines. So, for example you get 1 and 2, 3and9, 4and 8, and 5and6 in the first match up. Now you have to pair up the pairs as opponents. So, to pick 1's opponents you must choose one line parallel to each of 1's matchups, such that every other point is used twice. In the drawing, that will create a closed circuit, visiting the other 8 points once, with no two lines parallel to each other nor perpendicular to point 1's radius. An example circuit would be 2,3,9,7,8,5,4,6,2. Matching each of those lines with the 1 line that is parallel to it gives a solution (suboptimal in this case). The match ups would be
12v39 48v57
13v58 49v67
14v23 59v68
15v78 24v69
16v79 34v25
17v26 89v35
18v45 27v36
19v46 28v37
29v47 38v65
That is optimal for player one (and player 4). But, for example, player 2 plays opposite player 3 four times and never plays opposite 8. It has perfect pairings but the oppositions are off a total of 24 times. I'm sure there's a better solution, and my method may not be the one that will find it.
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: new riddle: tennis competition
« Reply #4 on: Jan 29th, 2004, 11:06am » |
Quote Modify
Remove
|
Note: Actually the solution I gave is off by 12 oppositions, not 24.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: new riddle: tennis competition
« Reply #5 on: Jan 29th, 2004, 11:46am » |
Quote Modify
|
Quote:| I think Thudandblunder wasn't taking into consideration that one player sits out. |
|
Yes, I was.
v = 9 is much harder than v = 5 because we have 2 matches going on simultaneously,
thus drastically reducing our options. I still believe it's impossible.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: new riddle: tennis competition
« Reply #6 on: Jan 29th, 2004, 5:10pm » |
Quote Modify
|
1-2 3-4 5-6 7-8 9
1-9 5-7 2-4 6-8 3
3-8 6-9 2-5 4-7 1
4-8 3-7 2-9 1-6 5
2-3 7-9 4-6 1-5 8
1-3 5-8 6-7 4-9 2
3-6 1-7 5-9 2-8 4
3-9 4-5 2-7 1-8 6
2-6 3-5 1-4 8-9 7
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: tennis competition
« Reply #7 on: Jan 29th, 2004, 6:33pm » |
Quote Modify
|
Hmm...may the force be with you, SWF. 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
gert1
Guest
|
That is great SWF.
How about 13 and 17 players, is there a general method to find these schedules?
|
|
IP Logged |
|
|
|
why_linux_BSD_rule
Newbie
Posts: 6
|
|
Re: tennis competition
« Reply #9 on: Jan 31st, 2004, 8:18am » |
Quote Modify
|
C(9,2) = 36
which means 36 unique combinations can be found.
i.e. if players are from A,B,C.........I then
A,B and B,A will both not be included here.
Two such courts would make it 4 teams playing with one spare (to collect balls  )
thus each round you will get rid of 4 combinations. Thus you need 9 rounds (because 9X4=36)
to exhaust all combinations.
Try the same case for the 13, 17 ......... (maybe you have to increase the court number to get it in a desired number of times)
I HOPE I am on the right track.
|
| « Last Edit: Jan 31st, 2004, 8:29am by why_linux_BSD_rule » |
IP Logged |
|
|
|
gert1
Guest
|
thanks, this site is exactly what I'm looking for.
May the force be with you too 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print