The seating arrangement problem, version 1
Professor Plum has a dinner party with 25 guests. Her guests are seated at 5 tables, with 5 guests at each table. After each dish, a new seating arrangement is made so that every guest sits down at a table with guests they have not already shared a table with.
What is the maximum number of dishes that can be served at the dinner party?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Answer: You can serve at most 6 dishes at the party.
Motivation:
step one Each guest has 24 other guests to meet, and can dine with 4 of these at a time (since each table fits 5 guests). So a potential maximum number of dishes is 6, which would make all guests meet everyone else.
step two Can seating arrangements be made so that every guest sits down with every other guest? That is; can we make six seating arrangements without putting any guest together with someone they have already dined with? Yes, we can. For example like this:
Give all the tables a number, or something else that ranks them in a clear order. Name all the chairs at each table 0, 1, 2, 3 and 4. After each dish, the guest moves as many tables forward as the number on her chair, and sits down on the chair with the same number. (Someone on chair 2 moves forwards two tables between every dish, while someone on chair 0 doesn't move at all.)
It will take five movements (six dishes) before anyone at a table gets back to anyone else at the same table. Instead of making the sixth seating arrangement identical to the first one, you gather all guests with the same chair numbers together at one table.
(It should actually be explained why this procedure works, but I have problems writing it down in a short and concise way. I'd like to say it like this: "The distance between guests at a table increases by 1 every time they move. When the distance is 5, they meet again. It is important that noone gets back to the original table before the full circle, which would happen if you have 4 tables and someone moves 2 tables forward after each dish.")