Разделы 
Дополнительно
Задача по математике - 1738
2019-01-20 
На клетчатой бумаге нарисован прямоугольник, стороны которого образуют углы в $45^{\circ}$ с линиями сетки, а вершины не лежат на линиях сетки. Может ли каждую сторону прямоугольника пересекать нечетное число линий сетки?
Решение:
Первое решение. Допустим, это возможно для прямоугольника $ABCD$.
Пусть $AB$ - его наименьшая сторона. Выберем начало координат в узле сетки, и направим оси координат вдоль линий сетки так, чтобы среди вершин прямоугольника вершина A имела наименьшую абсциссу, а вершина $B$ - наименьшую ординату. Через $A_x, B_x, C_x, D_x$ и $A_y, B_y, C_y, D_y$ обозначим проекции вершин на оси (см. рис.). Абсциссы точек $A_x, B_x, C_x, D_x$ и ординаты точек $A_y, B_y, C_y, D_y$ - нецелые, так как вершины $A, B, C, D$ не лежат на линиях сетки. Так как $\vec{D_xC_x} = \vec{A_xB_x}$ и $A_xD_x = AD \cdot cos 45^{\circ} \geq AB \cdot \cos 45^{ \circ} = A_xB_x$, точки на оси $O_x$ лежат в порядке $A_x, B_x, D_x, C_x$. ($B_x$ и $D_x$ могут совпасть). Также, точки на оси $O_y$ лежат в порядке $B_y, A_y, C_y, D_y$. При этом
$A_xB_x = D_xC_x = B_yA_y = C_yD_y = AB \cdot \cos 45^{\circ}, B_xD_x = A_yC_y = (AD - AB) cos 45^{\circ}$.
Через $t_1, t_2, t_3, t_4, s_1, s_2$ обозначим количество точек с целыми координатами соответственно на отрезках $A_xB_x, B_yA_y, D_xC_x, C_yD_y, B_xD_x, A_yC_y$. На отрезке $A_xB_x$ ровно $t_1$ целочисленных точек, поэтому сторона $AB$ пересекает ровно $t_1$ вертикальных линий сетки; на отрезке $A_yD_y t_4 + s_2$ целочисленных точек, следовательно, сторона $AD$ пересекает ровно $t_4 + s_2$ горизонтальных линий сетки, и т. д. Таким образом, условие пересечения каждой стороной нечетного числа линий сетки эквивалентно нечетности чисел $t_1 +t_2, t_3 +t_4, t_1 +t_4 + s_1 + s_2, t_2 + t_3 + s_1 + s_2$.
Лемма. Если два отрезка равной длины $d$ расположены на числовой прямой так, что их концы нецелочисленны, то количества целых точек на этих отрезках отличаются не более, чем на 1.
В самом деле, если на отрезке с левым концом в нецелой точке $a$ и правым концом в нецелой точке $b$ лежит $k$ целых точек $n, n + 1,\cdots, n + k - 1,$ то $n - 1 < a < n$ и $n + k - 1 < b < n + k$, поэтому $k - 1 < d = b - a < k + 1$ и $d - 1 < k < d + 1$, т. е. $k = [d]$ или $k = [d] + 1$. Лемма доказана.
Из леммы следует, что числа $t_1, t_2, t_3, t_4$ отличаются не более, чем на 1, т. е. равны $t$ или $t + 1$, и также числа $s_1$ и $s_2$ равны $s$ или $s + 1$. Так как $t_1 +t_2$ нечетно, то $t_1 = t_2$. Пусть для определенности $t_1 = t, t_2 = t + 1$.
1) Если $t_3 = t,$ то $t_4 = t + 1$, так как $t_3 + t_4$ нечетно. Тогда $s_1 + s_2 = (t_1 + t_4 + s_1 + s_2) - (t_1 + t_4) = (t_1 + t_4 + s_1 + s_2) - (2_t +1)$ четно. Отсюда $s_1 = s_2$. Но тогда $(t_2 + s_2 +t_4) - (t_1 + s_1 +t_3) = 2$ - противоречие утверждению леммы для отрезков $A_xC_x и B_yD_y$.
2) Если же $t_3 = t + 1$, то $t_4 = t$. Тогда $s_1 + s_2 = (t_1 +t_4 + s_1 + s_2) - (t_1 +t_4)$ - нечетно, т. е. либо $s_1 = s, s_2 = s + 1$, либо $s_1 = s + 1, s_2 = s$. Первый случай противоречит утверждению леммы для отрезков $A_xD_x \: B_yC_y$, второй - для отрезков $B_xC_x$ и $A_yD_y$.
Второе решение. Предположим, такой прямоугольник $ABCD$ существует. Пусть $AB \geq \sqrt{2}$. Отложим на сторонах $AB$ и $CD$ отрезки $BB^{ \prime} = CC^{ \prime} = \sqrt{2}[АВ/\sqrt{2}]$. Тогда отрезки $BB^{ \prime}$ и $CC^{ \prime}$ пересекают по одной вертикальной и горизонтальной линии, а отрезок $B^{ \prime}C^{ \prime}$ получается из $BC$ переносом на вектор $\vec{BB^{ \prime}}$ с целыми координатами. Поэтому прямоугольник $AB^{ \prime}C^{ \prime}D$ также удовлетворяет условию. Продолжая такие действия, получим в результате прямоугольник, все стороны которого меньше $ \sqrt{2}$ (обозначим его опять $ABCD$). Тогда каждая сторона пересекает не более одной прямой каждого направления, т. е. ровно по одной прямой - либо вертикальной, либо горизонтальной.
Пусть $A$ - самая левая точка прямоугольника, а $B$ - самая нижняя, тогда $C$ - самая правая, а $D$ - самая верхняя. Если отрезки $AB$ и $BC$ пересекают вертикальные прямые, то ломаная $CDA$ их также пересекает, а горизонтальные прямые, соответственно, не пересекает. Тогда проекция $ABCD$ на горизонтальную прямую имеет длину больше 1 (между $A$ и $C$ две вертикальных прямых), а на вертикальную - меньше 1, что невозможно.
Если отрезки $AB$ и $BC$ пересекают (одну и ту же!) горизонтальную прямую, то $ABCD$ лежит в полосе между двумя соседними вертикалями, а тогда $AD$ и $DC$ также пересекают горизонтальную прямую, что невозможно по тем же причинам.
Остался единственный (с точностью до симметрии) случай - $AB$ и $CD$ пересекают одну и ту же вертикальную прямую $v$, а $BC$ и $AD$ - одну и ту же горизонтальную прямую $h$. Тогда $A$ и $В$ лежат под $h$, а $C$ - над $h$, поэтому $BC > AB$. Аналогично, $В$ и $C$ лежат правее $v$, а $D$ - левее $v$, поэтому $BC < CD$. Итого, $AB < BC < CD$, что невозможно.
Ответ. Не может.
На клетчатой бумаге нарисован прямоугольник, стороны которого образуют углы в $45^{\circ}$ с линиями сетки, а вершины не лежат на линиях сетки. Может ли каждую сторону прямоугольника пересекать нечетное число линий сетки?
Решение:
Первое решение. Допустим, это возможно для прямоугольника $ABCD$.
Пусть $AB$ - его наименьшая сторона. Выберем начало координат в узле сетки, и направим оси координат вдоль линий сетки так, чтобы среди вершин прямоугольника вершина A имела наименьшую абсциссу, а вершина $B$ - наименьшую ординату. Через $A_x, B_x, C_x, D_x$ и $A_y, B_y, C_y, D_y$ обозначим проекции вершин на оси (см. рис.). Абсциссы точек $A_x, B_x, C_x, D_x$ и ординаты точек $A_y, B_y, C_y, D_y$ - нецелые, так как вершины $A, B, C, D$ не лежат на линиях сетки. Так как $\vec{D_xC_x} = \vec{A_xB_x}$ и $A_xD_x = AD \cdot cos 45^{\circ} \geq AB \cdot \cos 45^{ \circ} = A_xB_x$, точки на оси $O_x$ лежат в порядке $A_x, B_x, D_x, C_x$. ($B_x$ и $D_x$ могут совпасть). Также, точки на оси $O_y$ лежат в порядке $B_y, A_y, C_y, D_y$. При этом
$A_xB_x = D_xC_x = B_yA_y = C_yD_y = AB \cdot \cos 45^{\circ}, B_xD_x = A_yC_y = (AD - AB) cos 45^{\circ}$.
Через $t_1, t_2, t_3, t_4, s_1, s_2$ обозначим количество точек с целыми координатами соответственно на отрезках $A_xB_x, B_yA_y, D_xC_x, C_yD_y, B_xD_x, A_yC_y$. На отрезке $A_xB_x$ ровно $t_1$ целочисленных точек, поэтому сторона $AB$ пересекает ровно $t_1$ вертикальных линий сетки; на отрезке $A_yD_y t_4 + s_2$ целочисленных точек, следовательно, сторона $AD$ пересекает ровно $t_4 + s_2$ горизонтальных линий сетки, и т. д. Таким образом, условие пересечения каждой стороной нечетного числа линий сетки эквивалентно нечетности чисел $t_1 +t_2, t_3 +t_4, t_1 +t_4 + s_1 + s_2, t_2 + t_3 + s_1 + s_2$.
Лемма. Если два отрезка равной длины $d$ расположены на числовой прямой так, что их концы нецелочисленны, то количества целых точек на этих отрезках отличаются не более, чем на 1.
В самом деле, если на отрезке с левым концом в нецелой точке $a$ и правым концом в нецелой точке $b$ лежит $k$ целых точек $n, n + 1,\cdots, n + k - 1,$ то $n - 1 < a < n$ и $n + k - 1 < b < n + k$, поэтому $k - 1 < d = b - a < k + 1$ и $d - 1 < k < d + 1$, т. е. $k = [d]$ или $k = [d] + 1$. Лемма доказана.
Из леммы следует, что числа $t_1, t_2, t_3, t_4$ отличаются не более, чем на 1, т. е. равны $t$ или $t + 1$, и также числа $s_1$ и $s_2$ равны $s$ или $s + 1$. Так как $t_1 +t_2$ нечетно, то $t_1 = t_2$. Пусть для определенности $t_1 = t, t_2 = t + 1$.
1) Если $t_3 = t,$ то $t_4 = t + 1$, так как $t_3 + t_4$ нечетно. Тогда $s_1 + s_2 = (t_1 + t_4 + s_1 + s_2) - (t_1 + t_4) = (t_1 + t_4 + s_1 + s_2) - (2_t +1)$ четно. Отсюда $s_1 = s_2$. Но тогда $(t_2 + s_2 +t_4) - (t_1 + s_1 +t_3) = 2$ - противоречие утверждению леммы для отрезков $A_xC_x и B_yD_y$.
2) Если же $t_3 = t + 1$, то $t_4 = t$. Тогда $s_1 + s_2 = (t_1 +t_4 + s_1 + s_2) - (t_1 +t_4)$ - нечетно, т. е. либо $s_1 = s, s_2 = s + 1$, либо $s_1 = s + 1, s_2 = s$. Первый случай противоречит утверждению леммы для отрезков $A_xD_x \: B_yC_y$, второй - для отрезков $B_xC_x$ и $A_yD_y$.
Второе решение. Предположим, такой прямоугольник $ABCD$ существует. Пусть $AB \geq \sqrt{2}$. Отложим на сторонах $AB$ и $CD$ отрезки $BB^{ \prime} = CC^{ \prime} = \sqrt{2}[АВ/\sqrt{2}]$. Тогда отрезки $BB^{ \prime}$ и $CC^{ \prime}$ пересекают по одной вертикальной и горизонтальной линии, а отрезок $B^{ \prime}C^{ \prime}$ получается из $BC$ переносом на вектор $\vec{BB^{ \prime}}$ с целыми координатами. Поэтому прямоугольник $AB^{ \prime}C^{ \prime}D$ также удовлетворяет условию. Продолжая такие действия, получим в результате прямоугольник, все стороны которого меньше $ \sqrt{2}$ (обозначим его опять $ABCD$). Тогда каждая сторона пересекает не более одной прямой каждого направления, т. е. ровно по одной прямой - либо вертикальной, либо горизонтальной.
Пусть $A$ - самая левая точка прямоугольника, а $B$ - самая нижняя, тогда $C$ - самая правая, а $D$ - самая верхняя. Если отрезки $AB$ и $BC$ пересекают вертикальные прямые, то ломаная $CDA$ их также пересекает, а горизонтальные прямые, соответственно, не пересекает. Тогда проекция $ABCD$ на горизонтальную прямую имеет длину больше 1 (между $A$ и $C$ две вертикальных прямых), а на вертикальную - меньше 1, что невозможно.
Если отрезки $AB$ и $BC$ пересекают (одну и ту же!) горизонтальную прямую, то $ABCD$ лежит в полосе между двумя соседними вертикалями, а тогда $AD$ и $DC$ также пересекают горизонтальную прямую, что невозможно по тем же причинам.
Остался единственный (с точностью до симметрии) случай - $AB$ и $CD$ пересекают одну и ту же вертикальную прямую $v$, а $BC$ и $AD$ - одну и ту же горизонтальную прямую $h$. Тогда $A$ и $В$ лежат под $h$, а $C$ - над $h$, поэтому $BC > AB$. Аналогично, $В$ и $C$ лежат правее $v$, а $D$ - левее $v$, поэтому $BC < CD$. Итого, $AB < BC < CD$, что невозможно.
Ответ. Не может.
