The staircase-covering problem

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

Let C(n)C(n) be the minimum number of rectangles one needs to cover a staircase of order nn 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)C(n).

Note by Shenal Kotuwewatta
4 years ago

No vote yet
1 vote

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I 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.

Renjith Joshua - 4 years ago

Log in to reply

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

Tan Li Xuan - 4 years ago

Log in to reply

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

Renjith Joshua - 4 years ago

Log in to reply

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

Ivan Koswara - 4 years ago

Log in to reply

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

C(n)nC(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)nC(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 nn top-left corners of rectangles in our tiling, or, at least nn rectangles.

Ben Frankel - 4 years ago

Log in to reply

Claim: C(n)=n1 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.

Calvin Lin Staff - 4 years ago

Log in to reply

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

Tan Li Xuan - 4 years ago

Log in to reply

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

Ivan Koswara - 4 years ago

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×(n+1) n \times (n+1) rectangle instead?

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

Calvin Lin Staff - 4 years ago

Log in to reply

@Calvin Lin I take it as "cut the square with one diagonal, and remove the squares that are also cut apart with the diagonal; the rest is two congruent pieces, each piece is a staircase".

Ivan Koswara - 4 years ago

Log in to reply

@Ivan Koswara That is what I meant.

Shenal Kotuwewatta - 4 years ago

Log in to reply

jee advance2015 paper 2 ellipse question

Rahul Jain - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...