Remove the unit squares lying on a main diagonal of a $(n+1) \times (n+1)$ square grid. You get two congruent shapes, each containing $\frac{n(n+1)}{2}$ unit squares. Call such a shape a staircase of order $n$. (For example, the above image shows a staircase of order $3$)

Let $C(n)$ be the minimum number of rectangles one needs to cover a staircase of order $n$ such that all unit squares in the staircase are covered, no two rectangles overlap, and no part of a rectangle is outside the staircase.

Find an explicit formula for $C(n)$.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI think C(n) should be equal to n itself. I guess you could give a straightforward statement based proof where you show separately that it cannot be greater than n, nor can it be less than n.

Log in to reply

We can easily show that $n$ rectangles is sufficient by covering each row with one rectangle. Then, we observe that a staircase of order $n$ has $n$ "stairs", and each of the rectangles can cover at most one stair. So, we need at least $n$ rectangles.

Log in to reply

Precisely what I meant. For some reason, the words 'necessary' and sufficient' eluded me when I made my previous comment :)

Log in to reply

More interesting is the number of ways to cover the staircase with $C(n)$ rectangles (there are $C_n$ ways where $C_n$ is the $n$-th Catalan number).

Log in to reply

I claim that $C(n) = n$.

$C(n) \le n$: We can always tile a staircase with as many rectangles as steps by covering each row with a long rectangle.

$C(n) \ge n$: We can never tile a staircase with less rectangles than steps. Consider some step's top-left corner: this corner must coincide with the top-left corner of a rectangle in the tiling in order for the step to be covered. Thus we must have at least $n$ top-left corners of rectangles in our tiling, or, at least $n$ rectangles.

Log in to reply

Claim: $C(n) = n-1$ (due to the way you indexed it).

There is a one-line proof of that claim. It is left as an exercise to the reader.

Log in to reply

Then wouldn't C(1) = 0? How would we cover a staircase of order 1 with 0 rectangles?

Log in to reply

I don't see why $C(n) = n-1$; a staircase of order $n$ has $n$ rows.

Log in to reply

I didn't understand the "divided by one of it's main diagonals". Won't it be more of a $n \times (n+1)$ rectangle instead?

Though, given that he says the image has order 3, I guess he did pick the natural ordering.

Log in to reply

Log in to reply

Log in to reply

jee advance2015 paper 2 ellipse question

Log in to reply