Difference between revisions of "1997 IMO Problems/Problem 1"
(→Solution) |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 26: | Line 26: | ||
− | Part (a) | + | '''Part (a)''' |
case: <math>m</math> and <math>n</math> which are both even | case: <math>m</math> and <math>n</math> which are both even | ||
Line 82: | Line 82: | ||
− | Part (b) | + | '''Part (b)''' |
Since <math>f(m,n)= | Since <math>f(m,n)= | ||
Line 124: | Line 124: | ||
− | Part (c) | + | '''Part (c)''' |
Consider the case where <math>m=k</math> and <math>n=k+1</math> and k is even. | Consider the case where <math>m=k</math> and <math>n=k+1</math> and k is even. | ||
Line 130: | Line 130: | ||
<math>f(m,n)=f(k,k+1)=f(k,k)+h(k,1)=h(k,1)</math> | <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}{x | + | 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: | 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: | ||
Line 142: | Line 142: | ||
<math>h(k,1)=|S_{2}-S_{1}|=\left| \frac{4k-1}{12}-\frac{2k+1}{12} \right|=\frac{k-1}{6}</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 k | + | 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> | 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> | ||
Line 148: | Line 148: | ||
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. | 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}} | {{alternate solutions}} | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=1997|before=First Question|num-a=2}} | ||
+ | [[Category:Olympiad Geometry Problems]] | ||
+ | [[Category:3D Geometry Problems]] |
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 and , consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths and , lie along edges of the squares.
Let be the total area of the black part of the triangle and be the total area of the white part.
Let
(a) Calculate for all positive integers and which are either both even or both odd.
(b) Prove that for all and .
(c) Show that there is no constant such that for all and .
Solution
For any pair of positive integers and , consider a rectangle whose vertices have integer coordinates and whose legs, of lengths and , lie along edges of the squares.
Let , , , and , be the lower left vertex, lower right vertex, upper right vertex, and upper left vertex of rectangle respectively.
Let be the total area of the black part of the rectangle and be the total area of the white part.
Let
Part (a)
case: and which are both even
Since and are both even, the total area of the rectangle is 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 and
Let be the midpoint of line . Them is at coordinate
Since both and are even, then has integer coordinates.
Starting with vertex , because the length of is even, then the color for the square inside rectangle closest to is the opposite color of the square inside rectangle closest to , then starting with vertex , because the length of is even, then the color of the square inside rectangle closest to is the opposite color of the square inside rectangle closest to . this means that the color of the square inside rectangle closest to is the same as the color of the square inside rectangle closest to . Likewise, the color of the square inside rectangle closest to is the same as the color of the square inside rectangle closest to .
This color pattern and the fact that the midpoint has integer coordinates indicates that triangle has the same color pattern as triangle rotated 180 degrees.
Therefore, the white area in triangle is the same as the white area in triangle and the black area in triangle is the same as the black area in triangle .
Thus and , which gives
Therefore when both and are even.
case: and which are both odd
Since and are both odd, the total area of the rectangle is which is also odd
Since the total area is odd, then is not an integer but and are.
This means that in the rectangle there are squares of one color and squares of the other color
Let be the midpoint of line . Them is at coordinate Since both and are odd, then has non-integer coordinates coordinates but their decimal portions are both . This means that lies in the middle of the center square.
Starting with vertex , because the length of is odd, then the color for the square inside rectangle closest to is the same color of the square inside rectangle closest to , then starting with vertex , because the length of is odd, then the color of the square inside rectangle closest to is the same color of the square inside rectangle closest to . this means that the color of the square inside rectangle closest to is the same as the color of the square inside rectangle closest to . Likewise, the color of the square inside rectangle closest to is the same as the color of the square inside rectangle closest to .
This color pattern and the fact that the midpoint in in the center of the middle square that triangle has the same color pattern as triangle rotated 180 degrees.
Therefore, the white area in triangle is the same as the white area in triangle and the black area in triangle is the same as the black area in triangle .
Thus
Therefore when both and are odd.
To summarize part (a),
Part (b)
Since then for these cases the minimum values that and can have are 1. So for the cases where both are odd or both are even with equality at
Now we need to find the case were one of them is odd and the other one is even.
case is odd and is even, means that is even
Therefore
,
where 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 area of such triangle. Thus,
when is odd and is even
Which also means that
when is odd and is even
Now we look at the case where is even and is odd, means that is even
Therefore
,
Thus,
when is even and is odd
Therefore, for all four cases: and are both odd; and are both even; is odd with is even; and is even with is odd we have:
with equality at
Part (c)
Consider the case where and and k is even.
We're going to calculate noticing that the region for in will be the triangle formed by lines , and .
So, to calculate 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:
Then,
Thus for even we have
Since for this case, , then there is no upper bound for this case. Since part (c) describes an upper bound for all and , then having found one case where there is no upper bound means that there is no upper bound when considering all and
Therefore, there is no constant such that for all and because 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.
See Also
1997 IMO (Problems) • Resources | ||
Preceded by First Question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |