Don't meet the same person twice (involves math ... somehow)
July 31, 2010 10:14 AM Subscribe
36 people total, meeting in groups of 6. After 5 minutes, the groups shuffle into completely new groups. How many "rounds" can we go without people meeting with someone they've already met?
This is a real world case as part of a get-to-know-you business mixer. It's not my event, so I can't suggest an alternative plan. My mom asked me to solve this because she thinks highly of my problem solving skills. Well, I'm stumped, but I'm not about to let down my mom.
Using pencil and paper I came up with 4 completely unique rounds, but I'm stumped to come up with a 5th round schedule. Is it even possible?
This is a real world case as part of a get-to-know-you business mixer. It's not my event, so I can't suggest an alternative plan. My mom asked me to solve this because she thinks highly of my problem solving skills. Well, I'm stumped, but I'm not about to let down my mom.
Using pencil and paper I came up with 4 completely unique rounds, but I'm stumped to come up with a 5th round schedule. Is it even possible?
You can get five rounds if you imagine a "leader" from each group making synchronized visits to each of the five other groups. They will then have met everyone, so five looks like maximum to me.
posted by weapons-grade pandemonium at 10:57 AM on July 31, 2010
posted by weapons-grade pandemonium at 10:57 AM on July 31, 2010
If you make a 6 by 6 array of them, you get your rows, your columns, your diagonals to the right, your diagonals to the left. That makes 4. But your weird knight moves don't work because 6 has too many factors. (Not a proof, obviously)
posted by Obscure Reference at 10:59 AM on July 31, 2010
posted by Obscure Reference at 10:59 AM on July 31, 2010
I wasn't quite right. The leaders will not have met each other. But if you put them together as a unique group, you would then have to gather five unique groups of six from the remaining 30 people. Not sure if that is possible.
posted by weapons-grade pandemonium at 11:03 AM on July 31, 2010
posted by weapons-grade pandemonium at 11:03 AM on July 31, 2010
PMdixon: why is the obvious maximum 6? 7 seems possible; each person meets 5 people in each round, for a total of 35.
posted by madcaptenor at 11:07 AM on July 31, 2010
posted by madcaptenor at 11:07 AM on July 31, 2010
Response by poster: I had followed OR's logic previously, but checking it now it appears that the reverse diagonal doesn't work because one of the number repeats in a grouping. So I'm still at only 3 unique rounds.
Here's what I've got if anyone is interested.
posted by foggy out there now at 11:15 AM on July 31, 2010
Here's what I've got if anyone is interested.
posted by foggy out there now at 11:15 AM on July 31, 2010
Response by poster: Ugh, looks like someone already deleted the pastebin I posted. I'll post it here.
Round 1
01,02,03,04,05,06
07,08,09,10,11,12
13,14,15,16,17,18
19,20,21,22,23,24
25,26,27,28,29,30
31,32,33,34,35,36
Round 2
01,07,13,19,25,31
02,08,14,20,26,32
03,09,15,21,27,28
04,10,16,22,28,34
05,11,17,23,29,35
06,12,18,24,30,36
Round 3
01,08,15,22,29,36
07,14,21,28,35,06
13,20,27,34,05,12
19,26,33,04,11,18
25,32,03,10,17,24
31,02,09,16,23,30
posted by foggy out there now at 11:22 AM on July 31, 2010
Round 1
01,02,03,04,05,06
07,08,09,10,11,12
13,14,15,16,17,18
19,20,21,22,23,24
25,26,27,28,29,30
31,32,33,34,35,36
Round 2
01,07,13,19,25,31
02,08,14,20,26,32
03,09,15,21,27,28
04,10,16,22,28,34
05,11,17,23,29,35
06,12,18,24,30,36
Round 3
01,08,15,22,29,36
07,14,21,28,35,06
13,20,27,34,05,12
19,26,33,04,11,18
25,32,03,10,17,24
31,02,09,16,23,30
posted by foggy out there now at 11:22 AM on July 31, 2010
6 divided into 36 is 6.
Let's name the groups a, b, c, d, e and f. if A meets with each of the other groups that makes five.
To test this make a wheel, divide it into sixes, and label with a letter. You will see I'm right.
posted by St. Alia of the Bunnies at 11:23 AM on July 31, 2010
Let's name the groups a, b, c, d, e and f. if A meets with each of the other groups that makes five.
To test this make a wheel, divide it into sixes, and label with a letter. You will see I'm right.
posted by St. Alia of the Bunnies at 11:23 AM on July 31, 2010
Oops, you are saying completely different groups. This is why I suck at math.
posted by St. Alia of the Bunnies at 11:24 AM on July 31, 2010
posted by St. Alia of the Bunnies at 11:24 AM on July 31, 2010
You can't analyze this from a single person's perspective (or even "leaders") since the question involves no people meeting someone they've already met - i.e. the groups of 6 have to be unique for ALL members of the group each time. I'd be surprised if you could get a 5th round.
posted by birdsquared at 11:27 AM on July 31, 2010
posted by birdsquared at 11:27 AM on July 31, 2010
MUST remember to preview in Ask - whenever I type (or think) slowly, someone has usually already made the point...
posted by birdsquared at 11:30 AM on July 31, 2010
posted by birdsquared at 11:30 AM on July 31, 2010
Yeah, my answer is wrong, or at least wildly incomplete. I suspect the answer, for a setting involving n groups totalling n^2 people, might turn out to be one more than the number of elements of Z_n having a multiplicative inverse, in which case for 36 people in groups of 6 you can only do 3 rounds. Looking at your first grid, the sets containing person 1 can be written, if x and y are the usual cartesian coordinates, as: x=1; y=1; x+y=2 (mod 6). I suspect, but can't prove, that in general, any solution is going to be made up of the sets of partitions obtained from various (x+ay=k (n), k={0,1,2,...,n-1}) plus the partition (y=k (n), k={1,2,...,n-1}. For simplicity of arithmetic's sake, we'll start numbering at 0 instead of 1.
Here's a sketch of a proof that there's a solution for each element having a multiplicative inverse, which is the same as ever multiplying to 0 with a non-zero number. Consider the set containing the first point, ie k=0; then the equations are of the form x+ay=0 (n). For two partitions to have overlap, there are a1, a2, y1, y2 such that x+a1y1=x+a1y2=x+a2y2=x+a2y1 (n). By algebra magic, this gets to (a1-a2)(y1-y2)=0 (n). Note that we can be pretty sure that a=0 is going to be one of our solutions (I think you can make this assumption go away, but am slightly hungover.) So if a2=0, then we have a1(y1-y2)=0 (n). If n is prime, or if a1 has a multiplicative inverse, the only solution is y1=y2. Else we have the same x value giving rise to multiple y values, ie two people who were together in the "row" round will be together again later.
tl;dr: I think 3 is it. If you kick out 11 people or add 13, you can do 5 or 7 rounds, respectively.
posted by PMdixon at 12:08 PM on July 31, 2010
Here's a sketch of a proof that there's a solution for each element having a multiplicative inverse, which is the same as ever multiplying to 0 with a non-zero number. Consider the set containing the first point, ie k=0; then the equations are of the form x+ay=0 (n). For two partitions to have overlap, there are a1, a2, y1, y2 such that x+a1y1=x+a1y2=x+a2y2=x+a2y1 (n). By algebra magic, this gets to (a1-a2)(y1-y2)=0 (n). Note that we can be pretty sure that a=0 is going to be one of our solutions (I think you can make this assumption go away, but am slightly hungover.) So if a2=0, then we have a1(y1-y2)=0 (n). If n is prime, or if a1 has a multiplicative inverse, the only solution is y1=y2. Else we have the same x value giving rise to multiple y values, ie two people who were together in the "row" round will be together again later.
tl;dr: I think 3 is it. If you kick out 11 people or add 13, you can do 5 or 7 rounds, respectively.
posted by PMdixon at 12:08 PM on July 31, 2010
Response by poster: Correction, I found a typo in the second round.
01,02,03,04,05,06
07,08,09,10,11,12
13,14,15,16,17,18
19,20,21,22,23,24
25,26,27,28,29,30
31,32,33,34,35,36
01,07,13,19,25,31
02,08,14,20,26,32
03,09,15,21,27,33
04,10,16,22,28,34
05,11,17,23,29,35
06,12,18,24,30,36
01,08,15,22,29,36
07,14,21,28,35,06
13,20,27,34,05,12
19,26,33,04,11,18
25,32,03,10,17,24
31,02,09,16,23,30
Still only three rounds though. Thanks for all the help; you've preserved my sanity. I was losing my mind thinking a simple answer was just out of reach.
I'll suggest she reduce the group size from 6 to 4 if she needs more than three rounds.
posted by foggy out there now at 12:30 PM on July 31, 2010
01,02,03,04,05,06
07,08,09,10,11,12
13,14,15,16,17,18
19,20,21,22,23,24
25,26,27,28,29,30
31,32,33,34,35,36
01,07,13,19,25,31
02,08,14,20,26,32
03,09,15,21,27,33
04,10,16,22,28,34
05,11,17,23,29,35
06,12,18,24,30,36
01,08,15,22,29,36
07,14,21,28,35,06
13,20,27,34,05,12
19,26,33,04,11,18
25,32,03,10,17,24
31,02,09,16,23,30
Still only three rounds though. Thanks for all the help; you've preserved my sanity. I was losing my mind thinking a simple answer was just out of reach.
I'll suggest she reduce the group size from 6 to 4 if she needs more than three rounds.
posted by foggy out there now at 12:30 PM on July 31, 2010
PMDixon: Your lower bound (denoted as \phi(n)+1 where phi is the Euler function) looks fine, but in the smallest nontrivial case of 4 people with groups of 2, note that you can have 3 rounds, which is strictly greater than \phi(n)+1.
Another graph theoretic way to look at this is as an edge decomposition of the complete graph on 36 vertices, K_36, into copies of G, where G is a collection of 6 disjoint copies of K_6, (or at least an examination of how many copies of G we can squeeze into there).
posted by monkeymadness at 12:37 PM on July 31, 2010
Another graph theoretic way to look at this is as an edge decomposition of the complete graph on 36 vertices, K_36, into copies of G, where G is a collection of 6 disjoint copies of K_6, (or at least an examination of how many copies of G we can squeeze into there).
posted by monkeymadness at 12:37 PM on July 31, 2010
Here is a worksheet that does it all for you, from a chess site (since tournament directors have to do this).
posted by Wordwoman at 12:48 PM on July 31, 2010
posted by Wordwoman at 12:48 PM on July 31, 2010
Best answer: Ok, here is a way to have everyone meet each other, with no repeats, in 8 meetings.
This based on a group of 49 and the general idea will work with any square where the square root is prime (i.e, 2x2, 3x3, 5x5, 7x7, 11x11 etc.).
Assign everyone a number, 0-48. In the diagram below, vertical columns show the people in each meeting.
What you do if you have less than 49 people is just let some of the spots be blank--so for instance in your case where you have 36 people, the would be spots 0 through 35 and spots 36 through 48 will just be blank/empty. You will end up with some groups being smaller & some larger, but that doesn't really hurt anything.
The first seven meetings simply rotate the numbers in each row by a set amount (zero in the first row, 1 in the second row, 2 in the 3rd row, etc). This works out with seven rows because all these numbers are relatively prime to 7 (whereas it didn't work with six rows because 2, 3, and 4 are not relatively prime to 6).
The final meeting is with everyone in each of the rows--by that point they have met each person in each of the other rows but no on in their own row.
posted by flug at 12:58 PM on July 31, 2010
This based on a group of 49 and the general idea will work with any square where the square root is prime (i.e, 2x2, 3x3, 5x5, 7x7, 11x11 etc.).
Assign everyone a number, 0-48. In the diagram below, vertical columns show the people in each meeting.
What you do if you have less than 49 people is just let some of the spots be blank--so for instance in your case where you have 36 people, the would be spots 0 through 35 and spots 36 through 48 will just be blank/empty. You will end up with some groups being smaller & some larger, but that doesn't really hurt anything.
The first seven meetings simply rotate the numbers in each row by a set amount (zero in the first row, 1 in the second row, 2 in the 3rd row, etc). This works out with seven rows because all these numbers are relatively prime to 7 (whereas it didn't work with six rows because 2, 3, and 4 are not relatively prime to 6).
The final meeting is with everyone in each of the rows--by that point they have met each person in each of the other rows but no on in their own row.
MEETING 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 MEETING 2 0 1 2 3 4 5 6 8 9 10 11 12 13 7 16 17 18 19 20 14 15 24 25 26 27 21 22 23 32 33 34 28 29 30 31 40 41 35 36 37 38 39 48 42 43 44 45 46 47 MEETING 3 0 1 2 3 4 5 6 9 10 11 12 13 7 8 18 19 20 14 15 16 17 27 21 22 23 24 25 26 29 30 31 32 33 34 28 38 39 40 41 35 36 37 47 48 42 43 44 45 46 MEETING 4 0 1 2 3 4 5 6 10 11 12 13 7 8 9 20 14 15 16 17 18 19 23 24 25 26 27 21 22 33 34 28 29 30 31 32 36 37 38 39 40 41 35 46 47 48 42 43 44 45 MEETING 5 0 1 2 3 4 5 6 11 12 13 7 8 9 10 15 16 17 18 19 20 14 26 27 21 22 23 24 25 30 31 32 33 34 28 29 41 35 36 37 38 39 40 45 46 47 48 42 43 44 MEETING 6 0 1 2 3 4 5 6 12 13 7 8 9 10 11 17 18 19 20 14 15 16 22 23 24 25 26 27 21 34 28 29 30 31 32 33 39 40 41 35 36 37 38 44 45 46 47 48 42 43 MEETING 7 0 1 2 3 4 5 6 13 7 8 9 10 11 12 19 20 14 15 16 17 18 25 26 27 21 22 23 24 31 32 33 34 28 29 30 37 38 39 40 41 35 36 43 44 45 46 47 48 42 MEETING 8 0 7 14 21 28 35 42 1 8 15 22 29 36 43 2 9 16 23 30 37 44 3 10 17 24 31 38 45 4 11 18 25 32 39 46 5 12 19 26 33 40 47 6 13 20 27 34 41 48
posted by flug at 12:58 PM on July 31, 2010
By the way it might be possible to have 36 people meet each other in as few as 7 meetings with 6 people in each group (each person must meet 35 other people and meets 5 other people in each meeting, thus 35/5=7 is absolute minimum number of meetings required).
The point is, my 8-meeting solution above is not far off the optimal solution--at worst you're holding one more meeting than the optimal solution.
(And I'm not sure yet whether hypothetical optimal solution--7 meetings with 6 people in each--really exists. I'll have to think about it a little more.)
posted by flug at 1:08 PM on July 31, 2010
The point is, my 8-meeting solution above is not far off the optimal solution--at worst you're holding one more meeting than the optimal solution.
(And I'm not sure yet whether hypothetical optimal solution--7 meetings with 6 people in each--really exists. I'll have to think about it a little more.)
posted by flug at 1:08 PM on July 31, 2010
Here is a worksheet that does it all for you, from a chess site (since tournament directors have to do this).
However that is meetings with only two participants in each--a related problem but considerably easier than the one posed.
posted by flug at 1:10 PM on July 31, 2010
However that is meetings with only two participants in each--a related problem but considerably easier than the one posed.
posted by flug at 1:10 PM on July 31, 2010
Response by poster: Thanks flug.
I just asked her about the possibility of your solution (ie using smaller and larger groups within the session to ensure everyone meets everyone else).
Apparently the groups have to contain even numbers of people due to some sort of pairing game going on in each group. Sorry to add that constraint; I didn't know until I told her your solution.
posted by foggy out there now at 1:21 PM on July 31, 2010
I just asked her about the possibility of your solution (ie using smaller and larger groups within the session to ensure everyone meets everyone else).
Apparently the groups have to contain even numbers of people due to some sort of pairing game going on in each group. Sorry to add that constraint; I didn't know until I told her your solution.
posted by foggy out there now at 1:21 PM on July 31, 2010
Actually, I think if it can't be done with groups of 6, then it can only be done with groups of 2 or else the whole group at once. Reason being: each person needs to meet 35 other people, and they're meeting (groupsize - 1) people each round, so group size needs to be one more than a factor of 35 so that everyone is met is an integral number of rounds. Factors of 35 are 1, 5, 7, 35, so possible group sizes are 2, 6, 8, 36. 8 doesn't divide 36 evenly, so that only leaves 2 and 36.
posted by PMdixon at 1:42 PM on July 31, 2010
posted by PMdixon at 1:42 PM on July 31, 2010
the groups have to contain even numbers of people
From a practical point of view your best option for dealing with that is just to adjust the groups on the spot--either by moving someone from an odd-numbered group to another odd-numbered group or by having a few floaters who can join the odd-numbered groups to make them even, or some combination of those two tactics.
Even if we discover this mythical 6-person X 7 meeting perfect solution, what will you do when one or two people can't make it at the last minute or arrive late?
(And with a group of 36, a few missing/late is pretty much inevitable.)
posted by flug at 2:02 PM on July 31, 2010
From a practical point of view your best option for dealing with that is just to adjust the groups on the spot--either by moving someone from an odd-numbered group to another odd-numbered group or by having a few floaters who can join the odd-numbered groups to make them even, or some combination of those two tactics.
Even if we discover this mythical 6-person X 7 meeting perfect solution, what will you do when one or two people can't make it at the last minute or arrive late?
(And with a group of 36, a few missing/late is pretty much inevitable.)
posted by flug at 2:02 PM on July 31, 2010
Response by poster: Even if we discover this mythical 6-person X 7 meeting perfect solution, what will you do when one or two people can't make it at the last minute or arrive late?
You're right. There's just no way to count on a certain number of people showing up. She says she can drop the pairing game since having everyone meet everyone else without repeats is more important.
Thanks everybody.
posted by foggy out there now at 2:09 PM on July 31, 2010
You're right. There's just no way to count on a certain number of people showing up. She says she can drop the pairing game since having everyone meet everyone else without repeats is more important.
Thanks everybody.
posted by foggy out there now at 2:09 PM on July 31, 2010
I tried out a scheme to brute force the 6 person X 7 meeting solution but it didn't really work as easily as I had hoped. (It was able to get the solution for the case of 16 people, for instance, but the 36 person case just has too many more permutations to crack without a more sophisticated approach.)
My impression is that it's actually quite a difficult and interesting problem.
FWIW!
posted by flug at 8:13 PM on July 31, 2010
My impression is that it's actually quite a difficult and interesting problem.
FWIW!
posted by flug at 8:13 PM on July 31, 2010
Here's another one based on diagonals. I haven't checked every single entry, but I think it works.
posted by chocolatepeanutbuttercup at 6:07 AM on August 1, 2010
01, 09, 17, 19, 27, 35 02, 10, 18, 20, 28, 36 03, 11, 13, 21, 29, 31 04, 12, 14, 22, 30, 32 05, 07, 15, 23, 25, 33 06, 08, 16, 24, 26, 34
posted by chocolatepeanutbuttercup at 6:07 AM on August 1, 2010
Oops, sorry, I didn't see that flug had already explained this method.
posted by chocolatepeanutbuttercup at 6:20 AM on August 1, 2010
posted by chocolatepeanutbuttercup at 6:20 AM on August 1, 2010
Response by poster: Here's another one based on diagonals.
Yeah, that's the 4th one I came up with originally, but it repeats on the fourth line. Persons 4 and 22 would have already met in the 2nd grouping.
My impression is that it's actually quite a difficult and interesting problem.
I'm happy to know I wasn't losing my wits; difficult indeed.
posted by foggy out there now at 9:52 AM on August 1, 2010
Yeah, that's the 4th one I came up with originally, but it repeats on the fourth line. Persons 4 and 22 would have already met in the 2nd grouping.
My impression is that it's actually quite a difficult and interesting problem.
I'm happy to know I wasn't losing my wits; difficult indeed.
posted by foggy out there now at 9:52 AM on August 1, 2010
There is a thread on this topic on sci.math that has some interesting further information and has the keywords to look up research related to this question if anyone is interested.
From the comments there, it looks like with the 36 people meeting in groups of six, only three meetings max are possible without repeats.
So it looks like you guys did pretty good to find those first three, and now you know why you couldn't find #4!
posted by flug at 2:54 PM on August 1, 2010
From the comments there, it looks like with the 36 people meeting in groups of six, only three meetings max are possible without repeats.
So it looks like you guys did pretty good to find those first three, and now you know why you couldn't find #4!
posted by flug at 2:54 PM on August 1, 2010
« Older Anybody know how to access the service menu on a... | Minidiscs falling out of drawer Newer »
This thread is closed to new comments.
Construct a graph on the 36C6 vertices representing possible groups. There's an edge between two vertices iff they have a person in common. Then the goal is to find the largest independent set. Obviously the maximum here is <=6, but it's difficult to say more unless this is a known special case I'm unaware of.
posted by PMdixon at 10:27 AM on July 31, 2010 [1 favorite]