36 people, meeting in groups of 6. Is it possible to meet each person exactly once in a round of 7 meetings?
Brent Hugh
http://ask.metafilter.com/161031/Dont-meet-the-same-person-twice-involves-math-somehow#2311544
I'm wondering if anyone knows the answer or a good approach.
Slightly re-stated from that forum, here is the problem:
36 people total, meeting in groups of 6. After 5 minutes, the groups
shuffle into completely new groups. Repeat this every five minutes.
Is it possible to arrange the meetings in such a way that after 7 sets
of meetings, each person has been in a group with each of the other 36
people exactly once?
Interestingly there is a pretty simple solution for groups of 4, 9,
16, 25, 49 and all other squares of primes (see the link above for
details).
But how about squares of non-prime numbers, like groups of 36?
Is a solution possible? Is there some general method for finding it?
Any thoughts in general? (I find it hard to believe that this type of
problem hasn't been studied already . . . )
Gerry
> An interesting question was posted on Metafilter here:
>
>
> I'm wondering if anyone knows the answer or a good approach.
>
> Slightly re-stated from that forum, here is the problem:
>
> 36 people total, meeting in groups of 6. After 5 minutes, the groups
> shuffle into completely new groups. Repeat this every five minutes.
>
> Is it possible to arrange the meetings in such a way that after 7 sets
> of meetings, each person has been in a group with each of the other 36
> people exactly once?
>
> Interestingly there is a pretty simple solution for groups of 4, 9,
> 16, 25, 49 and all other squares of primes (see the link above for
> details).
16 is not the square of a prime.
> But how about squares of non-prime numbers, like groups of 36?
>
> Is a solution possible? Is there some general method for finding it?
> Any thoughts in general? (I find it hard to believe that this type of
> problem hasn't been studied already . . . )
There is a literature about these things. Sometimes
it's called the social golfer problem, sometimes it
relates to whist tournaments (but in those cases we
usually want groups of 4, not 6). Maybe resolvable
block designs is the keyphrase.
--
GM
Butch Malahide
>
> > 36 people total, meeting in groups of 6. After 5 minutes, the groups
> > shuffle into completely new groups. Repeat this every five minutes.
>
> > Is it possible to arrange the meetings in such a way that after 7 sets
> > of meetings, each person has been in a group with each of the other 36
> > people exactly once?
>
> > Interestingly there is a pretty simple solution for groups of 4, 9,
> > 16, 25, 49 and all other squares of primes (see the link above for
> > details).
>
> 16 is not the square of a prime.
But it is the square of a prime power.
> > But how about squares of non-prime numbers, like groups of 36?
>
> > Is a solution possible? Is there some general method for finding it?
> > Any thoughts in general? (I find it hard to believe that this type of
> > problem hasn't been studied already . . . )
>
> There is a literature about these things. Sometimes
> it's called the social golfer problem, sometimes it
> relates to whist tournaments (but in those cases we
> usually want groups of 4, not 6). Maybe resolvable
> block designs is the keyphrase.
Isn't the OP is just asking for a projective plane (or 5 mutually
orthogonal Latin squares) of order 6? And just getting through four
sets of meetings without two people being together twice, isn't that
just Euler's problem of the 36 officers, which was proved impossible
by Tarry? Or am I just confused?
Butch Malahide
>
> 36 people total, meeting in groups of 6. After 5 minutes, the groups
> shuffle into completely new groups. Repeat this every five minutes.
>
> Is it possible to arrange the meetings in such a way that after 7 sets
> of meetings, each person has been in a group with each of the other 36
> people exactly once?
No. Suppose that could be done. So you've got 36 guys and 42 groups.
Now get 7 new guys, and make those 7 guys into a group (called "the
line at infinity"). So now you've got 43 guys and 43 groups; one group
has 7 members the rest have only 6. Now add one more member to each of
those 6-member groups, as follows. Number the new guys from 1 to 7,
add new guy #1 to each of the 6 groups from the first meeting, add new
guy #2 to each of the 6 groups from the second meeting, and so on.
OK, now you've got 43 guys and 43 groups; each group has 7 members;
each guy is in 7 groups; any two groups have exactly one member in
common; and two guys are together in exactly one group. If you call
the guys "points" and the groups "lines", what you have is a structure
called a "projective plane of order 6". A projective plane of order n
is the same except that you have n + 1 points on a line and n + 1
lines through a point; the number of lines and the number of points
are both equal to n^2 + n + 1. Your question, then, is tantamount to
asking whether there is a projective plane of order 6.
It is known that a projective plane of order n exists if n is a prime
number, or more generally if n is a (positive) power of a prime
number; i.e., they exist for n = 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17,
19, 23, 25, 27, 29, . . . . (In other words, a projective plane of
order n exists whenever there is an n-element field.) It is
conjectured that they do not exist for any other value of n. I believe
that many values of n have been ruled out (as possible orders of
projective planes), but don't ask me what they are, I never studied
that stuff. All I know is that projective planes of order 6 do not
exist, and that was established a long time ago.
Search terms: "finite projective plane", "orthogonal latin squares",
"36 officers".
Butch Malahide
P.S. I looked at that "Metafilter" page, and I see they are also
asking how many rounds you can go without two people meeting a second
time. The answer is 3 rounds. Trying to do it for 4 rounds is
equivalent to Euler's problem of the 36 officers, and was proved
impossible by a guy named Tarry something like a hundred years ago.
Look it up on Wikipedia.
Danny73
>
> - Show quoted text -
I know what a round is but how many discrete meetings are possible?
Is it more than 18 meetings?
Butch Malahide
> Is it more than 18 meetings?
Good question. I don't know.
Gerry Myerson
<0dfa91bd-3c07-4dc4...@a30g2000vba.googlegroups.com>,
Butch Malahide <fred....@gmail.com> wrote:
I had a feeling it reduced to those problems, but I couldn't quite
make the connection. I see you've worked it out in another post.
Good!
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)