In the coordinate plane a rectangle with vertices $ (0, 0),$ $ (m, 0),$ $ (0, n),$ $ (m, n)$ is given where both $ m$ and $ n$ are odd integers. The rectangle is partitioned into triangles in such a way that (i) each triangle in the partition has at least one side (to be called a “good” side) that lies on a line of the form $ x = j$ or $ y = k,$ where $ j$ and $ k$ are integers, and the altitude on this side has length 1; (ii) each “bad” side (i.e., a side of any triangle in the partition that is not a “good” one) is a common side of two triangles in the partition. Prove that there exist at least two triangles in the partition each of which has two good sides.
Problem
Source: IMO ShortList 1990, Problem 14 (JAP 2)
Tags: analytic geometry, geometry, rectangle, combinatorics, IMO Shortlist
16.01.2010 05:54
We shall use the word "triangle" to refer to any triangle in the partition. A triangle with only one bad side is to said to be of kind I, otherwise it is said to be of kind II. Let $V$ be the set of the midpoints of all the bad sides, let $E$ be the set consisting of any line segment which joins two midpoints of bad sides for a triangle of kind II , let $G$ be the graph with $V$ as vertex set and $E$ as edge set. It is easy to show that each edge of $G$ is parallel to one of the axes and the distance from it to this axis is a half-integer , i.e., a number of the form $k+1/2$, where $k$ is an integer. for $P \in V$, let $d(P)$ denote the degree of $P$. Obviously, $d(P)$ is not greater than $2$ for all $P \in V$. we consider the following three cases. $(1)$: there exists a point $P$ such that $d(P)=0$. In this case, both the triangle with $P$ on their common ban side are of kind I, and the proof ends. $(2)$: there is a point $Q \in V$ such that $d(Q)=1$, then there exists a chain with $Q$ as its one extreme. Let $R$ be the other extreme of the chain, then $d(R)=1$. Both the triangle with $Q$ on its bad side and the triangle with $R$ on its bad side belong to kind I, in this case, the proof ends too. $(3)$: $d(P)=2$ for all $P \in V$. Then $G$ is a disjoint union of cycles. Now we divide the rectangle into $mn$ unit squares with integral lattice point as vertices. According to the construction of $G$ and the hypothesis that $d(P)=2$ for all $P \in V$, the central point of each unit square in the rectangle is passed by one and only one cycle. By coloring those unit square black and white alternately, we make the rectangle into an $m \times n$ chessboard. Each cycle passes through black and white squares alternately. Hence the number of the unit squares passed by a certain cycle of $G$ is an even integer. So is the total number of the unit squares in the rectangle .This contradicts the fact that $mn$ is an odd integer. This ends the proof.
15.06.2015 04:14
thanks a lot!!!!!!! :D :blush:
26.01.2017 11:42
sholly wrote: (3)Each cycle passes through black and white squares alternately I don't understand this line much, can someone clarify it?
27.06.2019 05:06
Color the rectangle with the standard black and white rectangle coloring. Call the offset of a triangle in the configuration the area of it which is black minus the area of it which is white. Call a triangle excellent if it has two good sides, and plain otherwise. Lemma. The offset of an excellent triangle is $\pm \frac12$, and the offset of a plain triangle is $0$. Proof. This is a simple computation for excellent triangles. As for plain triangles, just split the plain triangle in half with the altitude of length $1$, and use the same computations from before. $\blacksquare$ Since the "overall offset" of the entire rectangle is $1$, there must clearly be at least $2$ excellent triangles, so we're done. $\square$