Hi, pippic-ga:
Since I haven't heard back from you in a few days on the clarification
to the second part of your Question, let me go ahead and give results
about the first part. I'll also add a note on the second part at the
end.
Since in a group of 12 golfers, there are for each player 11 "others",
any player who goes out in 4 foursomes will necessarily find at least
one repetition (since there are three "others" in each foursome).
While it is possible to schedule twelve foursomes so that each player
experiences only one repetition, this schedule is almost certainly
useless for your purpose because it does not allow three foursomes to
play simultaneously on each day. In fact each pair of foursomes in a
schedule of that nature will intersect in at least one player, so you
couldn't even play two foursomes at a time. For the sake of
completeness I will give such a schedule further down and show how it
can be constructed.
So I think we have to state as an important aspect of your problem
that on each of four days, we schedule three mutually disjoint
foursomes. By mutually disjoint I mean that no player is assigned to
more than one of such three foursomes (and of course since there are
exactly 12 players, this implies each player is on exactly one of the
three foursomes for that day).
[There is some technical terminology for this, which might be useful
if you want to search the Web later for similar problems. Since two
foursomes on a given day "never meet" in a common player, these
various days' foursomes may be called "parallel classes". A "design"
(schedule of foursomes, in this case) that can be broken
("partitioned") into parallel classes is referred to as a "resolvable
design". Okay, enough technical terminology!]
The first day's "flight" is arbitrary, in the sense that up to a
permutation of the players, all possible schedules agree about the
first day. You can just divide the 12 players into any three groups
of four, and there's nothing better or worse about how those groups
are chosen. Nonetheless the choices for grouping on days 2, 3, and 4
will be conditioned by the first day's choice.
We can picture the first day's foursomes something like this:
A1--A2--A3--A4
B1--B2--B3--B4
C1--C2--C3--C4
which shows us three rows of four corresponding to three foursomes.
It is now impossible to choose _any_ foursome without getting at least
two players from the same foursome of that first day. Thus after the
first day, every foursome on a schedule will involve at least one
"repeat". Thus we will have at least three repeats on day 2, on day
3, and on day 4, and that's only considering how many repeats may
occur between the first day and each of the later days.
Given that repeats will (in this sense) occur all the time, we should
ask what the measure for "as close as possible to the ideal" should
be. Since generally the number of distinct pairs who play together at
some point is complementary to the number of repeat pairings, we could
try maximize the number of distinct pairings. Unfortunately, to do so
requires that a few pairings will be repeated multiple times, allowing
a greater number of distinct pairings overall at the expense of some
of the players.
To counteract that we can impose a restriction that each player will
meet the same number of "others". While this slightly reduces the
maximum number of pairs who have the chance to play together, it
treats all the players as equally as possible.
Note that for 12 players there are C(12,2) = 66 pairs of distinct
players. In the first day's schedule we will account for 6 pairings
in each of three foursomes, for a first day's total of 18 pairs of
distinct players.
On day 2 the minimum number of repetitions is three (one for each
foursome), so the maximum number of additional pairs of distinct
players we can hope to account for is 15, and it is easy to attain
this.
On day 3 there must be three repetitions from the first day and also
three repetitions from day 2. However if these repetitions were the
same three pairs of distinct players, we could get as many as another
15 pairings that had not previously been acheived. If we do not allow
for any "triple" repetitions at this point, we are limited to 18 - 3 -
3 = 12 new pairings. Let us assume the latter, so that after day 3 we
have in total:
18 + 15 + 12 = 45 pairings of distinct players
This sets the stage for day 4. We can choose the final foursomes so
that in the end, each player will have played with exactly 9 of the 11
possible other players. There is a certain amount of asymmetry in how
the repetitions are distributed in this case. Most players will have
met three others exactly twice in their schedule (so 12 - 3 repeats =
9 distinct other players met), but two of the players do meet each
other three times (and each meets another player twice). But these
two players will also have met nine others (subtract 2 from 12 for the
triple meeting and 1 for their "simple" repeat).
With those caveats here's my schedule for the four days:
First day:
(A1,A1,A3,A4)
(B1,B2,B3,B4)
(C1,C2,C3,C4)
Day 2:
(A1,B1,C1,A2)
(B2,C2,A3,B3)
(C3,A4,B4,C4)
Day 3:
(A1,B2,C3,A4)
(B1,C2,A3,B4)
(C1,A2,B3,C4)
Day 4:
(A1,C2,A3,C4)
(B1,A2,B2,C3)
(C1,B3,B4,A4)
In the end 54 of the 66 possible pairs will have played together at
some point during the four days, and it is impossible for all 12
players to each meet more than nine others in such a schedule.
Something of this kind is therefore my suggestion for "as close as
possible to the ideal".
*******************************************
Constructing Foursomes of 12 Players Where Each Distinct Pair Meets
[not suitable as a solution because no two foursomes are "disjoint"]
Consider the twelve hours on the dial of a clock, and starting at the
top (12th hour), mark four points separated successively by intervals
of 1, 2, and 4 hours:
(12, 1, 3, 7)
Now rotate this entire group of four points around the clock by an
hour each time, until you return to the starting configuration:
(1, 2, 4, 8)
(2, 3, 5, 9)
(3, 4, 6, 10)
(4, 5, 7, 11)
(5, 6, 8, 12)
(6, 7, 9, 1)
(7, 8, 10, 2)
(8, 9, 11, 3)
(9, 10, 12, 4)
(10, 11, 1, 5)
(11, 12, 2, 6)
(12, 1, 3, 7)
It will be found that every pair of distinct players (or hours) occurs
at least once in the schedule. Repeats are limited to one for each
player, which means there are six pairs of disinct players who meet
exactly twice, and otherwise any pair meets only once. These repeats
correspond to a difference of six hours (halfway around the dial) that
occurs initially between 1 and 7. After shifting this "basic pattern"
around by six hours, we again have a foursome that includes the same
pair 1 and 7, and the same is true of every pair differing by six.
*******************************************
As a final note let me comment a bit more about the second part of the Question.
If all that is needed is for one complete round of pairs and one
complete round of foursomes, drawn from a pool of 16 players, to avoid
any repeats, this is pretty easy.
Let's start with the round of 4 foursomes and label the players this way:
A1--A2--A3--A4
B1--B2--B3--B4
C1--C2--C3--C4
D1--D2--D3--D4
Given that there are many ways to choose 8 nonintersecting pairs for
the required round of "singles".
For example we could make pairs between the top two and bottom two rows:
A1--A2--A3--A4
|| || || ||
B1--B2--B3--B4
|| || || ||
C1--C2--C3--C4
|| || || ||
D1--D2--D3--D4
I hope this has been helpful, though I still suspect something more
was intended by the second part of the Question.
regards, mathtalk-ga |
