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