Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

, , No Comments
Problem Detail: 

This question is motivated by an older question about tiling an orthogonal polygon with squares.

enter image description here         enter image description here

Given a $3\times 2$ rectangle like the first image, the second image is a square partition of that rectangle.

  • A square partitioning is a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
  • A minimum square partitioning is a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

How can we prove that the second image is a minimum square partitioning of the $3\times 2$ rectangle?

Can we generalize this to ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$? (see followup question )

Asked By : Realz Slaw

Answered By : Yuval Filmus

The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S_1$ touching the bottom-left corner. There is some square $S_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, requiring another square.

I'm not sure how to extend this proof beyond $w > 3$. Let me just mention that a classical result of Dehn shows that if an $h \times w$ rectangle can be tiled by squares then $h/w$ is rational, and moreover there is some integer $c$ such that if you scale everything by $c$ then all squares have integer sides.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16809

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback