М2010. Зв’язна клітинна фігура

Задача із журналу «Квант» (2006 рік, №4)

Умова

Для натуральних чисел $m$ і $n$ позначимо через $F(m,n)$ кількість всіх зв’язних клітинних фігур прямокутнику $m\times n$. Доведіть, що парність числа $F(m,n)$ збігається з парність числа $\frac{n(n+1)}{2}\cdot\frac{m(m+1)}{2}.$ (Зв’язна клітинна фігура – це така непорожня множина клітин, що з будь-якої клітини цієї множини можна пройти в будь-яку іншу клітину цієї множини по клітинах цієї множини, переходячи щоразу в сусідню по стороні клітину.)

А.Бадзян

Рішення

Припустимо, що $F(m,0) = 0.$ Зв’язні фігури в прямокутнику $m\times 1$ – це $m$ фігур з однієї клітини та смужки із двох або більше клітин. Кожна смужка визначається парою клітин – першою та останньою, тому $$F(m,1) = m + \frac{m(m-1)}{2} = \frac{m(m+1)}{2}.$$

Нехай у прямокутнику $m$ рядків та $n\gt 1$ стовпців. Позначимо через $l$ вертикальну вісь симетрії. Кожній зв’язній фігурі відповідає фігура, симетрична щодо $l,$ тому несиметричні щодо $l$ фігури розбиваються на пари, і парність $F(m,n)$ збігається з парністю кількості зв’язних фігур, симетричних щодо $l.$

Розглянемо деяку фігуру $T,$ симетричну щодо $l.$

Нехай $n$ непарне, $n =2k-1,$ $k\ge 2.$ Фігура $T$ містить хоча б одну клітину $k$-го стовпця, інакше з клітини фігури $T$ неможливо пройти по клітинам $T$ в симетричну відносно $l$ клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина $T_{1}$ фігури $T,$ що розташована в $k$ найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини $x$ та $y$ фігури $T_{1}.$ Нехай $x’$ – клітина, що симетрична $x$ відносно $l,$ a $x’,z_{1},z_{2},\ldots,z_{t},y$ – послідовність клітин, що утворює шлях з $x’$ в $y$ по сусідніх клітинах фігури $T.$ Тоді, замінюючи в цьому шляху клітини, що лежать правіше $k$-го стовпця, на симетричні щодо $l,$ ми отримаємо шлях з $x$ в $y$ по сусідніх клітинах фігури $T_{1}$ (див. малюнок). Навпаки, якщо фігура $T_{1}$ розташована у прямокутнику, що складається з $k$ найлівіших



стовпців, зв’язна і містить хоча б одну клітину $k$-го стовпця, можна однозначно продовжити фігуру $T_{1}$ до зв’язної фігури $T,$ симетричної відносно $l$. Кількість зв’язних фігур у прямокутнику $m\times k$ дорівнює $F(m,k),$ серед них $F(m,k-1)$ фігур лежать у перших $k-1$ стовпцях (тобто не містить клітин $k$-го стовпця). Отже, кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times (2k-1)$ дорівнює $F(m,k)-F(m,k-1).$

Для парного $n = 2k,$ $k\ge 1,$ міркуючи аналогічно, встановимо взаємно однозначну відповідність між зв’язними симетричними щодо $l$ фігурами та зв’язними фігурами, що розташовані в перших $k$ стовпцях і що містять хоча б одну клітинку $k$-го стовпця. Звідси випливає, що кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times 2k$ дорівнює $F(m,k)-F(m,k-1).$

Отже, для $n = 2k-1$ и $n = 2k$ парність $F(m,n)$ збігається з парністю числа $F(m,k)-F(m,k-1).$

Доведемо індукцією по $n,$ що $F(m,n)$ непарно тоді і лише тоді, коли $m$ і $n$ дають залишок $1$ або $2$ при діленні на $4;$ звідси відразу випливає твердження задачі. Твердження вірне при $n = 0$ і $n = 1.$

Нехай $m$ дає залишок $0$ або $3$ при діленні на $4.$ Припустимо, що це твердження вірне для $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто ці числа парні. Якщо $n = 2k-1,$ $k\ge 2,$ або $n = 2k,$ $k\ge 1,$ то $n\gt k,$ тому $F(m,n)$ парне, так як $F(m,k)-F(m,k-1)$ парне. Нехай $m$ дає залишок $1$ або $2$ при діленні на $4.$ Припустимо, що твердження вірно для чисел $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто $F(m,s)$ непарне тоді і лише тоді, коли $s$ дає залишок від ділення $1$ або $2$ при діленні на $4.$ Тоді $F(m,s)-F(m,s-1)$ непарне тоді і лише тоді, коли $s$ непарне. Звідси випливає, що $F(m,n)$ непарне тоді і тільки тоді, коли $n = 2(2l + 1)-1 = 4l + 1$ або $n = 2(2l + 1) = 4l + 2.$

А.Бадзян

М1663. Взаємне розташування діагоналей опуклого чотирикутника

Задача із журналу «Квант» (1998 рік. №6)

Умова

Бісектриси вписаного чотирикутника утворюють у перетині опуклий чотирикутник. Доведіть, що діагоналі отриманого чотирикутника перпендикулярні.

С.Берлов

Розв’язок

Продовжимо протилежні сторони вихідного чотирикутника $ABCD$ до перетину в точках $P$ і $Q$ (див. рисунок). Доведемо спочатку, що бісектриса $PF$ кута $P$ перпендикулярна бісектрисі $QE$ кута $Q.$

Оскільки чотирикутник $ABCD$ — вписаний, зовнішній кут $DCQ$ дорівнює внутрішньому куту в протилежній вершині $A.$ Так як пряма $QE$ — бісектриса кута $Q$, то кути трикутника $AQE$ відповідно дорівнюють кутам трикутника $CQG.$ Отже, $\angle CGQ = \angle AEQ$. Але кути $CGQ$ і $PGE$ рівні як вертикальні. Тому $\angle PEG = \angle PGE$ і $\triangle PEG$ — рівнобедрений.

Отже, бісектриса кута $P$ є серединним перпендикуляром до відрізка $EG,$ тобто бісектриса $PF$ кута $P$ перпендикулярна бісектрисі $QE$ кута $Q.$

Звідси легко випливає твердження задачі, оскільки діагоналі чотирикутника, утвореного на бісектрисах чотирикутника $ABCD,$ лежать на бісектрисах $PF$ і $QE.$

У випадку, коли будь-які дві протилежні сторони чотирикутника $ABCD$ паралельні, твердження задачі випливає із симетричності креслення.

С.Берлов

M613. Подобные треугольники

Задача из журнала «Квант» (1980, №3)

Условие

На сторонах треугольника $ABC$ во внешнюю сторону построены подобные между собой треугольники $ADB,$ $BEC$ и $CFA,$ где
$$\frac{|AD|}{|DB|} = \frac{|BE|}{|EC|}= \frac{|CF|}{|FA|}=k;$$ $$\widehat{ADB}=\widehat{BEC}=\widehat{CFA}=\alpha.$$ Докажите, что:

  1. середины отрезков $AC,$ $DC,$ $BC$ і $EF -$ вершины параллелограмма;
  2. у этого параллелограмма два угла имеют величину $\alpha,$ a отношение длин сторон равняется $k.$
Л. Купцов

Решение

Обозначим через $\vec a^\prime$ вектор, полученный из вектора $\vec a$ поворотом на угол $\alpha$ против часовой стрелки. (Как известно, $(k\vec a)^\prime = k\vec a ^\prime$ для любого числа $k,$ $(\vec a+\vec b)^\prime=\vec a^\prime+\vec b^\prime, $ и вообще, для любого числа слагаемых, $(\vec a+\vec b+\ldots+\vec c)^\prime=\vec a^\prime+\vec b^\prime+\ldots+\vec c^\prime). $

Введем векторы $\overrightarrow{DA} = \vec a,$ $\overrightarrow{EB} = \vec b,$ $\overrightarrow{FC}=\vec c$ (см. рис.1).

рис.1

По условию $\overrightarrow{DB}=\frac 1k \vec a^\prime,$ $\overrightarrow{EC}=\frac 1k \vec b^\prime,$ $\overrightarrow{FA}=\frac 1k \vec c^\prime.$ Так как
$$\overrightarrow{AD}+\overrightarrow{DB}+\overrightarrow{BE}+\overrightarrow{EC}+\overrightarrow{CF}+\overrightarrow{FA}=\vec 0,$$ $$-\vec a+\frac 1k \vec a^\prime-\vec b+\frac 1k \vec b^\prime-\vec c+\frac 1k \vec c^\prime=\vec
0,$$ то есть $\vec a+\vec b+\vec c=\frac{\vec a^\prime+\vec b^\prime+\vec c^\prime}{k}=\frac 1k (\vec a+\vec b+\vec c)^\prime.$
Обозначив $\vec a+\vec b+\vec c$ через $\vec u,$ получим $$\vec u-\frac 1k \vec u^\prime=0. \qquad (\ast)$$ Поскольку векторы $\vec u$ та $\vec u^\prime$ неколинеарные $(\alpha \ne 0$ и $\alpha \ne 2\pi),$ равенство $(\ast)$ возможно тогда и только тогда, когда $\vec u=\vec 0.$ Поэтому $\vec a+\vec b+\vec c=\vec 0.$

Далее: поскольку $Q \: -$ середина $[DC]$ и $P \: -$ середина $[AC]$ (см. рис.1), $\overrightarrow{QP}=\frac 12 \vec a.$ Аналогично $\overrightarrow{QR}=\frac 12 \overrightarrow{DB}.$ Так как $(PQ)\|(AD)$ и $(QR) \| (BD),$ имеем $\widehat{PQR}=\alpha.$

Наконец, $$\overrightarrow{RS}=\overrightarrow{RC}+\overrightarrow{CF}+\overrightarrow{FS}=\frac 12 \overrightarrow{BC}-\vec c+\frac 12 \overrightarrow{FE}=$$ $$=\frac 12(-\vec b+\frac 1k \vec b^\prime)-\vec c+\frac 12 (\vec c-\frac 1k \vec b^\prime)=-\frac{\vec b+\vec c}{2}=\frac{\vec a}{2}=\overrightarrow{QP}.$$

Таким образом, четырехугольник $PQRS \: -$ параллелограмм с углом $PQR,$ равным $\alpha,$ в котором отношение длин сторон имеет вид $\frac{|PQ|}{|RQ|}=\frac{|AD|}{|DB|}=k.$

Л. Купцов

Евклидово пространство

Определение 1. Пусть дано вещественное линейное пространство $E$. Оно называется евклидовым, если на нем задано отображение из каждой пары векторов в соответствующее ей вещественное число. Назовем это отображение скалярным произведением. Отображение должно удолетворять следующим аксиомам:

  1. $\left(x, y \right) = \left(y, x \right),$
  2. $\left(\lambda x, y \right) = \lambda \left(x, y \right),$
  3. $\left(x + y, z \right) = \left(x, z\right) + \left(y, z\right),$
  4. $\left(x, x \right) > 0 \quad при \quad x \not= 0; (x, x) = 0 \quad при \quad x = 0; \forall x, y, z \in E, \forall \lambda \in R.$

Отсюда можно получить ряд следствий:

  1. $\left(x, \lambda y\right) = \lambda \left(x, y \right)$,
  2. $\left(x, y + z \right) = \left(x, y \right) + \left(x, z \right)$,
  3. $\left(x {-} z, y \right) = \left(x, y \right){-}\left(z, y \right)$,
  4. $\left(x, y {-} z \right) = \left(x, y \right){-}\left(x, z \right)$,
  5. $\forall a = \sum\limits_{j = 1}^m \alpha_j x_j$, $b = \sum\limits_{i = 1}^n \beta_i y_i: \\ \left(x, y\right) = \left(\sum\limits_{j = 1}^m \alpha_j x_j, b = \sum\limits_{i = 1}^n \beta_i y_i\right) = \sum\limits_{j = 1}^m \sum\limits_{i = 1}^n \alpha_j \beta_i \left(x_j, y_i \right)$

Любое n-мерное линейное пространство можно превратить в евклидово(с помощью определения в нем скалярного произведения). В n-мерном линейном пространстве скалярное произведение можно задать различными способами.

Например, возьмем в произвольном вещественном пространстве $G$ его некоторый базис $g = {e_1, e_2, \cdots, e_n}$ и два любых вектора $x$, $y$. Допустим, $$x = \sum\limits_{i = 1}^n \alpha_i e_i \quad y = \sum\limits_{i = 1}^n \beta_i e_i$$

Теперь можно ввести скалярное произведение: $\left(x, y\right) = \sum\limits_{i = 1}^n \alpha_i \beta_i.$

Любое подпространство из $E$ может быть Евклидовым, если в нем сохраняется скалярное произведение, определенное в $E$.

Определение 2. Пусть дан вектор $x$, принадлежащий евклидову пространству. Если $(x, x) = 1$, то этот вектор называется нормированным. Ненулевой вектор можно нормировать, если умножить его на произвольное число $\lambda$: $$\left(\lambda x, \lambda x \right) = \lambda^2 \left(x, x\right) = 1.$$

Значит, нормирующий множитель $\left(\lambda \right) = \left( x, x \right)^{{-}\frac{1}2}$

Определение 3. Пусть вектор $x$ принадлежит евклидову пространству $E$. Длиной вектора $x$ назовем число $\mid x \mid = + \sqrt{\left(x, x\right)}$, где $x \in R.$ Данное определение имеет свойства длины:

  1. $\mid 0 \mid = 0.$
  2. $\mid x \mid > 0, если x \not= 0.$
  3. $\mid \lambda \cdot x \mid = {\mid \lambda \mid}{\mid x \mid}$ — свойство абсолютной однородности.

Определение 4. Пусть даны векторы $x, y$, принадлежащие евклидову пространствую. Тогда $ \displaystyle \cos \left(x, y \right) = \frac{ \left(x, x \right)}{{ \mid x \mid}{ \cdot}{ \mid y \mid}}, 0 \leqslant \left(x, y \right) \leqslant \pi$ — косинус угла между этими векторами

Рассмотрим применимость школьной геометрии к геометрии евклидова пространства. Пусть заданы два вектора $x, y \in E; x \not= 0, y \not= 0$ — две стороны треугольника. Тогда разность $y-x$ — третья сторона. С помощью формулы для угла можно вычислить квадрат третьей стороны: $${\mid y-x\mid}^2 = \left(y-x, y-x \right) = {\mid y \mid}^2+{\mid x \mid}^2 {-} 2 \left(y, x\right) = {\mid y \mid}^2+{\mid x \mid}^2 {-} \mid y \mid \mid x \mid \cos \left(b, a\right)$$

Получили теорему косинусов. Разумеется, если $y \bot x$, то треугольник является прямоугольным. Также, из последней формулы можно получить теорему Пифагора: ${\mid y-x\mid}^2 = {\mid y \mid}^2+{\mid x \mid}^2.$ Из той же формулы получаем отношение длин сторон треугольника, если оценивать множитель $cos(b^a)$ сверху: $${\mid y-x\mid}^2 \leqslant {\mid y \mid}^2+{\mid x \mid}^2 {+} 2{\mid y \mid}{\mid x \mid} = \left({\mid y \mid}+{\mid x \mid}\right)^2 \Rightarrow \mid y-x \mid \leqslant {\mid y \mid}+{\mid x \mid}.$$

И снизу: $${\mid y-x\mid}^2 \leqslant {\mid y \mid}^2+{\mid x \mid}^2 {-} 2{\mid y \mid}{\mid x \mid} = \left({\mid y \mid}-{\mid x \mid}\right)^2 \Rightarrow \mid y-x \mid \leqslant {\mid y \mid}-{\mid x \mid}.$$

Литература

  1. Электронный конспект по линейной алгебре Белозерова Г.С.
  2. Воеводин В.В. Линейная алгебра.Стр. 88-90
  3. Курош А.Г. Курс высшей алгебры.Стр. 211-212

М827. О равновеликих треугольниках

 

Задача из журнала «Квант» (1984 год, 1 выпуск)

Условие

Известно, что четыре синих треугольника на рисунке 1 равновелики.

  1. Докажите, что три красных четырехугольника на этом рисунке также равновелики.
  2. Найдите площадь одного четырехугольника, если площадь одного синего треугольника равна 1.

Решение

Нам понадобится следующая часто применяемая

Лемма. Пусть $Р$ — точка на стороне $KL$ треугольника $KLM$. Тогда отношение площадей треугольников и равно $$S_{MKP}:S_{MPL}=|KP|:|PL|.$$ (Для доказательства достаточно заметить, что треугольники $MKP$ и $MPL$ имеют общую высоту проведенную из вершины $М$ (рис. 2).).

Рис. 1
Рис. 2
Рис. 3
  1. Введем обозначения, как  на рисунке 1. Заметим, что треугольники $AA_0C_0$ и $AA_0C_1$ равновелики (каждый из них составлен из треугольника $AA_0B_0$ и одного из из синих треугольников). Эти треугольники имеют общее основание $AA_0$, поэтому их вершины $C_0$ и $C_1$ равноудалены от прямой $AA_0$, то есть прямые $AA_0$ и $C_1C_0$ параллельны. Аналогично, $BB_0||A_1A_0$ и $CC_0||B_1B_0$. Рассмотрим трапецию $AA_0C_0C_1$ (рис. 3). Её диагонали пересекаются в точке $B_0$, а продолжения боковых сторон — в точке $B$. Эти точки лежат на прямой, соединяющей середины $D$ и $E$ её оснований $AA_0$ и $C_1C_0$. (Действительно, $B_0$ — центр гомотетии треугольников $B_0AA_0$ и $B_0C_0C_1$, а $B_0$ — центр гомотетии треугольников $BAA_0$ и $BC_1C_0$). А поскольку эта прямая параллельна $A_1A_0$, точка $B_0$ — середина отрезка $A_1A$. По лемме отсюда вытекает,что $S_{AB_0C}=S_{B_0A_1C}$. Следовательно (см. рис. 1), площади четырехугольников $AB_0A_0B_1$ и $CA_0C_0A_1$ равны. Аналогично доказывается, что и третий красный четырехугольник $BC_0B_0C_1$ имеет такую же площадь.

    Подумайте, останется ли верным утверждение этого пункта задачи, если потребовать равенства площадей только трех угловых синих треугольников.

  2. Площадь красного четырехугольника $s=1+\sqrt{5}$. Чтобы составить уравнение для нахождения искомой площади $s$, выразим двумя способами отношение $|BC_1|:|C_1A|$ с помощью леммы:$$|BC_1|:|C_1A|=S_{CBC_1}:S_{CC_1A}=(2s+2):(s+2)=S_{B_0BC_1}:S_{B_0C_1A}=(s/2):1.$$
    (Пояснения здесь требуют только равенство $S_{B_0BC_1}$. Как было показано выше, точка $E$ — середина $C_0C_1$ (рис. 3). Отсюда, опять-таки пользуясь леммой, легко вывести, что треугольники $B_0BC_1$ и $B_0BC_0$ равновелики. А вместе они составляют четырехугольник $BC_0B_0C_1$ площади $s$). Итак, $s$ удовлетворяет уравнению $$s^2-2s-4=0.$$ откуда $s=1+\sqrt{5}$.
  3. Б. И. Чиник, В. Н. Дубровский