Processing math: 100%

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

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

Умова

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

А.Бадзян

Рішення

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

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

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

Нехай n непарне, n=2k1, k2. Фігура T містить хоча б одну клітину k-го стовпця, інакше з клітини фігури T неможливо пройти по клітинам T в симетричну відносно l клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина T1 фігури T, що розташована в k найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини x та y фігури T1. Нехай x – клітина, що симетрична x відносно l, a x,z1,z2,,zt,y – послідовність клітин, що утворює шлях з x в y по сусідніх клітинах фігури T. Тоді, замінюючи в цьому шляху клітини, що лежать правіше k-го стовпця, на симетричні щодо l, ми отримаємо шлях з x в y по сусідніх клітинах фігури T1 (див. малюнок). Навпаки, якщо фігура T1 розташована у прямокутнику, що складається з k найлівіших



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

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

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

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

Нехай m дає залишок 0 або 3 при діленні на 4. Припустимо, що це твердження вірне для F(m,0),F(m,1),,F(m,n1), тобто ці числа парні. Якщо n=2k1, k2, або n=2k, k1, то n>k, тому F(m,n) парне, так як F(m,k)F(m,k1) парне. Нехай m дає залишок 1 або 2 при діленні на 4. Припустимо, що твердження вірно для чисел F(m,0),F(m,1),,F(m,n1), тобто F(m,s) непарне тоді і лише тоді, коли s дає залишок від ділення 1 або 2 при діленні на 4. Тоді F(m,s)F(m,s1) непарне тоді і лише тоді, коли 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. Отже, CGQ=AEQ. Але кути CGQ і PGE рівні як вертикальні. Тому PEG=PGE і PEG — рівнобедрений.

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

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

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

С.Берлов

Ф676. Движение рамки в магнитном поле

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

Условие

Рис.1

Проволочной квадратной рамке с периметром 4a и массой m сообщают в горизонтальном направлении некоторую начальную скорость. Рамка движется в вертикальной плоскости, все время находясь в магнитном поле, перпендикулярном плоскости рамки (см. рис.1). Индукция поля меняется по закону B(z)=B(0)+kz, где k=const. Сопротивление рамки равно R. Через некоторое время скорость рамки становится постоянной и равной v. Найти начальную скорость, сообщаемую рамке. Ускорение свободного падения g.

Решение

Рис.2

В отсутствие магнитного поля рамка двигалась бы в поле тяжести Земли с постоянной горизонтальной скоростью v0 вдоль оси X и равноускоренно с ускорением свободного падения g вдоль оси z. Очевидно, что движение рамки не изменилось бы, если бы она падала в однородном магнитном поле. В нашем случае поле — не однородное (вдоль оси z): B(z)=B(0)+kz, то есть индукция поля линейно растет с ростом z; поэтому при падении рамки поток магнитной индукции Φ, пронизывающий контур рамки, будет меняться и в контуре рамки будет возникать ЭДС индукции. Поскольку рамка является замкнутым проводящим контуром, по ней потечет индукционный ток. В этом случае, согласно закону Ампера, на стороны рамки будут действовать силы со стороны магнитного поля. Найдем направления и величины этих сил.

Пусть в некоторый момент времени центр масс рамки находится в точке с координатами xt,zt и проекции скорости центра масс на оси X и z равны vx и vz (см. рис.2). Поток магнитной индукции Φ, пронизывающий рамку в этот момент времени, равен Φ=(B0+k(zta2))+(B0+k(zt+a2))2a2=(B0+kz1)a2. Здесь B0+k(zta2) и B0+k(zt+a2)— значения индукции магнитного поля соответственно у верхней и нижней сторон рамки; поскольку зависимость Bz—  линейная, для вычисления Φ мы пользуемся средним ( по высоте z) значением индукции.

ЭДС индукции в рамке в данный момент времени равна |E|=|ΔΦ|Δt=ka2|Δz|Δt=ka2|v2|. индукционный ток равен I=|E|R=ka2R|vz|. Согласно правилу Ленца, возникающий в рамке ток будет течь против часовой стрелки. По закону Ампера со стороны магнитного поля в верхнюю сторону рамки будет действовать сила |F1|=(B0+k(zta2))Ia=(B0+k(zta2))ka3R|vz|. на нижнюю сторону — сила |F2|=(B0+k(zt+a2))Ia=(B0+k(zt+a2))ka3R|vz|.Силы F3 и F4, действующие на боковые стороны рамки, очевидно, будут равны по величине и противоположны по знаку: |F3|=|F4|=(B0+k(zta2))+(B0+k(zt+a2))2Ia= =(B0+kzt)ka3R|vz|. F3+F4=0.Следовательно, vx=const, то есть рамка будет двигаться вдоль оси X с постоянной скоростью, равной начальной скорости v0.

Таким образом, характер движения рамки в направлении оси z определяется силами F1,F2 и силой тяжести mgg. При установившейся скорости v рамки проекция скорости на ось z постоянна, то есть ускорение az вдоль оси z равно нулю: m|az|=m|g|+|F1||F2|=mgk2a4R|vz|=0. Отсюда находим проекцию vуст.z на ось z установившейся скорости рамки: vуст.z=mgRk2a4. Установившаяся скорость рамки равна v=v20+v2устz., где v0 — проекция скорости v на ось X, равная, как мы показали, начальной скорости,  сообщенной рамке. Таким образом, v0=v2v2уст.z=v2(mgRk2a4)2.

Скорость vуст.z может быть найдена и из энергетических соображений. При установившемся движении рамки изменение за время Δt потенциальной энергии рамки в поле тяжести Земли равно тепловой энергии, выделяющейся за это время в рамке: mgvуст.zΔt=I2уст.RΔt=(ka2R)2v2уст.zRΔt. Отсюда vуст.z=mgRk2a4.

В. Можаев

М13. Разность и сумма модулей

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

Условие

Докажите, что если разность между наибольшим и наименьшим из n вещественных чисел a1,a2,,an равна d, а сумма модулей всех n(n1)2 попарных разностей этих чисел i<j|aiaj| равна s, то (n1) dsn24d.

Решение

рисунок
Нанесем точки a1,a2,,an на числовую ось. Тогда d — расстояние между крайними из этих точек, самой левой и самой правой, а i<j|aiaj| — сумма всех попарных расстояний между этими точками. Можно, очевидно, считать, что точки обозначены через a1,a2,,an в порядке возрастания: a1a2an (рисунок). Обозначим расстояние между соседними точками ak и ak+1 через dk(k=1,2,,n1). Очевидно, d=d1+d2+dn1. Выразим теперь s через величины dk. Для этого заменим в сумме s длину каждого отрезка |aiaj| суммой тех dk, из которых он состоит: |aiaj|=di+di+1++dj1. Ясно, что dk входит в те отрезки, у которых левый конец лежит в одной из точек a1,,ak, а правый — в одной из точек ak+1,an, то есть в общей сложности dk входит в сумму k(nk) раз. Поэтому s=n1k=1k(nk)dk. Теперь доказываемое утверждение следует из двух совсем простых неравенств: для всех k=1,,n1

  1. k(nk)n1knk2n+10(k1)(nk1)0
  2. k(nk)n24n24nk+4k20(n2k)2

Пользуясь этими оценками n1k=1k(nk)dkn1k=1(n1)dk=(n1)d, n1k=1k(nk)dkn1k=1n24dk=n24d.

Интересно выяснить

Являются ли указанные в условии задачи оценки точными, нельзя ли, скажем, вместо n1 поставить в левом неравенстве большее число? Для того, чтобы убедиться в противном, достаточно привести пример такого случая, когда неравенство превращается в равенство (причем в обеих его частях стоят положительные числа). Такой пример легко придумать, разобравшись в нашем доказательстве: нужно расположить точки a1,a2,,an так, чтобы все dk, кроме первого — d1, равнялись нулю, то есть взять a1<a2=a3==an. Тогда s=(n1)d1=(n1)d.

Что касается второго неравенства sn24d, то при четном n=2m в нем тоже может достигаться равенство (достаточно взять a1=a2==am<am+1==a2m), а при нечетном n=2m+1 его можно несколько уточнить: нетрудно сообразить, что при нечетном n наибольшее из чисел k(nk) равно n12×n+12=n214; пользуясь этим вместо неравенства б), можно так же, как и выше, доказать более сильное неравенство s<n214d. Равенство в нем достигается, когда a1==am<am+1==a2m+1.

М1864. О сумме квадратов длин попарно параллельных отрезков

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

Условие

В квадрат ABCD вписана ломаная MKALN такая, что MKA=KAL=ALN=45(рис.1). Докажите, что MK2+AL2=AK2+NL2.

рис. 1

Симметрично отобразим ABK относительно гипотенузы AK, а ADL относительно гипотенузы AL (рис.2). При этом точки B и D склеятся в точку P, так как AB = AD, B=D=90 и AP является высотой AKL.

рис. 2
Более того, при этом точки M и N склеятся в точку Q, где Q ортоцентр AKL. Это произойдет потому, что QLA=QKA=KAL=45, из чего следует, что прямые QL и QK высоты AKL, а три высоты пересекаются в одной точке.

Сразу делаем вывод: BM=DN.

Используя теорему Пифагора сначала для ABK и MBK, а затем для ADL и NDL получаем AB2BM2=AK2MK2 и AD2DN2=AL2NL2.

Окончательно получим MK2+AL2=AK2+NL2, что и требовалось доказать.

Дополнительно можно доказать, что AM=AN=KL и что пять точек M, K, A, L и N принадлежат одной окружности.

В. Произволов

Некоторые дополнения

1.При симметричном отображении ABK относительно гипотенузы AK мы получаем APK, в котором AB=AP, BK=KP, MK=KQ, BM=QP, MKA=AKQ=45, BKM=PKQ.

Аналогично, при симметричном отображении ADL относительно гипотенузы AL мы получаем APL, в котором AD=AP, LD=LP, NL=QL, ND=QP, ALN=ALQ=45, NLD=QLK.

Таким образом, так как BM=QP,ND=QP, тогда, по транзитивности, ND=BM.

2. Докажем, что Q — ортоцентр AKL. Для этого воспользуемся рис.3.

рис.3

APKL. Проведем через точки K и Q прямую до пересечения с прямой AL, KQAL=K1. Также проведем прямую, проходящую через точки L и Q и пересекающую прямую AK, QLAK=L1. Так как AP — высота AKL. Осталось показать, что KK1 и LL1 — высоты AKL.

Рассмотрим AKK1, в нём KAK1=AKK1=45, тогда AK1K=1804545=90 KK1AL, то есть KK1 — высота AKL. Аналогично, ALL1: KAK1=AKK1=45 LL1AK, то есть LL1 — высота AKL.

Таким образом, три высоты AKL пересекаются в одной точке Q, что и означает, что Q — ортоцентр AKL.

3. Распишем более подробно как мы получили равенство.

ABK: AB2+BK2=AK2BK2=AK2AB2 BMK: BM2=MK2BK2BM2=MK2AK2+AB2 AB2BM2=AK2MK2 ALD: AL2=AD2+LD2LD2=AL2AD2 NDL: ND2=NL2LD2ND2=NL2AL2+AD2 AD2ND2=AL2NL2 MK2+AL2=AK2+BM2AB2+AD2ND2+NL2=AK2+NL2,(так как AD=AB,ND=BM).

4. Докажем, что точки M, K, A, L и N принадлежат одной окружности.

Так как около любого треугольника можно описать окружность, то точки K, A и L уже принадлежат окружности ω1, описанной около AKL. Покажем, что точки M L также принадлежат этой окружности.

Рассмотрим BMK и обозначим в нем BKM=α, тогда BMK=90α. AMK: AMK=180(90α)=90+α MAK=180(45+90+α)=45α ADL: DAL=90(45α+45)=α NLD: LND=45+α NLD=90(45+α)=45α.

Из первого пункта следует, что NLD=QLK=45α,BKM=QKP=α.Значит, ALK=45+45α=90α,MKL=45+45+α=90+α.Тогда, AMK+ALK=90+α+90α=180 MKL+MAL=90+α+90α=180

Таким образом, в четырехугольнике AMKL сумма противолежащих углов равна 180, значит четырехугольник AMKL можно вписать в окружность ω2. Так как, окружность ω2 описана около AMKL, тогда она описана около AKL, но так как около треугольника можно описать только одну окружность, то ω1=ω2 и точки M, K, A, L и N принадлежат одной окружности.

5. Докажем, что AM=AN=KL.

Из первого пункта: BM=ND, а так как AB=AD, то AM=ANОсталось показать, что AM=KL.Так как MKA=KAL=45, то MKAL, тогда, так как MAL=KLA=90α, AMKL — равнобокая трапеция AM=KL, тогда AM=AN=KL.