×   Home   Blog   Newsletter   Privacy   Contact Us   About

Social Distancing at the Bar

A puzzle for our times: A social distancing puzzle.
Restrictions are slowly being lifted, and Lefty’s bar is now able to serve customers (with constraints).
There are ten stools at the bar. The restrictions state that no customer can sit on a stool directly adjacent to another customer but, other than that, they can sit wherever they like. With this constraint, how many possible seating configurations are there?
How many different seating configurations are there with ten stools if no two adjacent stools are allowed to be occupied?
Advertisement:

Start Small

Let’s start small, and work our way up to ten stools. We'll start off with one stool, calculate the answer, then add another chair to the left.
With just one seating position, there are only two options; it is either occupied, or it is not:


   TOTAL: 2

With two seats, there are three options. Both are empty, or the first is occupied, or the last is occupied:

⊗⊗
✓⊗
⊗✓
   TOTAL: 3

With three available seats, there are five valid configurations:

⊗⊗⊗
⊗✓⊗
⊗⊗✓
✓⊗⊗
✓⊗✓
   TOTAL: 5

With four available seats, there are eight valid configurations:

⊗⊗⊗⊗
⊗⊗✓⊗
⊗⊗⊗✓
⊗✓⊗⊗
⊗✓⊗✓
✓⊗⊗⊗
✓⊗✓⊗
✓⊗⊗✓
   TOTAL: 8

Do you start to see a pattern?

Pattern

When we think about adding a new chair to the end, if the previous last outer-most chair is occupied, it's not be possible to add another filled one. Therefore, the only thing we can do is add an empty chair. So, a valid configuration is taking all the previous configurations a chair ago and simply adding a blank chair to the end. To this group we also need to add in the all configurations from two chairs ago, to which we append an occupied chair, followed by by a blank chair. This generates all the possible valid combinations: We can add a chair and a gap to any valid configuration two chairs ago, or a single gap to a a valid configuration one chair ago.
This is a Fibannoci Sequence! How neat is that?
Sn+1 = ('⊗' + Sn) + ('✓⊗' + Sn-1)
So, for five chairs, the only valid configurations for seating are the eight possible four chair configurations pre-pended with a blank chair, followed by the five valid three chair combinations pre-pended with an occupied chair and a blank chair. A total of thirteen valid seating configurations.

⊗⊗⊗⊗⊗
⊗⊗⊗✓⊗
⊗⊗⊗⊗✓
⊗⊗✓⊗⊗
⊗⊗✓⊗✓
⊗✓⊗⊗⊗
⊗✓⊗✓⊗
⊗✓⊗⊗✓
✓⊗⊗⊗⊗
✓⊗⊗✓⊗
✓⊗⊗⊗✓
✓⊗✓⊗⊗
✓⊗✓⊗✓
   TOTAL: 13

Fibonacci

Here is a table of the first configurations up to ten stools. As you can see, the answer for ten chairs is 144. You can read more about Fibonacci Numbers here, and find out details of how to derive a formula to determine them wihtout the need for recursion.
#Stools Safe Configurations
12
23
35
48
513
621
734
855
989
10144
There are 144 possible safe seating configurations for ten stools.
Please stay safe.