Social Distancing at the Bar Riddle

I came across the following puzzle yesterday (edited for relevancy):

There is a bar with 25 seats in a line. People are social-distancing so when they walk into the bar, they always try to find a seat farthest away from others. To comply with government restrictions, no two people can sit next to each other. If a person walks in and there are no available seats, they will leave. Where should the owner tell his first customer to sit in order to maximize the number of people in the bar?

In order to solve this problem, we can utilize some wishful thinking. The best-case scenario is when every person is seated exactly two away from everyone else:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25.

How can we produce such a sequence? Well, if we had every fourth person, then the other people can sit in-between them (while still maintaining a distance of 2):

1, 5, 9, 13, 17, 21, 25.

To obtain this configuration, we take every eighth person, so the remaining people can sit a distance of four away from everyone else:

1, 9, 17, 25.

Finally, to obtain this configuration, we either need to put the first person on seat 9 or 17. We used backtracking in order to determine the best starting seat.

For a visual solution, I created a MatLab program that would test out each starting location of the first customer and then generates how the other customers would fill out the bar. For the original puzzle, this creates the following graph:

maxconfig_25_2

The y-axis is the location of the first customer seated, while the x-axis shows the seating configuration according to the bars’ rules. The starred values indicate the optimal configuration, which occurs exactly when the first person is seated at 9. The relative size of each Polkadot is the order the customer is seated in the configuration, which is why the line $y=x$ has the largest dots.

In this case, we were able to seat $\lceil \frac{25}{2}\rceil=13$ people effectively. Can we always obtain this bound for a bar with $n$ seats?

Unfortunately, the answer is no, but this isn’t obvious to see. Plotting the number of seats against the maximum number of people seated gives the following graph:

MaxSeated

The stars indicate when the maximum number of people seated equals $\lceil \frac{n}{2}\rceil$ . It’s interesting to note the outliers here are when $n=15, 23, 27, 28, 29, 30, 31, 39$ .

Let’s take one of these specific values and see what goes wrong in our backtracking approach. For $n=15$ , the best possible scenario would be:

1, 3, 5, 7, 9, 11, 13, 15.

In order to obtain this, we take every fourth person as we did before:

1, 5, 9, 13.

To obtain this, we suspect we should seat the first customer at 9. However, plotting this shows this generates a different graph:

maxconfig_15_2

The sequence starting at 9 is 1, 3, 5, 7, 9, 12, 15. Why did we skip over 13? This is because our backtracking approach didn’t account for the selection mechanism.

Starting with 9, the second person selected will sit at 1. After this, the next person will sit at 15, then 5 to create the current configuration: 1, 5, 9, 15. The next person entering the bar will want to sit as far away from the other people as possible. Scanning all the seats, they’ll choose seat 12 since it’s 3 away from both 9 and 15. Therefore, 15 is a suboptimal starting value.

We noticed every value before this was optimal, which leads us to wonder if we can characterize all of the values of $n$ that give an optimal configuration.

Expanding the search up to $n=100$ gives the following values that are optimal:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 24 25 26 32 33 34 35 36 37 38 40 41 42 48 49 50 64 65 66 67 68 69 70 72 73 74 80 81 82 96 97 98.

I found that every number in the list above is of one of the forms

$2^a, 2^a+2^b, 2^a+2^b+1, 2^a+2^b+2,$

where $a$ and $b$ are non-negative integers. This leads me to conjecture that these forms contain all the initial values of $n$ that produce an optimal configuration, however, this may be a case of The Strong Law of Small Numbers at work.

If how closely everyone is seated together makes you a bit uneasy in the graphs, we can expand the gap between people. For a fixed number of people in the bar, $n=25$ , we vary the gap size, $g$ to produce the following seating configurations:

The starred values indicate the best seat configuration. Compare these with the graph of gap size 2 earlier. Notice the best first seat varies between 1 and 9.

We can now plot the number of people seated compared to gap size:

gapsize25

A value is starred if the maximum number of people seated equals $\lceil \frac{n}{g} \rceil$ . In this case, not only is length 25 optimal for a gap size of 2, but it’s optimal for every gap!

We wonder when this pattern will remain. Of the values of n above that were found to be optimal for a gap size of 2, the following are optimal for every gap size:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 24 25 26 32 33 48 49.

An example of a value of n which gives suboptimal gap sizes is n=68:

gapsize68

The gap sizes of 3, 6, 7, and 9 are all suboptimal. This is the same for n=69 and 70. Similarly, for n=80, 81, and 82, we have suboptimal gap sizes of 3, 6, 7, and 11.

Since the gap size of 3 seems to produce suboptimal behaviour for several values, we plot the number of seats compared to the maximum number of seats for $g=3$ :

gapsize3half

The starred values indicate when the max number of people seated equals $\lceil \frac{n}{3}\rceil$ . We see the initial part is a step function in threes, similar to $g=2$ .

gapsize3secondhalf

There is also a long valley around n=70 and n=80, as predicted above.

The full list of values of $n$ that are optimal for $g=3$ are given below:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 24 25 26 27 28 29 30 31 32 33 36 37 38 39 48 49 50 51 52 53 54 55 56 57 60 61 62 63 72 73 74 75 96 97 98 99 100.

A few closing thoughts to the reader:

Can we characterize the values of $n$ above similar to what we did for $g=2$ ?
Are any of these sequences on the Online Encyclopedia of Integer Sequences?
Has a full mathematical analysis been conducted? I’ve seen the XKCD Urinal Protocol Vulnerability, but this assumes the first person sits on the end.
Stay safe, and continue to practice social distancing everywhere you go!

Similar to Fermat’s Last Theorem

Let $n$ be a positive integer. Prove that there exist distinct positive integers $x, y, z$ such that $x^{n-1} + y^n = z^{n+1}.$ (Source: 1997 IMO Shortlist N6)

The equation $x^{n}+y^n=z^n$ is known to have no nontrivial solutions for $n\ge 3$ due to Fermat’s Last Theorem (if you’ve not read Fermat’s Enigma I highly recommend checking it out). This very similar looking equation, however, has an infinite number of solutions. In this blog post, we’ll examine how this difficult looking problem can be solved with one simple observation: $1+8=9$ .

For a concrete example of this, consider the case $n=3$ giving the equation $x^{2}+y^{3}=z^{4}.$ Assume we multiply the equation by a number of the form $2^{\alpha}\cdot 3^{\beta}$ . We then will have: $2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}.$ Since we want the first part to be a perfect square, we should have $2\mid \alpha$ and $2\mid \beta$ . Since the second part should be a perfect cube, we should have $3\mid (\alpha+3)$ and $3\mid \beta$ . Finally, since the last part should be a perfect fourth power, $4\mid \alpha$ and $4\mid (\beta+2)$ . Solving these system of linear congruences gives $\alpha=0$ and $\beta=6$ ! We get back the equation $3^6+3^6\cdot 2^3=3^8$ , from which we read off the solution $(x,y,z)=(3^3, 3^2\cdot 2, 3^2)=(27, 18, 9)$ .

We now attempt to generalize this technique. We begin by multiplying $1+8=9$ by $2^{\alpha}\cdot 3^{\beta}$ again to obtain $2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}.$ We then want the exponents on the leftmost term to be divisible by $n$ , on the middle term to be divisible by $n+1$ , and on the rightmost term to be divisible by $n+2$ . This is equivalent to:

$\begin{cases} \alpha&\equiv 0\pmod{n} \\ \alpha&\equiv -3\pmod{n+1} \\ \alpha&\equiv 0\pmod{n+2} \end{cases}$ and $\begin{cases} \beta&\equiv 0\pmod{n} \\ \beta&\equiv 0\pmod{n+1} \\ \beta&\equiv -2\pmod{n+2}. \end{cases}$

Notice that in the first case, the first and third conditions are equivalent to $\alpha\equiv 0\pmod{n(n+2)}$ . Since $\gcd(n, n+2)=\gcd(n+1, n+2)=1$ , we can use the Chinese Remainder Theorem to know that $\alpha$ has a unique solution mod $\text{lcm}(n, n+1, n+2)$ .

On the other hand, for $\beta$ , in the case that $n$ is even, $\gcd(n, n+2)=2$ , therefore, we have to use an extended version of the Chinese Remainder Theorem. Thankfully, since $\gcd(n, n+2)=2$ in this case and $0\equiv -2\pmod{2}$ , we are still guaranteed a unique solution for $\beta$ mod $\text{lcm}(n, n+1, n+2)$ .

Substituting these solutions in for $\alpha$ and $\beta$ gives a solution $(x,y,z)$ to the original equation. Once we have the congruences for $\alpha$ and $\beta$ , we can then find an infinite parameterized version of solutions for $(x,y,z)$ .

For instance, in the case of $n=3$ above, we had $\alpha\equiv 0\pmod{12}, \beta\equiv 6\pmod{12}$ . If we in general write $\alpha=12\alpha'$ and $\beta=12\beta'+6$ , we then find

$2^{12\alpha'}\cdot 3^{12\beta'+6}+2^{12\alpha'+3}\cdot 3^{12\beta'+6}=2^{12\alpha'}\cdot 3^{12\beta'+8}.$

This then translates into $(x,y,z)=(2^{6\alpha'}\cdot 3^{6\beta'+3}, 2^{4\alpha'+1}\cdot 3^{2+4\beta'}, 2^{3\alpha'}\cdot 3^{3\beta'+2})$ . Notice for $\alpha'=\beta'=0$ , this gives the solution triple $(x,y,z)=(27, 18, 9)$ found above.

It’s pretty interesting to me how when you change one small thing in the formulation of the problem (subtract $1$ from the exponent on $x$ and add $1$ to the exponent of $z$ ) gives an entirely new problem, where we go from no solutions to an infinite number!

Puzzling Integral Solutions

At the falls clubs fair for the Mathematical Sciences Society at University of Alberta, we put up a poster board with two challenging integrals, offering free t-shirts to anybody who solved them. We put out several mini-whiteboards for people to work on, and to my surprise, there was quite a bit of interest (free tshirts are always a great motivator!). Here’s the solutions to two of these challenges. I really like how the first one looks symbolically challenging, but conceptually is not, while the second one looks more elementary, but involves a clever trick courtesy of Richard Feynman.

Link to Integral Solutions