THE BANQUET SEATING PROBLEM
Alexis Jane Torre1, Ashley Scruse2, Michelle Rosado3, Francis Su4.
1TheUniversity of Arizona, Tucson, AZ, 2Clark Atlanta University, Atlanta, GA, 3University of Puerto Rico Mayaguez Campus, Mayaguez, PR, 4Harvey Mudd College, Claremont, CA.
Suppose you are planning a banquet and want to seat n = mk people around k tables with m people at each table. Each person gives you a list of j people next to whom they would enjoy sitting. What is the smallest j for which you can always make a seating arrangement that would seat each person next to one of the people on their list? We show that j must be strictly more than half of n, the total number of people. Our key tool is a particular blue-green-red lemma that helps us construct worst-case scenario seating arrangements. We consider cases with 2 tables and more than 2 tables.