# Waiters, Waiters, everywhere…

Today I was nerdsniped in the math office. My department head and two colleagues were working on this problem. I don’t know where it came from. But golly, did I enjoy it!

Imagine you have a row of waiters all facing forward. Each waiter has a beautiful silver platter that they are carrying. They have to choose: will they hold it directly in front of them, or on their left side, or on their right side? Here’s a diagram showing the three options (I imagine I’m looking down on the waiter.)

Okay, so there is one constraint. Remember the waiters are all standing in a row. So you can’t have the platters crash into each other. So here’s an example of an OK way the waiters could hold their platters, and then a NOT OK way the waiters could hold their platters.

So here’s the question… If you have n waiters standing in a row, how many different ways could they hold their platters?

I am not going to post the answer here, because I like to nerdsnipe! But if you want to check your answer, for 20 waiters, I calculate 267,914,296 different positions!

I bet you will have a lot of fun with this problem. One person in our office came up with many pages of work, and had a very complex approach which yielded some deep insights. She was super psyched about the intricate superstructure she was building. Another person got to review solving a particular type of thingie using matrices (I want to keep things vague so I’m going to use the word thingie to avoid giving anything away). I and another person had the same approach that led to a quick and elegant solution, but left me with rich conceptual questions to pursue. And as I started doing that, I realized that I had accidentally stumbled on the complex approach that the first person had taken.

Advertisements

## 5 comments

1. Hm, my number for 20 waiters is a LOT higher than that, but I could be doing something wrong. Oh! Sorry, I missed that you couldn’t use the fourth direction. Yes, I agree. These numbers are interesting and knowing the numbers can also help you figure out some reasons why they work.

2. I quickly got a recurrence relation that gave me the same answer as you for 20, then I used generating functions to solve the recurrence relation (with some help from Wolfram Alpha, since my algebra is a bit rusty). The closed-form solution gave the same results for 20 as the recurrence relation. It took me 10–20 minutes to do the problem, as I’ve not solved recurrence relations in a long time.

Nice problem.

3. Mike says:

The sequence w(n) =number of arrangements for n waiters is a sub-sequence of the Fibonacci series, which of course has many fascinating structural properties. In particular, the sequence consists of every other term of the Fibonacci series starting at 3.