Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Partition of a rectangle into squares problem"

(→‎Proof via Dirichlet's simultaneous rational approximation theorem)
m (proofreading)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
{{stub}}
 
 
==Problem statement==
 
==Problem statement==
−
Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational
+
Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational.
 +
----
 +
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==
 
==Proof via Dirichlet's simultaneous [[rational approximation]] theorem==
 
Without loss of generality, we may assume that both sides of our rectange are greater than <math>1</math>.
 
Without loss of generality, we may assume that both sides of our rectange are greater than <math>1</math>.
−
We can choose a positive integer <math>q</math> such that the product of every coordinate of every vertex of every square in our partition becomes almost an integer after multiplication by <math>q</math>. So we may assume that all these coordinates differ from integers by at most <math>\frac 15</math>. Let now <math>a</math> and <math>b</math> be the horizontal and the vertical side of our rectangle respectively and let <math>s_i</math> be the sides of the squares in the partition. Denote by <math>\tilde x</math> the nearest integer to <math>x</math>. Now, draw the horizontal lines at all half-integer heights (i.e., the heights <math>\pm\frac 1 2,\pm\frac 3 2,\dots</math>) and look at the total length <math>L</math> of these lines within our rectangle. On one hand, we have <math>L=a\tilde b</math> (there are <math>\tilde b</math> lines intersecting our rectangle and each of them intersects it by an interval of length <math>a</math>. On the other hand, looking at what happens in each square, we get <math>L=\sum_i s_i\tilde s_i</math>. Thus <math>a\tilde b=\sum_i s_i\tilde s_i</math>. Similarly, drawing the vertical lines through half-integer points, we arrive at the identity  
+
We can choose a positive integer <math>q</math> such that the product of every coordinate of every vertex of every square in our partition becomes almost an integer after multiplication by <math>q</math>. So, we may assume that all these coordinates differ from integers by, at most, <math>\frac 15</math>. Now let <math>a</math> and <math>b</math> be the horizontal and the vertical side of our rectangle, respectively, and let <math>s_i</math> be the sides of the squares in the partition. Denote by <math>\tilde x</math> the nearest integer to <math>x</math>. Now, draw the horizontal lines at all half-integer heights (i.e., the heights <math>\pm\frac 1 2,\pm\frac 3 2,\dots</math>) and look at the total length <math>L</math> of these lines within our rectangle. On one hand, we have <math>L=a\tilde b</math>. (There are <math>\tilde b</math> lines intersecting our rectangle and each of them intersects it by an interval of length <math>a</math>.) On the other hand, looking at what happens in each square, we get <math>L=\sum_i s_i\tilde s_i</math>. Thus <math>a\tilde b=\sum_i s_i\tilde s_i</math>. Similarly, drawing the vertical lines through half-integer points, we arrive at the identity  
 
<math>b\tilde a =\sum_i s_i\tilde s_i</math>. Thus <math>a\tilde b=b\tilde a</math>, i.e., <math>\frac a b=\frac {\tilde a}{\tilde b}\in\mathbb Q</math>.
 
<math>b\tilde a =\sum_i s_i\tilde s_i</math>. Thus <math>a\tilde b=b\tilde a</math>, i.e., <math>\frac a b=\frac {\tilde a}{\tilde b}\in\mathbb Q</math>.

Latest revision as of 12:50, 26 June 2006

Problem statement

Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational.

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_i s_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$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Partition_of_a_rectangle_into_squares_problem&oldid=4745"