This mind-bender from combinatorics demonstrates how a seemingly unrelated problem can be mapped to the solution of another problem.
This problem is based on a very famous concept from Combinatorial Mathematics, and demonstrates how an apparently unrelated problem can be mapped to an existing problem and solved using its solution.
We start by taking an empty $2 \times 6$ grid as shown below, and start filling up the numbers in increasing order, that is, $1, 2, ..., 12$
| $\ $ | $\ $ | $\ $ | $\ $ | $\ $ | $\ $ |
| $\ $ | $\ $ | $\ $ | $\ $ | $\ $ | $\ $ |
-----------book page break-----------
We can see that each number can go to a cell which has no vacant cell either above it or to the left of it.
While placing the integer $1$, there is only one cell which has no vacant cell either above or to the left, which is the top left cell of the grid.
Therefore, we get:
| $1$ | $*$ | $\ $ | $\ $ | $\ $ | $\ $ |
| $*$ | $\ $ | $\ $ | $\ $ | $\ $ | $\ $ |
The grid above also shows the possible places where $2$ can be placed. If we place $2$ in any cell other than the ones marked with $*$ it means $2$ will have an integer greater than $2$ either on the top or to the left. Let's say we place $2$ in either one of the cells as shown below. The cells marked with $*$ shows the possible positions for the next value $3$:
| $1$ | $2$ | $*$ | $\ $ | $\ $ | $\ $ |
| $*$ | $\ $ | $\ $ | $\ $ | $\ $ | $\ $ |
or
| $1$ | $*$ | $\ $ | $\ $ | $\ $ | $\ $ |
| $2$ | $\ $ | $\ $ | $\ $ | $\ $ | $\ $ |
Likewise we can fill the grid by placing the next higher integer in the rightmost unfilled cell of either the top row or the bottom row, with the condition that the number of filled cells in the bottom row at any point in time cannot exceed those in the top row.
Now, we see that if we consume the given integers in order, we can choose the left-most unfilled cell of either the top row or the bottom row, with the condition that the filled cells in the bottom row cannot exceed the ones in the top row.
-----------book page break-----------
This maps directly to the Catalan Number $(C_n)$ problem of valid arrangement of $2n$ parenthesis where the number of closing parenthesis cannot exceed the number of opening parenthesis at any point inside an arrangement. In this case choosing the top row cell corresponds to an opening parenthesis and choosing a bottom row cell corresponds to a closing parenthesis. At any point in time the number of filled cells in the bottom row cannot exceed that in the top row.
Therefore, our answer is the sixth Catalan Number $C_{6} = \dfrac{1}{6 + 1} \dbinom{12}{6} = 132$. We can learn more about Catalan Numbers, including its derivation .