М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},\cdots,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),\cdots,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),\cdots,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.$

А.Бадзян

M1401. Перетин прямої, яка з’єднує дві бісектриси різних вписаних трикутників, і центра вписаного кола

Задача М1401 з журналу «Квант» (1993 рік, № 11/12)

Умова

На дузі $BC$ кола, описаного навколо трикутника $ABC$ (що не містить $A$), взято точку $K$. Нехай $NK$ і $MK$ — бісектриси трикутника $AKB$ і $AKC$. Доведіть, що пряма $MN$ проходить через центр вписаного кола трикутника $ABC$.

В. Акопян

Розв’язок

Випишемо умову, за якої пряма $MN$ (де $M$ і $N$ — точки на сторонах кута $A$) перетинає бісектрису у заданій точці $Q$ (мал. 1). Покладемо $AM = x$, $AN = y$, $AQ = q$, $\angle MAN = 2\alpha$. Сума площ трикутників $AMQ$ і $ANQ$ дорівнює площі трикутника $MAN$; звідси $xq + yq = 2xy \cos \alpha$, або $1/x + 1/y = 2\cos\alpha / q$. (Це — формула для обчислення бісектриси $q$ по двум сторонам $x$, $y$ і куту $2\alpha$ між ними.) Таким чином, щоб довести, що в нашій задачі прямі $MN$ перетинають бісектрису в одній і тій самій точці, достатньо перевірити, що величина $1/AM + 1/AN$ постійна. Один з способів довести це — використання теореми синусів. Нехай $d$ — діаметр кола, $\angle ABC = 2\beta$, $\angle ACB = 2\gamma$, $\angle ABK = \varphi$. Тоді $AK = d \sin\varphi$,
$$AM = d \sin \varphi \cdot \frac{\sin \gamma}{\sin(\varphi + \gamma)},$$
$$AN = d \sin \varphi \cdot \frac{\sin \beta}{\sin(\pi — \varphi + \beta)} = d \sin \varphi \cdot \frac{\sin\beta}{\sin(\varphi — \beta)},$$
тому величина
$$\frac{1}{AM} + \frac{1}{AN} = \frac{1}{d} \left(\frac{\sin(\varphi + \gamma)}{\sin\varphi\sin\gamma} + \frac{\sin(\varphi-\beta)}{\sin\varphi\sin\beta} \right) = \frac{1}{d}\left(\cot\gamma+\cot\varphi+\cot\beta — \cot\varphi \right) = \frac{1}{d} \left(\cot\gamma + \cot\beta \right)$$
дійсно не залежить від $\varphi$.

Мал. 1

Ще один спосіб, замість тригонометрії, використовує теорему Птолемея. За властивісттю бісектриси маємо:
$$\frac{AB — x}{x} = \frac{BK}{AK},$$
або
$$\frac{AB}{x} = 1 + \frac{BK}{AK}. \;\;\;(1)$$
Аналогічно
$$\frac{AC}{y} = 1 + \frac{CK}{AK}.\;\;\;(2)$$
За теоремою Птолемея $BK \cdot AC + CK \cdot AB = AK \cdot BC$. Отже,
$$\frac{BK}{AK}\cdot AC + \frac{CK}{AK} \cdot AB = BC.$$
З допомогою цієї рівності отримаємо з (1) і (2) твердження, що доводиться, про те, що $1/x + 1/y$ постійна.

Залишається пояснити, що фіксована точка $Q$, через яку проходять усі прямі $MN$, дійсно центр вписаного кола.

Це можна зробити, наприклад, розглянувши одне спеціальне положення точки $K$, коли вона знаходиться в середині дуги $BC$; тоді
$$BM/MA = BK/KA = CK/KA = CN/NA \;\;\;(3)$$
(так що $MN$ паралельна $BC$). Нехай $P$ — точка перетину $AK$ зі стороною $BC$. З подоби трикутників $BKA$ і $PKB$ (вони мають спільний кут $K$ і рівні кути, які опираються на рівні дуги $KC$ і $KB$) відношення (3) дорівнює:
$$BK/KA = BP/AB = PQ/QA,$$
де $Q$ — центр вписаного кола трикутника.

Але це можна обчислити і без допомоги обчислень. Помітимо, що коли точка $K$ наближається до $B$, то $M$ також наближається до $B$, так що граничним положенням прямої $MN$ буде бісектриса кута $B$ (так само, коли $K$ наближається до $C$, граничним положенням $MN$ буде бісектриса кута $C$). Ці «граничні» прямі, звичайно, теж проходять через точку $Q$; тим самим $Q$ — точка перетину бісектрис трикутника $ABC$.

Мал. 2

Інший роз’язок задачі М1401 можна отримати, спираючись на наступну чудову теорему Паскаля: точки перетину трьох пар протилежних сторін вписаного шестикутника лежать на одній пряій1. Щоб отримати цей шестикутник $ABDKEC$, достатньо продовжити бісектриси до перетину з колом у точках $D$ і $E$ (вони ділять відповідні дуги навпіл — див. мал. 2); тоді $M,$ $N,$ $Q$ — точки перетину його сторін $AB$ і $EK$, $DK$ і $CA$, $BD$ і $EC$.

В. Акопян, Н. Васильєв, В. Дубровський, В. Сендеров

1Див. статтю Н. Васильєва «Гексаграми Паскаля і кубічні криві» в «Кванті» №8 від 1987 р.

М1314. Про діагоналі випуклого чотирикутника та центри вписаних кіл трикутників

Задача М1314 з журналу «Квант» 1991 року №11

Умова

\(ABCD\) — випуклий чотирикутник, діагоналі котрого перетинаються в точці \(O\). Нехай \(P\) та \(Q\) — центри кіл, описаних навколо трикутників \(ABO\) і \(CDO\).

Доведіть, що \(AB+CD\leq4PQ\)

Ф. Назаров

Розв’язання

Нехай \(O\) — точка перетину діагоналей чоторикутника \(ABCD\). Проведемо пряму, що ділить кути \(BOA\) та \(COD\) навпіл і, що перетинає кола, описані навколо трикутників \(AOB\) і \(COD\) у точках \(K\) і \(L\) відповідно. (малюнок)

Нехай \(PM\) та \(QN\) — перпендикуляри, опущені із точок \(P\) і \(Q\) на пряму \(KL\).

Так як сума кутів \(\angle KBO\) і \(\angle KAO\) = \(180^{\circ}\), один з цих двох кутів не є гострим. Будемо для визначенності вважати, що таким кутом є \(KBO\).

З трикутника \(KBO\) отримаємо, що \(КО > KB\). А так як трикутник \(AKB\) — рівнобедрений, $$2KB = KB + KA > AB.$$

Отже, \(2KO > AB\). Аналогічно доводиться, що \(2LO > CD\).

Але тоді $$4PQ \geq 4MN = 2KL = 2KO + 2LO > AB + CD.$$

Ф. Назаров

M1206. Про рівність квадрату радіуса кола і площі чотирикутника

$\DeclareMathOperator{\tg}{tg}$

Задача M1206 із журналу «Квант» (1990 г. №2)

Умова

У колі проведено два перпендикулярні один одному діаметри $AE$ і $BF.$ На дузі $EF$ узято точку $C.$ Хорди $CA$ і $CB$ перетинають діаметри $BF$ і $AE$ відповідно в точках $P$ і $Q$ (малюнок 1). Доведіть що площа чотирикутника APQB дорівнює квадрату радіуса кола.

(А. Костенков)

Розв’язання

Один з найпростіших розв’язків отримуємо прямим обчисленням за формулою $S_{APQB} = PQ \cdot BP / 2.$ Якщо $\angle CAE = a,$ то $AQ = AO + OQ = (1 + \tg\beta),$ де $O$ — центр, а $R$ — радіус даного кола, $$S_{APQB} = \frac{1}{2} R^2(1 + \tg\alpha + \tg\beta + \tg\alpha \tg\beta).$$ Тепер треба довести, що величина в дужках дорівнює 2, тобто що $(\tg\alpha + \tg\beta)/(1 — \tg\alpha \tg\beta) = 1.$ У лівій частині цієї рівності стоїть вираз для $\tg(\alpha + \beta).$ Залишається зауважити, що $\alpha + \beta = \angle CAE + \angle CBF = 45^\circ$ (кути $CBF$ і $CAE$ спираються на дуги $CF$ і $CE,$ які в сумі складають $90^\circ),$ а $\tg45^\circ = 1.$


Малюнок 1

Намітимо і «чисто геометричний» розв’язок. Нехай $D$ — точка перетину хорд $AC$ і $EF$ (малюнок 2). Тоді, очевидно, $S_{ABD} = S_{ABEF}/2 = R^2,$ і ми повинні сказати, що $S_{ABD}=S_{ABPQ},$ тобто що $S_{BDF}=S_{BQP}.$ Точки $Q,$ $E,$ $C$ і $D$ лежать на одному колі $(\angle QED = 45^\circ = \angle QCD);$ тому $\angle DQE = 180^\circ — \angle DCE = 90^\circ.$ Отже, прямі $DQ$ і $BP$ паралельні, а отже, трикутники $BDP$ і $BQP$ рівновеликі.


Малюнок 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$ паралельні, твердження задачі випливає із симетричності креслення.

С.Берлов