М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 р.

M1268. Про доведення площі трикутника

Задача M1268 із журналу «Квант» (1991 р. №1)

Умова

Всередині трикутника $ABC$ взято довільну точку $X$. Прямі $AX,$ $BX,$ $CX$ перетинають сторони $BC,$ $CA$ і $AB$ в точках $A_1,$ $B_1,$ $C_1.$ Нехай $AB_1 \cdot AC_1 \cdot BC_1 \cdot BA_1 \cdot CA_1 \cdot CB_1 = \Pi.$ Доведіть, що площа $S$ трикутника $A_1B_1C_1$ дорівнює $S=\frac{\sqrt{\Pi}}{2R}$, де $R$ — радіус описаного навколо трикутника $ABC$ кола.

Розв’язання

Нехай точки $C_1$ $A_1$ і $B_1$ ділять сторони $c= AB,$ $a= BC$ і $b= CA$ відповідно на відрізки $p$ і $u,$ $q$ і $v,$ $r$ і $w$ (мал. 1). Оскільки площа трикунтика з даним кутом пропорційна добутку сторін, що утворюють цей кут, площа $S$ блакитного трикутника дорівнює площі всього трикутника $S_{ABC},$ помноженого на коефіцієнт $$1-\frac{qu}{ca} — \frac{rv}{bc} — \frac{pw}{ab} = \frac{abc-bqu-arv-cpw}{abc}.$$

Підставивши замість $a, b, c$ суми $p+u, q+v, r+w$ і згадавши відому формулу $S_{ABC} = abc/4R,$ ми отримаємо гарну формулу площі блакитного трикутника $$S=\frac{pqr+uvw}{4R},$$ але вона відрізняється від тієї, яку потрібно було довести. Тепер скористаємось теомерою Чева, згідко з якою при будь-якому виборі точки $X$ всередині трикутника $ABC$ виконується рівність $$pqr=uvw. (*)$$

Із рівності $(*)$ і $П=pqruvw$ слідує, що $$П=(pqr+uvw)^2 /4,$$ а значить, що і потрібна формула для $S.$

Для доведення формули $(*)$ можна також використати площі. Відношення площ трикутників $AXB$ і $CXB$ зі спільною основою $XB$ дорівнює відношенню їх висот, тобто $w/r$ (мал. 2). Перемножуючи три таких відношення, отримаємо $$\frac{p}{u}\cdot\frac{q}{v}\cdot\frac{r}{w}=\frac{S_{AXC}}{S_{CXA}}\cdot\frac{S_{CXA}}{S_{AXB}}\cdot\frac{S_{AXB}}{S_{BXC}}=1.$$

Н.Васильєв, Н.Просолов


М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

(В. Дубровський)