Prev: Thermodynamics is recycleable but not the Maxwell theory Re: Exoplanets in Tight 2:1 Resonance #251 & 4.35 Atom Totality & Correcting Math
Next: So why my initials at the start?
From: Gerry on 1 Aug 2010 02:39
On Aug 1, 11:51 am, Brent Hugh <brentdh...(a)gmail.com> wrote:
> An interesting question was posted on Metafilter here:
>
>  http://ask.metafilter.com/161031/Dont-meet-the-same-person-twice-invo....
>
> 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
From: Butch Malahide on 1 Aug 2010 03:33
On Aug 1, 1:39 am, Gerry <ge...(a)math.mq.edu.au> wrote:
>
> > 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?
From: Butch Malahide on 1 Aug 2010 05:09
On Jul 31, 8:51 pm, Brent Hugh <brentdh...(a)gmail.com> wrote:
>
> 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".
From: Butch Malahide on 1 Aug 2010 05:31
On Aug 1, 4:09 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
> On Jul 31, 8:51 pm, Brent Hugh <brentdh...(a)gmail.com> wrote:
>
>
>
> > 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".

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.
From: Danny73 on 1 Aug 2010 13:13
On Aug 1, 5:31 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
> On Aug 1, 4:09 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
>
>
>
>
>
> > On Jul 31, 8:51 pm, Brent Hugh <brentdh...(a)gmail.com> wrote:
>
> > > 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".
>
> 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.- Hide quoted text -
>
> - Show quoted text -

I know what a round is but how many discrete meetings are possible?
Is it more than 18 meetings?
 |  Next  |  Last
Pages: 1 2
Prev: Thermodynamics is recycleable but not the Maxwell theory Re: Exoplanets in Tight 2:1 Resonance #251 & 4.35 Atom Totality & Correcting Math
Next: So why my initials at the start?