4
$\begingroup$

Just a few simple premises:

  • 40 people, 10 people per table
  • At some point you want every one to switch tables, and have a few people as possible sitting at a table with someone they sat with the first time around.

This is not a homework problem--this is an actual issue I'm encountering while trying to organize a networking event. There are two main questions:

1) Is it even possible to devise a reassignment scheme were everyone is sitting with an entirely new crowd?

2) Assuming the answer to (1) is no, what's a reasonable algorithm for reassigning that will make it so that as many people as possible are sitting with new people at their new table.

The reason I think the answer to (1) is "No", is because I did 100k simulations of random table reassignment for each person (code below), from that I found there were zero times where nobody was sitting at a table with someone they sat with in the first round. On average, the maximally "redundant" table (i.e. the one that had the most people who were previously sat together) had about 4.65 people who sat with each other the first time around, and there was about an 87% chance of that number being 4 or 5. The min appeared to be 3.

Beyond that I can't really wrap my head around this. If there's a name for problems like this, please let me know or, better yet, if you have a good answer, let's hear it. Thanks!

M = rep(0,100000)
x <- rep(1:4, each=10)
for(k in 1:100000)
{
 s <- sample( 1:40, 40 ) 
 x2 <- x[s]
 m1 <- max( summary(as.factor(x2[1:10])) ) 
 m2 <- max( summary(as.factor(x2[11:20])) ) 
 m3 <- max( summary(as.factor(x2[21:30])) ) 
 m4 <- max( summary(as.factor(x2[31:40])) )  
 M[k] <- max( c(m1,m2,m3,m4) ) 
 if( M[k] == 0 ) print(s) 
}
$\endgroup$
  • $\begingroup$ Hint: matrix(rep(letters[1:4], 10), 10, 4) Another hint: Generalized Pigeonhole Principle. $\endgroup$ – whuber Nov 28 '18 at 22:16
  • $\begingroup$ It is because of its connection to experimental designs that I see this question as within our range of topics on CV, though arguably it might also count as an optimization problem on which AI techniques are sometimes applied; however, there are multiple questions on this type of problem on math.SE (if it's on topic here it should stay; if it's not that's probably the best place for it) $\endgroup$ – Glen_b Nov 29 '18 at 2:22
  • $\begingroup$ Are you only wanting a single swap or do you need a solution for multiple swaps? $\endgroup$ – ReneBt Nov 29 '18 at 4:30
  • $\begingroup$ @ReneBt, I was only asking about a single swap but multiple swaps would be ideal. $\endgroup$ – how_to_seat Nov 29 '18 at 15:01
2
$\begingroup$

[I may return with some further comments and pointers on the later parts, since this answer doesn't presently suggest a general algorithm; going beyond 3 sittings in particular is not in general a solved problem, though there are some useful strategies, and lots of connections to related problems.]

This is closely related to the social golfer problem ("can $g$ groups of $k$ golfers play for $w$ weeks without playing with someone they've previously played with?"). [The original such problem - 20 years ago now - considered 8 groups of four golfers, and asked how many weeks they could play without repeating partners. 11 weeks could be ruled out, so interest focused on whether 10 weeks was possible, to which the answer eventually turned out to be 'yes'.]

There's also the much older Kirkman schoolgirl problem, which relates to 15 girls walking in triplets once each day and asking how they can do this for 7 days without anyone walking with someone they've previously accompanied.

[There are a number of variants on the social golfer problem. Some of those may relate more directly to your problem.]

Such problems are also intimately related to experimental design in statistics (e.g. many optimal solutions of the social golfer problem - arrangements giving the largest $w$ for given $g,k$ - are resolvable balanced incomplete block designs, or RBIBDs).

In relation to your two questions:

  1. It is possible for everyone avoid anyone they've sat with before on their second 'sitting' if there are at least as many tables as people per table (i.e. the table size is no more than the square root of the number of guests).

    Indeed, if tables are 'small' in this sense, you should be able to get at least 3 consecutive arrangements - "sittings" - where everyone sits with all-new people every time.

    So, for example, for 8 tables of 5 people I have a solution at hand for up to 6 "sittings" (this may have been surpassed more recently, since the results I am looking at right now are pretty old). Generally speaking, the smaller the tables, the more 'social' sittings can be accommodated.

    Your case has 'large' tables (more people per table than tables) so there is no 'social' second sitting.

  2. Three people together that have been together before will be the minimum achievable with a second sitting and 4 tables of 10.

    We can see fairly readily that it cannot be 2 (this is presumably what whuber is getting at by raising the generalized pigeonhole principle). Consider people from table A; on the first sitting we stamp their hand with an 'a'. Now we arrange them in pairs over the four tables, two at table A, two at table B, two at table C, two at table D. What are we to do with the two left over? They must sit at tables that already have a pair of people with "a" stamps.

    Consequently the minimum number of achievable repeats cannot be less than three. We might entertain the possibility it might be higher than three, but since you already have a solution where it's three, you know that it's achievable, we needn't waste further effort trying to establish that three is possible.

    You might then set about trying to minimize the number of "three-peats" / maximize the number of double-ups.

    Clearly you can get an average of "2.5" on the second sitting (half the people sit with 2 others they already sat with half with one person they already sat with). Here the lower-case letters refer to the 'stamps' on their hands (i.e. the table people were at in the first sitting):

      A: aaabbcccdd
      B: aabbbccddd
      C: aaabbcccdd
      D: aabbbccddd
    

    This should be the best achievable. Of the 9 other people at the table in round 2, on average 7.5 of them are 'new' and 1.5 of them we've already sat with.

$\endgroup$
  • $\begingroup$ As far as an algorithm goes, I suggested an effective one in a comment to the question: namely, create an array of tables $\times$ people with the original table identifiers, transpose it, and reform that into the original dimensions. That the best average must be no less than 2.5 on the second sitting is immediate from the Pigeonhole Principle. $\endgroup$ – whuber Nov 29 '18 at 14:35
  • $\begingroup$ Extremely helpful. Thanks @Glen_b. One ancillary question--I am having trouble seeing how the "i.e." is equivalent to the original statement in: "if there are at least as many tables as people per table (i.e. the table size is no more than the square root of the number of guests)." $\endgroup$ – how_to_seat Nov 29 '18 at 15:08
  • $\begingroup$ If you have $n$ people at $t$ tables, you will seat $s=n/t$ people per table. If $t\geq s$ then $n/s\geq s$ or $s^2\leq n$ (and correspondingly, $t^2\geq n$). $\endgroup$ – Glen_b Nov 29 '18 at 16:32
  • $\begingroup$ Got it, thanks again @Glen_b. I can't upvote, but I have accepted your answer. $\endgroup$ – how_to_seat Nov 29 '18 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.