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 "2004 USAMO Problems/Problem 3"

m (→‎Problem)
(→‎Solution: official solution)
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
We will show that a dissection satisfying the requirements of the problem is possible if and only if <math>k\neq 1</math>.
 +
 
 +
We first show by contradiction that such a dissection is not possible when <math>k = 1</math>. Assume that we have such a dissection. The common boundary of the two dissecting polygons must be a single broken line connecting two points on the boundary of the square (otherwise either the square is subdivided in more than two pieces or one of the polygons is inside the other). The two dissecting polygons must have the same number of vertices. They share all the vertices on the common boundary, so they have to use the same number of corners of the square as their own vertices. Therefore, the common boundary must connect two opposite sides of the square (otherwise one of the polygons will contain at least three corners of the square, while the other at most two). However, this means that each of the dissecting polygons must use an entire side of the square as one of its sides, and thus each polygon has a side of length 1. A side of longest length in one of the polygons is either a side on the common boundary or, if all those sides have length less than 1, it is a side of the square. But this is also true of the polygon, which means that the longest side length in the two polygons is the same. This is impossible since they are similar but not congruent, so we have a contradiction.
 +
 
 +
We now construct a dissection satisfying the requirements of the problem when <math>k\neq 1</math>. Notice that we may assume that <math>k > 1</math>, because a <math>1\times k</math> rectangle is similar to a <math>1\times\frac{1}{k}</math> rectangle.
 +
 
 +
We first construct a dissection of an appropriate chosen rectangle (denoted by <math>ABCD</math> below) into two similar noncongruent polygons. The construct depends on two parameters (<math>n</math> and <math>r</math> below). By appropriate choice of these parameters we show that the constructed rectangle can be made similar to a <math>1\times k</math> rectangle, for any <math>k > 1</math>. The construction follows.
 +
 
 +
Let <math>r > 1</math> be a real number. For any positive integer <math>n</math>, consider the following sequence of <math>2n + 2</math> points:
 +
<cmath>A_0 = (0,0), A_1 = (1,0), A_2 = (1,r), A_3 = (1 + r^2, r), \\
 +
A_4 = (1 + r^2, r + r^3), A_5 = (1 + r^2 + r^4, r + r^3),</cmath>
 +
and so on, until
 +
<cmath>A_{2n+1} = (1 + r^2 + r^4 + \cdots + r^{2n}, r + r^3 + r^5 + \cdots + r^{2n - 1}).</cmath>
 +
Define a rectangle <math>ABCD</math> by
 +
<cmath>A = A_0, B = (1 + r^2 + \cdots + r^{2n}, 0), C = A_{2n + 1}, \text{ and }D = (0, r + r^3 + \cdots + r^{2n - 1}).</cmath>
 +
The sides of the <math>(2n+2)</math>-gon <math>A_1A_2\ldots A_{2n+1}B</math> have lengths
 +
<cmath>r, r^2, r^3, \ldots, r^{2n}, r + r^3 + r^5 + \cdots + r^{2n-1}, r^2 + r^4 + r^6 + \cdots + r^{2n},</cmath>
 +
and the sides of the <math>(2n+2)</math>-gon <math>A_0A_1A_2\ldots A_{2n}D</math> have lengths
 +
<cmath>1, r, r^2, \ldots, r^{2n-1}, 1 + r^2 + r^4 + \cdots + r^{2n-2}, r + r^3 + r^5 + \cdots + r^{2n-1},</cmath>
 +
respectively. These two polygons dissect the rectangle <math>ABCD</math> and, apart from orientation, it is clear that they are similar but noncongruent, with coefficient of similarity <math>r > 1</math>. The rectangle <math>ABCD</math> and its dissection are thus constructed.
 +
 
 +
The rectangle <math>ABCD</math> is similar to a rectangle of size <math>1\times f_n(r)</math>, where
 +
<cmath>f_n(r) = \frac{1 + r^2 + \cdots + r^{2n}}{r + r^3 + \cdots + r^{2n-1}}.</cmath>
 +
It remains to show that <math>f_n(r)</math> can have any value <math>k > 1</math> for appropriate choices of <math>n</math> and <math>r</math>. Choose <math>n</math> sufficiently large so that <math>1 + \frac{1}{n} < k</math>. Since
 +
<cmath>f_n(1) = 1 + \frac{1}{n} < k < k\frac{1 + k^2 + \cdots + k^{2n}}{k^2 + k^4 + \cdots + k^{2n}} = f_n(k)</cmath>
 +
and <math>f_n(r)</math> is a continuous function for positive <math>r</math>, there exists an <math>r</math> such that <math>1 < r < k</math> and <math>f_n(r) = k</math>, so we are done.
 +
 
 +
{{alternate solutions}}
 +
 
 
== Resources ==
 
== Resources ==
  
 
{{USAMO newbox|year=2004|num-b=2|num-a=4}}
 
{{USAMO newbox|year=2004|num-b=2|num-a=4}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 12:57, 18 July 2014

Problem

(Ricky Liu) For what values of $k > 0$ is it possible to dissect a $1 \times k$ rectangle into two similar, but incongruent, polygons?

Solution

We will show that a dissection satisfying the requirements of the problem is possible if and only if $k\neq 1$.

We first show by contradiction that such a dissection is not possible when $k = 1$. Assume that we have such a dissection. The common boundary of the two dissecting polygons must be a single broken line connecting two points on the boundary of the square (otherwise either the square is subdivided in more than two pieces or one of the polygons is inside the other). The two dissecting polygons must have the same number of vertices. They share all the vertices on the common boundary, so they have to use the same number of corners of the square as their own vertices. Therefore, the common boundary must connect two opposite sides of the square (otherwise one of the polygons will contain at least three corners of the square, while the other at most two). However, this means that each of the dissecting polygons must use an entire side of the square as one of its sides, and thus each polygon has a side of length 1. A side of longest length in one of the polygons is either a side on the common boundary or, if all those sides have length less than 1, it is a side of the square. But this is also true of the polygon, which means that the longest side length in the two polygons is the same. This is impossible since they are similar but not congruent, so we have a contradiction.

We now construct a dissection satisfying the requirements of the problem when $k\neq 1$. Notice that we may assume that $k > 1$, because a $1\times k$ rectangle is similar to a $1\times\frac{1}{k}$ rectangle.

We first construct a dissection of an appropriate chosen rectangle (denoted by $ABCD$ below) into two similar noncongruent polygons. The construct depends on two parameters ($n$ and $r$ below). By appropriate choice of these parameters we show that the constructed rectangle can be made similar to a $1\times k$ rectangle, for any $k > 1$. The construction follows.

Let $r > 1$ be a real number. For any positive integer $n$, consider the following sequence of $2n + 2$ points: \[A_0 = (0,0), A_1 = (1,0), A_2 = (1,r), A_3 = (1 + r^2, r), \\ A_4 = (1 + r^2, r + r^3), A_5 = (1 + r^2 + r^4, r + r^3),\] and so on, until \[A_{2n+1} = (1 + r^2 + r^4 + \cdots + r^{2n}, r + r^3 + r^5 + \cdots + r^{2n - 1}).\] Define a rectangle $ABCD$ by \[A = A_0, B = (1 + r^2 + \cdots + r^{2n}, 0), C = A_{2n + 1}, \text{ and }D = (0, r + r^3 + \cdots + r^{2n - 1}).\] The sides of the $(2n+2)$-gon $A_1A_2\ldots A_{2n+1}B$ have lengths \[r, r^2, r^3, \ldots, r^{2n}, r + r^3 + r^5 + \cdots + r^{2n-1}, r^2 + r^4 + r^6 + \cdots + r^{2n},\] and the sides of the $(2n+2)$-gon $A_0A_1A_2\ldots A_{2n}D$ have lengths \[1, r, r^2, \ldots, r^{2n-1}, 1 + r^2 + r^4 + \cdots + r^{2n-2}, r + r^3 + r^5 + \cdots + r^{2n-1},\] respectively. These two polygons dissect the rectangle $ABCD$ and, apart from orientation, it is clear that they are similar but noncongruent, with coefficient of similarity $r > 1$. The rectangle $ABCD$ and its dissection are thus constructed.

The rectangle $ABCD$ is similar to a rectangle of size $1\times f_n(r)$, where \[f_n(r) = \frac{1 + r^2 + \cdots + r^{2n}}{r + r^3 + \cdots + r^{2n-1}}.\] It remains to show that $f_n(r)$ can have any value $k > 1$ for appropriate choices of $n$ and $r$. Choose $n$ sufficiently large so that $1 + \frac{1}{n} < k$. Since \[f_n(1) = 1 + \frac{1}{n} < k < k\frac{1 + k^2 + \cdots + k^{2n}}{k^2 + k^4 + \cdots + k^{2n}} = f_n(k)\] and $f_n(r)$ is a continuous function for positive $r$, there exists an $r$ such that $1 < r < k$ and $f_n(r) = k$, so we are done.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2004 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_USAMO_Problems/Problem_3&oldid=62542"