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.

А.Бадзян

М697. Пузатость прямоугольника

Задача

разделение квадрата на прямоугольники

Назовем пузатостью прямоугольника отношение его меньшей стороны к большей (пузатость квадрата равна 1). Докажите ,что, как бы не резать квадрат на прямоугольники, сумма их пузатостей будет не меньше 1.

Доказательство

Будем считать что длина стороны квадрата равна 1. Тогда пусть мы разбили квадрат на n прямоугольников размерами ak×bk причем при всех k akbk

Одно из возможных разбиений квадрата на прямоугольники

тогда:

1bk1bkbkakbkak×bknk=1akbknk=1ak×bk=1 (сумма nk=1ak×bk является суммой площадей прямоугольников и по свойству площади равна площади квадрата (то есть 1)).

А это значит что:

nk=1akbk1 . А это и значит, что как бы не резать квадрат на прямоугольники, сумма их пузатостей будет не меньше 1.

Что и требовалось доказать.

М658. О разбиении квадрата отрезками

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

Условие

В квадрате со сторо­ной 1 проведено конечное чис­ло отрезков (рис. 1), парал­лельных его сторонам. Отрез­ки могут пересекать друг друга. Сумма длин проведен­ных отрезков равна 18. Дока­жите. что среди частей, на которые квадрат разбивается этими отрезками, найдется такая, площадь которой не меньше 0.01

Решение

Сумма длин границ всех частей, на которые квадрат разбит отрезками, равна 218+4=40 (длины проведенных отрезков входят в эту сумму по два раза, длины сторон квадрата — по одному). Пусть для i-й части сумма длин горизонтальных границ равна xi, вертикальных — 2yi, а площадь i-й части равна c2i (ci>0) : тогда xiyic2i (рис. 2), поэтому xi+yi2xiyi2ci. Итак, 40=(2xi+2yi)4ci, откуда ci10 (здесь сумма берется но всем частям разбиении).

Если c2i<0.01 (то есть ci<0.1) для всех i, то 1=c2i<0.1ci=0.1ci , откуда ci10. Противоречие. Очевидно, оценка 18 — точная: восемнадцатью отрезками длины 1 наш квадрат можно разбить на 100 одинаковых квадратиков площади 0.01 каждый.

А.Анджан

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

Условие

Квадрат клетчатой бумаги, состоящий из n×n клеток, разрезан на 2n прямоугольников. При этом каждый прямоугольник расположен либо целиком ниже, либо выше ступенчатой ломаной, разделяющей квадрат (рис.1). Докажите, что найдется клетка клетчатой бумаги, являющаяся одним из названных прямоугольников.

Рис. 1

Решение

Ступенчатая ломанная разрезает квадрат на два ступенчатых треугольника T1 и T2, при этом основание T1 состоит из n клеток, а основание T2 – из n1 клетки. В силу условия задачи, один из них разрезан на m, а другой – на k прямоугольников, причем m+k=2n. Пока что фиксируем внимание на отдельно взятом ступенчатом треугольнике T, в основании которого s клеток (рис.2). Так как при разрезании T на прямоугольники любые две точки из набора A1,A2,,As должны принадлежать разным прямоугольникам, можно заключить, что T нельзя разрезать на менее чем s прямоугольников.

Рис. 2

Разберем далее тот случай, когда T разрезан в точности на s прямоугольников; тогда каждая из точек A1,A2,,As принадлежит только одному из них и, более того, каждая из s закрашенных клеток принадлежит целиком только одному из s прямоугольников. Не закрашенных клеток, примыкающих по сторонам к закрашенным, на единицу меньше, чем закрашенных, поэтому хотя бы один из s прямоугольников не выйдет за пределы своей заштрихованной клетки, т.е. будет с ней совпадать. Возвращаясь к ступенчатым треугольникам T1 и T2, можно сказать, что mn, а kn1. Но так как m+k=2n, то либо m=n, либо k=n1. Значит, либо в T1, либо в T2 найдется прямоугольник, совпадающий с клеткой клетчатой бумаги.

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

Сведение кратных интегралов к повторным

Сведение двойного интеграла к повторному

Теорема 1

Пусть:

  1. функция f(x,y) интегрируема в некотором прямоугольнике Π={(x,y):axb,cyd};
  2. для любых x[a,b] существует интеграл dcf(x,y)dy.

Тогда dcf(x,y)dy — интегрируемая на отрезке [a,b] функция от аргумента x, и справедлива следующая формула:
Πf(x,y)dxdy=badxdcf(x,y)dy.

Доказательство

Спойлер

Следствие 1

Пусть:

  1. существует двойной интеграл Πf(x,y)dxdy;
  2. для любых x[a,b] существует интеграл dcf(x,y)dy;
  3. для любых y[c,d] существует интеграл baf(x,y)dx.

Тогда справедлива формула

Πf(x,y)dxdy=badxdcf(x,y)dy= dcdybaf(x,y)dx.(3)

Следствие 2

Непрерывность функции f(x,y) в прямоугольнике Π влечет выполнимость условий следствия 1, а значит, справедлива формула (3).

Если функция ψ(x) интегрируема на отрезке [a,b], то формула (3) остается справедливой при замене функции f(x,y) на ψ(x)f(x,y).

Определение 1

Пусть:

  1. ϕ(x) и ψ(x) — функции, непрерывные на отрезке [a,b];
  2. для любых x(a,b) выполняется неравенство ϕ(x)<ψ(x).

Тогда область (рисунок 1)
Ω={(x,y):ϕ(x)<y<ψ(x),a<x<b}
будем называть элементарной относительно оси y.
Fig_1
Поскольку граница области δΩ состоит из графиков непрерывных функций, то Ωизмеримая по Жордану область.

Теорема 2

Пусть:

  1. Ω — элементарная область относительно оси y;
  2. функция f(x,y) интегрируема на области ¯Ω=ΩδΩ;
  3. для любых x[a,b] существует интеграл ψ(x)ϕ(x)f(x,y)dy.

Тогда справедлива следующая формула:
Ωf(x,y)dxdy=badxψ(x)ϕ(x)f(x,y)dy.(4)

Доказательство

Спойлер

Пример 1

Вычислить двойной интеграл Gx2dxdy по области G={(x,y):1<x<1,x2<y<2} (рисунок 3).
Fig_3

Решение

Спойлер

Пример 2

Свести к повторному интеграл Gf(x,y)dxdy, где G — область, ограниченная окружностями x2+y2=4 и x22x+y2=0 (рисунок 4).
Fig_4

Решение

Спойлер

Сведение тройного интеграла к повторному

Определение 2

Область ΩR3 будем называть элементарной относительно оси z, если
Ω={(x,y,z):(x,y)GR2,ϕ(x,y)<z<ψ(x,y)},
где G — ограниченная в R2 область, а функции ϕ(x,y) и ψ(x,y) непрерывны на ¯G, где ¯G — замыкание области G.

Теорема 3

Если функция f(x,y,z) непрерывна на ¯Ω=ΩδΩ, где область Ω элементарна относительно оси z, то справедлива следующая формула:
Ωf(x,y,z)dxdydz=Gdxdyψ(x,y)ϕ(x,y)f(x,y,z)dz.(6)

Доказательство

Спойлер

Пример 3

Вычислить тройной интеграл Gzdxdydz, где G — область, ограниченная плоскостями x+y+z=1, x=0, y=0 и z=0 (рисунок 5).
Fig_5

Решение

Спойлер

Тест

Проверьте свои знания по теме, пройдя этот небольшой тест.