Meathead Math - Plate Permutation [Solution]

Solution for the week of 2/9/15

Our problem from 2/16/15 was

[…] you find yourself in the squat rack. Great, squat is one of your best exercises. In fact, in order to get a good workout, you need to add 5 plates to each side! Of course, you know from experience that you can’t just load each of the plates arbitrarily. In particular, if one side has ≥3 plates more than the other side, the bar will become too imbalanced and the weight will come crashing down (ignore the physics for now and just assume that this is true). How many unique ways are there to add plates to the bar so that each side has 5 plates and one side never has ≥3 plates more than the other side?

How about if we need to load up N plates? And what if the balance of bar in the rack is modified so that the bar will tip if one side as ≥m more plates than the other side?

Solution

Some of you may have recognized that this problem can be modeled by a Dyck path with some additional constraints applied.

All the Dyck paths of length 6. Image from Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Typically Dyck path can’t go below the x axis but that won’t bu sufficient for our situation. We need to apply the “no more that two additional plates on a particular side” constraint. But there’s two ways we can apply this and our choice depends on what we consider to be a unique barbell configuration. If choose not to distinguish between the right and left side (i.e. 1 plate on the left and 0 on the right is the same as 0 on the left and 1 on the right), then we can model this problem as a Dyck path with the constraints that the path never goes below the x-axis and never goes above the line y=2. If we do distinguish between the left and right side, then we can model this problem as a Dyck path with the constraints that the path never goes below y=-2 and never goes above the line y=2. I've chosen not to distinguish between the side.

At first glance, this problem seems like it could benefit from the reflection principal, which is a standard technique for handing lattice paths with constraints. However, we will note that we are dealing with two different constraints here which complicates this approach significantly. If we wanted to take this approach, we could attempt to model the problem by counting all the possible paths from (0,0) to (10,0) or (2N,0) and then subtracting the paths that violate the constraints. However, having the two constraints means we would need to account for the paths that violate both constraints, which I couldn't figure out how to do.

\(\begin{align*} & |\text{valid Dyck paths}| = \binom{2N}{N} \\ & - \left( \binom{2N}{N+1} + \binom{2N}{N+2} - |\text{paths violating constraint 1 and 2}| \right) \end{align*} \)

Instead of using the reflection principal, we can write a recursive relationship (think of the Dyck paths sort of like a Markov chain). The chain can be in three possible states: 0, 1, and 2. The state represents the difference between the number of plates on the left and right side. The chain starts in state 0 and ends in state 0 after 10 steps. With this, we just need to determine the relationship between the different states

We first note that if we are in state 0, we can only move to state 1. If we are in state 2, we can only move to state 1. If we are in state 1, we can move to state 0 or state 2. This gives us the following relationships:

\(\begin{align*} s_0(t+1) &= s_1(t) \\ s_1(t+1) &= s_0(t) + s_2(t) \\ s_2(t+1) &= s_1(t) \end{align*}\)

Our initial conditions are:

\(\begin{align*} s_0(0) &= 1 \\ s_1(0) &= 0 \\ s_2(0) &= 0 \end{align*}\)

We want to find s₀(10). So let's try iterating this out and see if a pattern emerges

\(\begin{align*} s_0(1) &= 0 \\ s_0(2) &= s_1(1) = s_0(0) + s_2(0) = 1 \\ s_0(3) &= s_1(2) = s_0(1) + s_2(1) = 0 \\ s_0(4) &= s_1(3) = s_0(2) + s_2(2) = 1 + s_1(1) = 1 + 1 = 2 \\ s_0(5) &= s_1(4) = s_0(3) + s_2(3) = 0 + s_1(2) = 0 + 0 = 0 \\ s_0(6) &= s_1(5) = s_0(4) + s_2(4) = 2 + s_1(3) = 2 + 2 = 4 \\ s_0(7) &= s_1(6) = s_0(5) + s_2(5) = 0 + s_1(4) = 0 + 0 = 0 \\ s_0(8) &= s_1(7) = s_0(6) + s_2(6) = 4 + s_1(5) = 4 + 4 = 8 \\ \vdots \end{align*}\)

The following pattern seems to be emerging.

\(s_0(t) = \begin{cases} 0 & t \text{ is odd} \\ 2^{t/2 - 1} & t \text{ is even} \end{cases}\)

This can be verified with induction, which I will omit here but the details can be found here.

Substituting in t=2N=10 we get 16! And that’s our answer!

If anyone counted the situation where distinguish between the two sides, please comment with your solution. Also, if you’re interested in the generalized solution to the number of Dyck paths whose height is less than or equal to k, check out this post.

As always, please comment with any thoughts or feedback you had on this problem or if you approached it differently. Thanks for reading!