4
$\begingroup$

recently I encountered this problem: "Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational."

I have found the a solution which I need help to understand:

Clearly, every rectangle with rational ratio of sides can be partitioned into finitely many equal squares. Thus, the interesting part of the problem is the "only if" one. Proof via Dirichlet's simultaneous rational approximation theorem Without loss of generality, we may assume that both sides of our rectange are greater than $1$. We can choose a positive integer $q$ such that the product of every coordinate of every vertex of every square in our partition becomes almost an integer after multiplication by $q$. So, we may assume that all these coordinates differ from integers by, at most, $\frac 15$. Now let $a$ and $b$ be the horizontal and the vertical side of our rectangle, respectively, and let $s_i$ be the sides of the squares in the partition. Denote by $\tilde x$ the nearest integer to $x$. Now, draw the horizontal lines at all half-integer heights (i.e., the heights $\pm\frac 1 2,\pm\frac 3 2,\dots$) and look at the total length $L$ of these lines within our rectangle. On one hand, we have $L=a\tilde b$. (There are $\tilde b$ lines intersecting our rectangle and each of them intersects it by an interval of length $a$.) On the other hand, looking at what happens in each square, we get $L=\sum_i s_i\tilde s_i$. Thus $a\tilde b=\sum_is_i\tilde s_i$. Similarly, drawing the vertical lines through half-integer points, we arrive at the identity $b\tilde a =\sum_i s_i\tilde s_i$. Thus $a\tilde b=b\tilde a$, i.e., $\frac a b=\frac {\tilde a}{\tilde b}\in\mathbb Q$.

I didn't understood why did he had to use Dirichlet theorem in order to draw line on each side, particulary I didnt understood why did he had to do this and how everything in this part connected:

Without loss of generality, we may assume that both sides of our rectange are greater than $1$. We can choose a positive integer $q$ such that the product of every coordinate of every vertex of every square in our partition becomes almost an integer after multiplication by $q$. So, we may assume that all these coordinates differ from integers by, at most, $\frac 15$.

If anyone can please explain it, it would be great, thanks

reference for the problem and solution: https://artofproblemsolving.com/wiki/index.php/Partition_of_a_rectangle_into_squares_problem

I’m asking about the answer he gave, not about any other solution...

$\endgroup$
13
  • $\begingroup$ Where did you encounter the problem, please? Where did you find the solution? Where did the author use Dirichlet's Theorem? (It's not in anything you quoted.) $\endgroup$ Commented Jun 12, 2019 at 13:26
  • 1
    $\begingroup$ @GerryMyerson hey, I added a refference to the problem and the solution... $\endgroup$ Commented Jun 12, 2019 at 13:27
  • $\begingroup$ @GerryMyerson also, its not a duplicate , since this is another side of this problem( he asked if x/y is rattional then ...., and im asking the other side -if it can be partioned then..). also I'm asking about the answer I posted not the answer he added there... $\endgroup$ Commented Jun 12, 2019 at 13:29
  • $\begingroup$ The question as you quote it is an "if and only if" question. The question may not be a duplicate, but did you read the answer that was posted there? $\endgroup$ Commented Jun 12, 2019 at 13:34
  • $\begingroup$ @GerryMyerson Yes I did and I didnt understood it quite well , and I'm asking for help on how they solved it.... just what I wrote at the post.. $\endgroup$ Commented Jun 12, 2019 at 13:35

2 Answers 2

7
$\begingroup$

The solver wants to draw horizontal lines through the rectangle, and wants the number of horizontal lines to be $\tilde b$, which is the integer nearest the height of the rectangle. You can do this by drawing the lines at the half-integral heights $\pm1/2,\pm3/2,\pm5/2,\dots$. But things get messy if one or more of those horizontal lines coincides with an edge of a square, as the solver wants to break each horizontal line up into segments, and attribute each segment to exactly one of the squares in the tiling. So, you have to make sure that there are no edges at a half-integral height. That's where Dirichlet's Theorem On Diophantine Approximation comes in; it ensures that given any finite collection of numbers, there is a positive integer $q$ such that you can multiply each of the numbers by $q$ and the resulting numbers won't be half-integers (will in fact differ from the nearest integer by at most one-fifth).

Now the solver is also going to draw vertical lines, and these are also going to be at half-integers (so the number of vertical lines will be $\tilde a$), and these also have to miss the sides of the squares, so the finite collection of numbers to be multiplied by $q$ has to include all the horizontal coordinates, but that's still a finite collection of numbers, so Dirichlet applies.

But why one-fifth, when one-third would be good enough to avoid all the edges of squares? Well, you want the number of line segments in any given square to be $\tilde s_i$, so you want a square to have $s_i$ at least one-half if it has a line segment running through it. With coordinates as much as one-third away from the nearest integer, you could have a square of side one-third with a line segment through it; but with coordinates no more than one-fifth from an integer, a square must have side at least three-fifths to have a segment through it, and $3/5>1/2$.

I hope this helps.

$\endgroup$
1
$\begingroup$

Another (very nice and instructive) proof of this fact (together with the classic electric network approach to the whole theory of squaring of rectangles) is presented in a very good book by Paul Nahin called "Mrs Perkins's Electric Quilt and other Intriguing Stories of Mathematical Physics".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .