On an $n$ × $n$ board, the set of all squares that are located on or below the main diagonal of the board is called the$n-ladder$. For example, the following figure shows a $3-ladder$: [asy][asy] draw((0,0)--(0,3)); draw((0,0)--(3,0)); draw((0,1)--(3,1)); draw((1,0)--(1,3)); draw((0,2)--(2,2)); draw((2,0)--(2,2)); draw((0,3)--(1,3)); draw((3,0)--(3,1)); [/asy][/asy] In how many ways can a $99-ladder$ be divided into some rectangles, which have their sides on grid lines, in such a way that all the rectangles have distinct areas?
Problem
Source: 2010 Peru Iberoamerican TST problem 6
Tags: combinatorics
trk08
11.05.2023 03:20
In a $n-ladder$, any two of the $1\times 1$ squares that are on the diagonal cannot be in the same rectangle. Since there are $n$ of these squares, there must be at least $n$ rectangles. Also, since they must all have different areas, the minimum possible sum of these $n$ rectangles must be:
\[1+2+\dots+n=\frac{n(n+1)}{2},\]which is the total number of squares in this $n-ladder$. This means we must have all of the follwing areas of rectangles:
\[1,2\dots, n.\]
The only way we can have all of these rectangles be placed is if the all have a width of $1$. There are two ways to place the largest one. After we do so, we get a $(n-1)-ladder$ and by a similar process, there are two ways to place the largest one here. If we keep doing this we can see there re a total of $2^{n-1}$ ways.
Thus, the answer is $\boxed{2^{98}}$
ReaperGod
11.05.2023 04:17
trk08 wrote: The only way we can have all of these rectangles be placed is if the all have a width of $1$. This means that there is a total of $2$ ways to place them. There are actually $2^{n-1}$ ways to place them.
trk08
11.05.2023 04:25
ReaperGod wrote: trk08 wrote: The only way we can have all of these rectangles be placed is if the all have a width of $1$. This means that there is a total of $2$ ways to place them. There are actually $2^{n-1}$ ways to place them. oops, I missed that