Forming groups of 4
Denis
please accept my apologies and hopefully someone can direct me to the right
group.
The problem I am trying to solve:
There are 12 people (numbered 1 to 12). I need to produce 3 groups of 4
seven times with the condition that no one person has another person in his
group more than twice.
Not sure if its possible to do this but I hope someone has the answer.
Jan
Arturo Magidin
This is sometimes called the "Golf foursome problem": k people
want to play m rounds of golf; you play golf in groups of four, called
"foursome"s. You want to arrange the foursomes so that two players are
not in the same foursome more than once.
I will number the players as 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C.
We may assume the first round is played as:
1 2 3 4
5 6 7 8
9 A B C
Now, what about the second round? Can you find three people, no two of
which have played before and none of which has played with 1 before,
to make up a foursome for 1 for the second round?
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
Chip Eastham
> In article <drednYdWMOeR59PVRVny...@brightview.com>, Denis <den@nomail> wrote:
> >I'm not sure if this is the right group to put this question. If not,
> >please accept my apologies and hopefully someone can direct me to the right
> >group.
>
> >The problem I am trying to solve:
> >There are 12 people (numbered 1 to 12). I need to produce 3 groups of 4
> >seven times with the condition that no one person has another person in his
> >group more than twice.
>
> >Not sure if its possible to do this but I hope someone has the answer.
>
> This is sometimes called the "Golf foursome problem": k people
> want to play m rounds of golf; you play golf in groups of four, called
> "foursome"s. You want to arrange the foursomes so that two players are
> not in the same foursome more than once.
Actually, the OP weakened the requirement that "two players
are not in the same foursome more than once" to "no one
person has another person in his group more than twice".
Another aspect of the requirements may be that the "3
groups of 4 seven times" is, like the golf foursome
problem, that we want a resolvable design, i.e. that
each of the seven times, we have each player once in
the 3 foursomes.
A good starting point is probably:
[La Jolla Covering Repository]
http://www.ccrwest.org/cover.html
where we find the following optimal covering of pairs
by twelve foursomes:
2 3 5 9
3 4 6 10
4 5 7 11
5 6 8 12
1 6 7 9
2 7 8 10
3 8 9 11
4 9 10 12
1 5 10 11
2 6 11 12
1 3 7 12
1 2 4 8
In these 12 foursomes, only six pairs occur twice:
(1,7) (2,8) (3,9) (4,10) (5,11) (6,12)
and no pair occurs more than twice. So one approach
is to look for 9 more foursomes that avoid duplicate
pairings as well as the six pairs above.
Resolvability (partitioning the foursomes into
partitions of the 12 players, or "parallel classes")
probably cannot be obtained by this approach.
regards, chip
Christopher Henrich
"Denis" <den@nomail> wrote:
Among 12 people, there are 12*11/2 = 66 distinct pairs. Each pair may be
used at most 2 times, so there are 132 pairs to be used.
Each foursome has 6 pairs; a "round" of three foursomes uses up 18 pairs.
7 rounds require 126 pairs 126 <= 132, so this crude analysis suggests
tat the problem is solvable but it may be a tight fit.
Arturo Magidin's variant, where each distinct pair can occur no more
than once, is definitely out.
--
Christopher J. Henrich
chen...@monmouth.com
htp://www.mathinteract.com
Virgil
mag...@math.berkeley.edu (Arturo Magidin) wrote:
> In article <drednYdWMOe...@brightview.com>, Denis <den@nomail> wrote:
> >I'm not sure if this is the right group to put this question. If not,
> >please accept my apologies and hopefully someone can direct me to the right
> >group.
> >
> >The problem I am trying to solve:
> >There are 12 people (numbered 1 to 12). I need to produce 3 groups of 4
> >seven times with the condition that no one person has another person in his
> >group more than twice.
> >
> >Not sure if its possible to do this but I hope someone has the answer.
>
> This is sometimes called the "Golf foursome problem": k people
> want to play m rounds of golf; you play golf in groups of four, called
> "foursome"s. You want to arrange the foursomes so that two players are
> not in the same foursome more than once.
>
> I will number the players as 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C.
>
> We may assume the first round is played as:
>
> 1 2 3 4
> 5 6 7 8
> 9 A B C
>
> Now, what about the second round? Can you find three people, no two of
> which have played before and none of which has played with 1 before,
> to make up a foursome for 1 for the second round?
Shouldn't that read "no two of which have played TOGETHER before and
none of which has played with 1 before"?
Chip Eastham
The particular approach I suggested turns out to be
a dead end. Any set of 9 foursomes (over 12 players)
in which no pair occurs more than once has a certain
configuration of "holes" (pairs not "covered") that
is incompatible with the "extra pairs" appearing in
the covering design of 12 foursomes listed.
In particular the "holes" of any such 9 foursomes
consist of four 3-subsets that partition the players
so that no pair within a 3-subset will meet.
The extra pairs of the design from the La Jolla
covering repository took the form of six disjoint
pairs. It is therefore impossible to make the
12 holes (missing pairs) of the 9 foursomes cover
the 6 extra pairs of that 12 foursome covering
design.
regards, chip
Arturo Magidin
Virgil <Vir...@gmale.com> wrote:
>In article <g2m713$2g9f$1...@agate.berkeley.edu>,
> mag...@math.berkeley.edu (Arturo Magidin) wrote:
[...]
>> >The problem I am trying to solve:
>> >There are 12 people (numbered 1 to 12). I need to produce 3 groups of 4
>> >seven times with the condition that no one person has another
>> >person in his group more than twice.
>> >
[...]
>> Now, what about the second round? Can you find three people, no two of
>> which have played before and none of which has played with 1 before,
>> to make up a foursome for 1 for the second round?
>
>Shouldn't that read "no two of which have played TOGETHER before and
>none of which has played with 1 before"?
(i) Yes; and (ii) doesn't matter, because I misread the problem. The
condition is that any particular pair of individuals will not play
together three times or more, I thought the condition (as in the usual
golf problem) is that no particular pair of individuals will play
together twice or more.
Chip Eastham
> In article <drednYdWMOeR59PVRVny...@brightview.com>,
Hi, Christopher:
Sometimes improved estimates come from drilling down
on the number of "blocks" that contain a particular
point (player).
If no pair can appear more than twice, then the most
number of foursomes a player can occur in is 7, as
with 8 foursomes a player would be paired 24 times
and with only 11 other players, one of them would
have to appear more than twice. If some player is
in fewer than 7 foursomes, another player would need
to appear in more than 7 because the count is tight:
(7 foursomes per player)*(12 players) = 84
= (4 players per foursome)*(21 foursomes)
This argument holds even if we don't assume the design
is resolvable, i.e. that foursomes occur in 7 daily
rounds with each round partitioning the 12 players in
three foursomes.
In fact we can prove that a resolvable arrangement
is impossible by looking at the number of duplicate
pairs. It follows from each player appearing in 7
foursomes that each player appears in 10 duplicate
pairs (one other player appears only once in some
common foursome, accounting for the 21 available
slots). Since there are 12 players and duplicate
pairs are counted twice (once for each player)
when we multiply 10*12, there are actually 60
pairs that are duplicated (appear twice).
But in a resolvable design, the question that Arturo
asks us to consider leads to the conclusion that any
two of the rounds (parallel classes) must share at
least three duplicate pairs. There are C(7,2) = 21
pairs of rounds, and no pair duplicated between one
pair of rounds could be duplicated again against
another round (since that pair would then appear more
than twice). So any resolvable design would entail
at least 63 duplicate pairs, contrary to the figure
60 duplicate pairs derived above.
The "unresolvable" version remains open, AFAIK, i.e.
can 21 foursomes be formed of 12 players without any
pair appearing more than twice.
regards, chip
Chip Eastham
Hi, Jan:
As I explained elsewhere in this thread, it is not
possible to to arrange the "3 groups of 4" seven
times so that each person occurs exactly once in
each of the seven "rounds" (3 groups of 4).
Is it of interest to you to know whether 21 groups
of 4 are possible, using the given 12 people so
that no pair is grouped together more than twice?
regards, chip
Denis
Yes 21 groups of 4 you mention in the last paragraph would be of interest to
me. Perhaps I can then choose the 7 lots out of that.
Many thanks for trying to solve tihis, way beyond my capabilities.
Jan
"Chip Eastham" <hard...@gmail.com> wrote in message
news:4f978734-ed12-4811...@2g2000hsn.googlegroups.com...
Chip Eastham
> Hi Chip
>
> Yes 21 groups of 4 you mention in the last paragraph would be of interest to
> me. Perhaps I can then choose the 7 lots out of that.
>
> Many thanks for trying to solve tihis, way beyond my capabilities.
>
> Jan
>
>
> news:4f978734-ed12-4811...@2g2000hsn.googlegroups.com...
>
> > On Jun 10, 8:56 am, "Denis" <den@nomail> wrote:
> >> I'm not sure if this is the right group to put this question. If not,
> >> please accept my apologies and hopefully someone can direct me to the
> >> right
> >> group.
>
> >> The problem I am trying to solve:
> >> There are 12 people (numbered 1 to 12). I need to produce 3 groups of 4
> >> seven times with the condition that no one person has another person in
> >> his
> >> group more than twice.
>
> >> Not sure if its possible to do this but I hope someone has the answer.
>
> >> Jan
>
> > Hi, Jan:
>
> > As I explained elsewhere in this thread, it is not
> > possible to to arrange the "3 groups of 4" seven
> > times so that each person occurs exactly once in
> > each of the seven "rounds" (3 groups of 4).
>
> > Is it of interest to you to know whether 21 groups
> > of 4 are possible, using the given 12 people so
> > that no pair is grouped together more than twice?
>
> > regards, chip
>
>
Hi, Jan:
Here's what I came up with: 21 blocks of four out of
twelve points/players such that no pair appears more
than twice together in a foursome:
List = [(5 , 6 , 7 , 8), (2 , 7 , 10 , 11), (2 , 7 , 9 , 10),
(4 , 6 , 7 , 9), (4 , 5 , 8 , 9), (2 , 4 , 5 , 12),
(3 , 8 , 10 , 12), (3 , 7 , 8 , 12), (3 , 4 , 6 , 11),
(2 , 3 , 6 , 11), (1 , 9 , 11 , 12), (1 , 8 , 9 , 11),
(1 , 5 , 6 , 10), (1 , 3 , 5 , 10), (1 , 2 , 4 , 12),
(1 , 3 , 4 , 7), (1 , 2 , 6 , 8), (2 , 3 , 5 , 9),
(6 , 9 , 10 , 12), (5 , 7 , 11 , 12), (4 , 8 , 10 , 11)]
/* end of design */
The last six foursomes each contain one pair that appears
together only once (rather than twice) by design:
(1,7), (2,8), (3,9), (4,10), (5,11), (6,12)
Each of the other possible pairs occurs exactly twice.
regards, chip
Chip Eastham
Hi, Jan:
As I said, there is no "resolvable" design of 21
foursomes out of twelve players such that no pair
meets more than twice. So the above design is not
resolvable, and indeed there are no three mutually
disjoint blocks in the whole collection.
Thus you cannot schedule any 3 foursomes here
simultaneously. However each block has at least
one other block which is mutually disjoint with it.
The graph in which edges connect mutually disjoint
blocks looks like this:
{1,9,11,12} ------ {5,6,7,8} ------ {1,2,4,12}
{2,7,10,11} ------ {4,5,8,9} ------ {2,3,6,11}
{3,8,10,12} ------ {4,6,7,9} ------ {1,3,5,10}
{1,5,6,10} ------ {3,7,8,12}
{2,7,9,10} ------ {3,4,6,11}
{1,8,9,11} ------ {2,4,5,12}
{1,3,4,7} ------ {6,9,10,12}
{1,2,6,8} ------ {5,7,11,12}
{2,3,5,9} ------ {4,8,10,11}
This suggests to me a 9 day schedule in which two
disjoint foursomes play on 6 of the 9 days (see the
last six rows of the graph above). On the other 3
days three foursomes each are scheduled (see the
first three rows of the graph above), with the first
and last of those having a pair of players in common,
but no overlap between those and the middle foursome.
Thus the pair who play twice would have a break to
rest during the middle match on those 3 days.
regards, chip
Chip Eastham
It is possible to group the twelve people into
3 disjoint groups of 4 six times so that no pair
appears more than twice:
R1 = [[a1, a2, a3, a4], [b1, b2, b3, b4], [c1, c2, c3, c4]]
R2 = [[a1, a2, b3, c4], [b1, b2, c3, a4], [c1, c2, a3, b4]]
R3 = [[b2, c4, a1, a3], [c2, a4, b1, b3], [a2, b4, c1, c3]]
R4 = [[b4, c3, a1, a4], [a3, c1, b2, b3], [a2, b1, c2, c4]]
R5 = [[b1, c3, a2, a3], [a1, c2, b2, b4], [a4, b3, c1, c4]]
R6 = [[b2, c1, a2, a4], [a3, c4, b1, b4], [a1, b3, c2, c3]]
regards, chip