Have 40 people at 4 tables: how to switch tables so that the minimum number of people possible are sitting with someone at their original table

Question

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) 
}

Answer 1

[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.