3
$\begingroup$

[based on a true story]

I have here some climbing holds that I've made. There are two relevant parameters:

  1. The angle on the top, and
  2. The thickness, as shown.

Climbing Holds

Now it is definitely the case that $B_1$ is easier to hold than $S_1$. If we implement an easiness score for each hold — the smaller the number, the easier to grip — it is clear that the easiness score of $B_1$ $<$ easiness score of $S_1$. We will use the function $E(x)$ to denote the easiness score of a hold. Therefore, $E(B_1) < E(S_1)$.

Now, clearly $B_2$ is easier to hold than $S_2$, so we can say: $E(B_2) < E(S_2)$. We can also extend this to $B_3$ and $S_3$: $E(B_3) < E(S_3)$.

It is also the case that $B_1$ is easier to hold than $B_2$, which is easier to hold than $B_3$ — therefore, $E(B_1) < E(B_2) < E(B_3)$. Additionally, $E(S_1) < E(S_2) < E(S_3)$.

In general,

  1. The thicker the hold, the easier it is to grip;
  2. The more the hold slopes towards the wall, the easier it is to grip.

I want to arrange a course in which they go in order of increasing difficulty. There are 5 possible ways this could be done given the above constraints:

  1. $B_1$, $B_2$, $B_3$, $S_1$, $S_2$, $S_3$
  2. $B_1$, $B_2$, $S_1$, $B_3$, $S_2$, $S_3$
  3. $B_1$, $S_1$, $B_2$, $B_3$, $S_2$, $S_3$
  4. $B_1$, $B_2$, $S_1$, $S_2$, $B_3$, $S_3$
  5. $B_1$, $S_1$, $B_2$, $S_2$, $B_3$, $S_3$

But, what if I have 4 different angles? Or 5 angles? What's the general number of ways of arranging the routes?

And, trickier perhaps, what if I have 3 different thicknesses ($S$, $M$, $L$) and 3 different angles? Or in general, $n$ different thicknesses and $m$ different angles?

$\endgroup$
  • $\begingroup$ "It is also the case that B1"...? I think you forgot to finish a sentence. Looks like you typed it out in the source but it's rendering differently since you used a ">". $\endgroup$ – Hugh Oct 20 '18 at 2:54
  • 1
    $\begingroup$ Yes - I started fixing the problem but you beat me to it. I've still placed my edit in the edit queue, since I made some visual/structural edits that improve the overall clarity of the question. You're more than welcome to un-do it if you feel that it complicates things or changes the question you're asking. I also added my own question to the end, simply out of curiosity. $\endgroup$ – Hugh Oct 20 '18 at 3:22
  • $\begingroup$ Although I love this problem, it does seem a bit "Math SE" in terms of the combinatorics. But, I'm going to let it slide, for now. $\endgroup$ – Hugh Oct 20 '18 at 3:26
2
$\begingroup$

To build your course from top to bottom, you can always choose the next available S or B (the lowest-numbered one remaining) provided that you never have more S's than B's on your wall.

You can visualise this as an $n\times n$ square grid where you have to go from the top-left $(0,0)$ corner to the bottom-right $(n,n)$ corner by travelling along the edges down or to the right only, whilst also staying on or below the diagonal of the square. Every downwards move is choosing the next hold to be a B, every move to the right means you choose an S hold. The number of paths to $(n,m)$ is then equal to the number of ways to build the wall with $n$ S-holds and $m$ B-holds. You can count the number of ways to do this just by filling in the numbers on the grid as follows:

 
 1  -  -  -  -  -
 1  1  -  -  -  -
 1  2  2  -  -  -
 1  3  5  5  -  -
 1  4  9 14 14  -
 1  5 14 28 42 42
 
Each entry is the sum of the number above it and the number to its left, where everything outside the triangle is considered zero.
For example, at three steps down and three to the right (i.e. fourth row and fourth column) there is the number $5$, the number of climbing walls with $3$ holds of each width.

Now we'd like a formula for these.

This is called the Catalan triangle: OEIS A008315
According to that page they have the formula $C(n,m) = \binom{n+m}{n}\frac{n-m+1}{n+1}$.

Proof of the formula:

For $n\ge m$ we have: $$C(n-1,m)+C(n,m-1) = \\ = \binom{n-1+m}{n-1}\frac{n-m}{n} + \binom{n+m-1}{n}\frac{n-m+2}{n+1}\\ = \frac{(n-1+m)!(n-m)}{n(n-1)!m!} + \frac{(n+m-1)!(n-m+2)}{(n+1)n!(m-1)!)}\\ = \frac{(n+m-1)!(n-m)}{n!m!} + \frac{(n+m-1)!(n-m+2)}{(n+1)!(m-1)!)}\\ = \frac{(n+m-1)!(n-m)(n+1)}{(n+1)!m!} + \frac{(n+m-1)!(n-m+2)m}{(n+1)!m!)}\\ = \frac{(n+m-1)!((n-m)(n+1)+(n-m+2)m)}{(n+1)!m!} \\ = \frac{(n+m-1)!(n^2-m^2+n+m)}{(n+1)!m!} \\ = \frac{(n+m-1)!(n+m)(n-m+1)}{(n+1)!m!} \\ = \frac{(n+m)!(n-m+1)}{(n+1)!m!}\\ = \binom{n+m}{n}\frac{n-m+1}{n+1}\\ = C(n,m)$$
Combine this with the fact that $C(n-1,n)=0$ and $C(n,0)=1$, this show that the formula follows the same rules we used to construct the numbers in the grid, so the formula must produce the same numbers.

For an equal number of S-holds and B-holds:

The numbers on the diagonal are the answers for when you have an equal number of S-holds as B-holds. Those numbers are the Catalan numbers: OEIS A000108
They have the formula $C(n,n)=\frac{(2n)!}{n!(n+1)!}$.

I don't know what you'd get if you generalise it to three or more thicknesses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.