Difference between revisions of "1997 IMO Problems/Problem 1"

Latest revision as of 01:20, 21 November 2023

Problem

In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternatively black and white (as on a chessboard).

For any pair of positive integers $m$ and $n$ , consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $m$ and $n$ , lie along edges of the squares.

Let $S_{1}$ be the total area of the black part of the triangle and $S_{2}$ be the total area of the white part.

Let $f(m,n)=|S_{1}-S_{2}|$

(a) Calculate $f(m,n)$ for all positive integers $m$ and $n$ which are either both even or both odd.

(b) Prove that $f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}$ for all $m$ and $n$ .

(c) Show that there is no constant $C$ such that $f(m,n)<C$ for all $m$ and $n$ .

Solution

For any pair of positive integers $m$ and $n$ , consider a rectangle $ABCD$ whose vertices have integer coordinates and whose legs, of lengths $m$ and $n$ , lie along edges of the squares.

Let $A$ , $B$ , $C$ , and $D$ , be the lower left vertex, lower right vertex, upper right vertex, and upper left vertex of rectangle $ABCD$ respectively.

Let $T_{1}$ be the total area of the black part of the rectangle and $T_{2}$ be the total area of the white part.

Let $g(m,n)=|T_{1}-T_{2}|$

Part (a)

case: $m$ and $n$ which are both even

Since $m$ and $n$ are both even, the total area of the rectangle $ABCD$ is $m \times n$ which is also even

Since every row has an even number of squares there are equally as many white squares than black squares for each row.

Since every column has an even number of squares there are equally as many white squares than black squares for each column.

This means that in the rectangle there are equal number of white squares and black squares.

Therefore $T_{1}=T_{2}=\frac{mn}{2}$ and $g(m,n)=|T_{1}-T_{2}|=0$

Let $M$ be the midpoint of line $AC$ . Them $M$ is at coordinate $(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})$

Since both $m$ and $n$ are even, then $M$ has integer coordinates.

Starting with vertex $A$ , because the length of $AB$ is even, then the color for the square inside rectangle $ABCD$ closest to $B$ is the opposite color of the square inside rectangle $ABCD$ closest to $A$ , then starting with vertex $B$ , because the length of $BC$ is even, then the color of the square inside rectangle $ABCD$ closest to $C$ is the opposite color of the square inside rectangle $ABCD$ closest to $B$ . this means that the color of the square inside rectangle $ABCD$ closest to $A$ is the same as the color of the square inside rectangle $ABCD$ closest to $C$ . Likewise, the color of the square inside rectangle $ABCD$ closest to $B$ is the same as the color of the square inside rectangle $ABCD$ closest to $D$ .

This color pattern and the fact that the midpoint $M$ has integer coordinates indicates that triangle $ABC$ has the same color pattern as triangle $CDA$ rotated 180 degrees.

Therefore, the white area in triangle $ABC$ is the same as the white area in triangle $CDA$ and the black area in triangle $ABC$ is the same as the black area in triangle $CDA$ .

Thus $S_{1}=\frac{T_{1}}{2}$ and $S_{2}=\frac{T_{2}}{2}$ , which gives $f(m,n)=\frac{g(m,n)}{2}=0$

Therefore $f(m,n)=0$ when both $m$ and $n$ are even.

case: $m$ and $n$ which are both odd

Since $m$ and $n$ are both odd, the total area of the rectangle $ABCD$ is $m \times n$ which is also odd

Since the total area is odd, then $\frac{mn}{2}$ is not an integer but $\frac{mn+1}{2}$ and $\frac{mn-1}{2}$ are.

This means that in the rectangle there are $\frac{mn+1}{2}$ squares of one color and $\frac{mn+1}{2}$ squares of the other color

$g(m,n)=|T_{1}-T_{2}|=\left| \frac{mn+1}{2}-\frac{mn-1}{2} \right|=1$

Let $M$ be the midpoint of line $AC$ . Them $M$ is at coordinate $(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})$ Since both $m$ and $n$ are odd, then $M$ has non-integer coordinates coordinates but their decimal portions are both $0.5$ . This means that $M$ lies in the middle of the center square.

Starting with vertex $A$ , because the length of $AB$ is odd, then the color for the square inside rectangle $ABCD$ closest to $B$ is the same color of the square inside rectangle $ABCD$ closest to $A$ , then starting with vertex $B$ , because the length of $BC$ is odd, then the color of the square inside rectangle $ABCD$ closest to $C$ is the same color of the square inside rectangle $ABCD$ closest to $B$ . this means that the color of the square inside rectangle $ABCD$ closest to $A$ is the same as the color of the square inside rectangle $ABCD$ closest to $C$ . Likewise, the color of the square inside rectangle $ABCD$ closest to $B$ is the same as the color of the square inside rectangle $ABCD$ closest to $D$ .

This color pattern and the fact that the midpoint $M$ in in the center of the middle square that triangle $ABC$ has the same color pattern as triangle $CDA$ rotated 180 degrees.

Therefore, the white area in triangle $ABC$ is the same as the white area in triangle $CDA$ and the black area in triangle $ABC$ is the same as the black area in triangle $CDA$ .

Thus $f(m,n)=\frac{g(m,n)}{2}=\frac{1}{2}$

Therefore $f(m,n)=\frac{1}{2}$ when both $m$ and $n$ are odd.

To summarize part (a),

$f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}$

Part (b)

Since $f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}$ then for these cases the minimum values that $m$ and $n$ can have are 1. So for the cases where both are odd or both are even $f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}$ with equality at $m=n=1$

Now we need to find the case were one of them is odd and the other one is even.

case $max\left\{ m,n \right\}$ is odd and $min\left\{ m,n \right\}$ is even, means that $max\left\{ m,n \right\}-1$ is even

Therefore $f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)=0$

$f(m,n)=f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\})$ ,

where $h(1,n)$ is the absolute value of the difference between the white area and black area of a triangle with base or size 1 and height n where this triangle is not necessarily a rectangular triangle.

Therefore $h(1,n) \le$ area of such triangle. Thus, $h(1,min\left\{ m,n \right\}) \le \frac{1}{2}min\left\{ m,n \right\}$

$f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\}) \le 0 +\frac{1}{2}min\left\{ m,n \right\}$

$f(m,n) \le \frac{1}{2}min\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is odd and $min\left\{ m,n \right\}$ is even

Which also means that

$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is odd and $max\left\{ m,n \right\}$ is even

Now we look at the case where $max\left\{ m,n \right\}$ is even and $min\left\{ m,n \right\}$ is odd, means that $min\left\{ m,n \right\}-1$ is even

Therefore $f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)=0$

$f(m,n)=f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\})$ ,

Thus, $h(1,max\left\{ m,n \right\}) \le \frac{1}{2}max\left\{ m,n \right\}$

$f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\}) \le 0 +\frac{1}{2}max\left\{ m,n \right\}$

$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is even and $min\left\{ m,n \right\}$ is odd

Therefore, for all four cases: $m$ and $n$ are both odd; $m$ and $n$ are both even; $max\left\{ m,n \right\}$ is odd with $min\left\{ m,n \right\}$ is even; and $max\left\{ m,n \right\}$ is even with $min\left\{ m,n \right\}$ is odd we have:

$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ with equality at $m=n=1$

Part (c)

Consider the case where $m=k$ and $n=k+1$ and k is even.

$f(m,n)=f(k,k+1)=f(k,k)+h(k,1)=h(k,1)$

We're going to calculate $h(k,1)$ noticing that the region for $h(k,1)$ in $f(m,n)$ will be the triangle formed by lines $y=kx$ , $y=\frac{k+1}{k}x$ and $x=k$ .

So, to calculate $h(k,1)$ we first calculate the total area of the black triangular regions within the triangle (assuming the first corner is white) with the following series formula:

$S_{1}=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1}{k}j-j \right)\left(j- \frac{k}{k+1}j \right)=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1-k}{k} \right)\left( \frac{k+1-k}{k+1} \right)j^{2}$

$S_{1}=\frac{1}{2k(k+1)}\sum_{j=1}^{k}j^{2}=\frac{1}{2k(k+1)}\frac{k(k+1)(2k+1)}{6}=\frac{2k+1}{12}$

Then, $S_{2}=\frac{k}{2}-S_{1}=\frac{k}{2}-\frac{2k+1}{12}=\frac{4k-1}{12}$

$h(k,1)=|S_{2}-S_{1}|=\left| \frac{4k-1}{12}-\frac{2k+1}{12} \right|=\frac{k-1}{6}$

Thus for even $k$ we have $f(k,k+1)=h(k,1)=\frac{k-1}{6}$

Since for this case, $C=\lim_{k \to \infty} f(k,k+1)=\lim_{k \to \infty} \frac{k-1}{6}=\infty$ , then there is no upper bound for this case. Since part (c) describes an upper bound for all $m$ and $n$ , then having found one case where there is no upper bound means that there is no upper bound when considering all $m$ and $n$

Therefore, there is no constant $C$ such that $f(m,n)<C$ for all $m$ and $n$ because $C \to \infty\;$ on some cases.

~ Tomas Diaz. orders@tomasdiaz.com

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

@@ Line 24: / Line 24: @@
 Let <math>g(m,n)=|T_{1}-T_{2}|</math>
-Part (a):
+'''Part (a)'''
 case: <math>m</math> and <math>n</math> which are both even
@@ Line 38: / Line 40: @@
 Therefore <math>T_{1}=T_{2}=\frac{mn}{2}</math> and <math>g(m,n)=|T_{1}-T_{2}|=0</math>
-Let <math>M</math> be the midpoint of line <math>AC</math>.  Them <math>M</math> is at coordinate <math>(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})</math>  Since both <math>m</math> and <math>n</math> are even, then <math>M</math> has integer coordinates.
+Let <math>M</math> be the midpoint of line <math>AC</math>.  Them <math>M</math> is at coordinate <math>(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})</math>
+Since both <math>m</math> and <math>n</math> are even, then <math>M</math> has integer coordinates.
 Starting with vertex <math>A</math>, because the length of <math>AB</math> is even, then the color for the square inside rectangle <math>ABCD</math> closest to <math>B</math> is the opposite color of the square inside rectangle <math>ABCD</math> closest to <math>A</math>, then starting with vertex <math>B</math>, because the length of <math>BC</math> is even, then the color of the square inside rectangle <math>ABCD</math> closest to <math>C</math> is the opposite color of the square inside rectangle <math>ABCD</math> closest to <math>B</math>.  this means that the color of the square inside rectangle <math>ABCD</math> closest to <math>A</math> is the same as the color of the square inside rectangle <math>ABCD</math> closest to <math>C</math>.  Likewise, the color of the square inside rectangle <math>ABCD</math> closest to <math>B</math> is the same as the color of the square inside rectangle <math>ABCD</math> closest to <math>D</math>.
@@ Line 71: / Line 75: @@
 Therefore <math>f(m,n)=\frac{1}{2}</math> when both <math>m</math> and <math>n</math> are odd.
+To summarize part (a),
+<math>f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}</math>
+'''Part (b)'''
+Since <math>f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}</math> then for these cases the minimum values that <math>m</math> and <math>n</math> can have are 1.  So for the cases where both are odd or both are even <math>f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}</math> with equality at <math>m=n=1</math>
+Now we need to find the case were one of them is odd and the other one is even.
-(a) Calculate <math>f(m,n)</math> for all positive integers <math>m</math> and <math>n</math> which are either both even or both odd.
+case <math>max\left\{ m,n \right\}</math> is odd and <math>min\left\{ m,n \right\}</math> is even, means that <math>max\left\{ m,n \right\}-1</math> is even
-(b) Prove that <math>f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}</math> for all <math>m</math> and <math>n</math>.
+Therefore <math>f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)=0</math>
-(c) Show that there is no constant <math>C</math> such that <math>f(m,n)<C</math> for all <math>m</math> and <math>n</math>.
+<math>f(m,n)=f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\})</math>,
+where <math>h(1,n)</math> is the absolute value of the difference between the white area and black area of a triangle with base or size 1 and height n where this triangle is not necessarily a rectangular triangle.
+Therefore <math>h(1,n) \le </math> area of such triangle.  Thus, <math>h(1,min\left\{ m,n \right\}) \le \frac{1}{2}min\left\{ m,n \right\}</math>
+<math>f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\}) \le 0 +\frac{1}{2}min\left\{ m,n \right\}</math>
+<math>f(m,n) \le \frac{1}{2}min\left\{ m,n \right\}</math> when <math>max\left\{ m,n \right\}</math> is odd and <math>min\left\{ m,n \right\}</math> is even
+Which also means that
+<math>f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}</math> when <math>max\left\{ m,n \right\}</math> is odd and <math>max\left\{ m,n \right\}</math> is even
+Now we look at the case where <math>max\left\{ m,n \right\}</math> is even and <math>min\left\{ m,n \right\}</math> is odd, means that <math>min\left\{ m,n \right\}-1</math> is even
+Therefore <math>f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)=0</math>
+<math>f(m,n)=f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\})</math>,
+Thus, <math>h(1,max\left\{ m,n \right\}) \le \frac{1}{2}max\left\{ m,n \right\}</math>
+<math>f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\}) \le 0 +\frac{1}{2}max\left\{ m,n \right\}</math>
+<math>f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}</math> when <math>max\left\{ m,n \right\}</math> is even and <math>min\left\{ m,n \right\}</math> is odd
+Therefore, for all four cases: <math>m</math> and <math>n</math> are both odd; <math>m</math> and <math>n</math> are both even; <math>max\left\{ m,n \right\}</math> is odd with <math>min\left\{ m,n \right\}</math> is even; and <math>max\left\{ m,n \right\}</math> is even with <math>min\left\{ m,n \right\}</math> is odd we have:
+<math>f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}</math> with equality at <math>m=n=1</math>
+'''Part (c)'''
+Consider the case where <math>m=k</math> and <math>n=k+1</math> and k is even.
+<math>f(m,n)=f(k,k+1)=f(k,k)+h(k,1)=h(k,1)</math>
+We're going to calculate <math>h(k,1)</math> noticing that the region for <math>h(k,1)</math> in <math>f(m,n)</math> will be the triangle formed by lines <math>y=kx</math>, <math>y=\frac{k+1}{k}x</math> and <math>x=k</math>.
+So, to calculate <math>h(k,1)</math> we first calculate the total area of the black triangular regions within the triangle (assuming the first corner is white) with the following series formula:
+<math>S_{1}=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1}{k}j-j \right)\left(j- \frac{k}{k+1}j \right)=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1-k}{k} \right)\left( \frac{k+1-k}{k+1} \right)j^{2}</math>
+<math>S_{1}=\frac{1}{2k(k+1)}\sum_{j=1}^{k}j^{2}=\frac{1}{2k(k+1)}\frac{k(k+1)(2k+1)}{6}=\frac{2k+1}{12}</math>
+Then, <math>S_{2}=\frac{k}{2}-S_{1}=\frac{k}{2}-\frac{2k+1}{12}=\frac{4k-1}{12}</math>
+<math>h(k,1)=|S_{2}-S_{1}|=\left| \frac{4k-1}{12}-\frac{2k+1}{12}  \right|=\frac{k-1}{6}</math>
+Thus for even <math>k</math> we have <math>f(k,k+1)=h(k,1)=\frac{k-1}{6}</math>
+Since for this case, <math>C=\lim_{k \to \infty} f(k,k+1)=\lim_{k \to \infty} \frac{k-1}{6}=\infty</math>, then there is no upper bound for this case.  Since part (c) describes an upper bound for all <math>m</math> and <math>n</math>, then having found one case where there is no upper bound means that there is no upper bound when considering all <math>m</math> and <math>n</math>
+Therefore, there is no constant <math>C</math> such that <math>f(m,n)<C</math> for all <math>m</math> and <math>n</math> because <math>C \to \infty\;</math> on some cases.
+~ Tomas Diaz. orders@tomasdiaz.com
 {{alternate solutions}}
+==See Also==
+{{IMO box|year=1997|before=First Question|num-a=2}}
+[[Category:Olympiad Geometry Problems]]
+[[Category:3D Geometry Problems]]

1997 IMO (Problems) • Resources
Preceded by First Question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "1997 IMO Problems/Problem 1"

Latest revision as of 01:20, 21 November 2023

Problem

Solution

See Also