Метка: разбиение

M1635. О разбиении сторон правильного треугольника на $n$ равных отрезков.

Задача из журнала «Квант» (выпуск №2, 1998).

Условие

    Каждая сторона правильного треугольника разбита на $n$ равных отрезков, и через все точки деления проведены прямые, параллельные сторонам. Данный треугольник разбился на $n^{2}$ маленьких треугольников-клеток. Треугольники, расположенные между двумя соседними параллельными, образуют полоску.

  1. Какое наибольшее число клеток можно отметить, чтобы никакие две отмеченные клетки не принадлежали одной полоске ни по одному из трёх направлений, если $n=10$?
  2. Тот же вопрос для $n=9$.

Решение

  1. На рисунке 1 показан способ отметить 7 треугольников. Чтобы доказать, что при $n=10$ нельзя отметить 8 треугольников, разрежем исходный треугольник средними линиями на четыре треугольника. Каждый из них состоит из 25 треугольничков. Обозначим количества отмеченных треугольничков в угловых треугольниках буквами $k,l,m$, а в центральном — $n$. Тогда $k+l+n \leq 5$, поскольку два угловых треугольника вместе с центральным состоят из 5 полос. Аналогично,$l+m+n \leq 5$ и $m+k+n \leq 5$.
    Сложим эти три неравенства: $2k+2l+2m+3n \leq 15$. Следовательно, $ k+l+m+n \leq \frac{1}{2} \cdot (2\cdot k+2\cdot l+2\cdot m+3\cdot n)\leq \frac{15}{2} < 8 $.

  2. Решим задачу для произвольного $n$. Рассмотрим одну из сторон исходного треугольника и пронумеруем полоски соответствующего направления следующим образом: полоска, прилегающая к стороне, пусть будет иметь номер 1; следующая за ней — номер 2;…; полоска, состоящая из одного треугольника, примыкающего к вершине исходного большого треугольника, получит номер $n$.
    Теперь положение любого из $n^{2}$ треугольничков можно задать тройкой чисел — номеров полосок, в которых он лежит.
    Уточнение о номерах полосок

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

    [свернуть]

    Введённые нами тройки номеров = «координаты» треугольничков — не могут принимать произвольные значения. Их сумма равна $n+2$, если треугольничек расположен «остриём вверх» (т.е. ориентирован так же, как исходный большой треугольник), и равна $n+1$, если «остриём вниз».
    Предположим, отмечены $k$ треугольников, никакие два из которых не попали в одну полоску. Оценим сумму $S$ всех их координат двумя способами. С одной стороны, сумма координат любого треугольника не превышает $n+2$, поэтому $ S\leq k\cdot (n+2) $. С другой стороны, сумма значений одной из координат по всем отмеченным треугольникам не меньше чем $1+2+3+\cdots +k=\frac{k\cdot (k+1)}{2}$. Значит, $3\cdot \frac{k\cdot (k+1)}{2}\leq S\leq k\cdot (n+2)$, откуда $3\cdot \frac{k+1}{2}\leq n+2$, т.е. $k+1\leq \frac{2\cdot n+4}{3}$. Итак, $k\leq \frac{2\cdot n+1}{3}\cdots$.
    Отметить $[\frac{2\cdot n+1}{3}]$ треугольничков можно следующим образом. Рассмотрим число $m=[\frac{n+1}{3}]$. На основании исходного треугольника отметим $(m+1)-й$ слева треугольничек, расположенный остриём вверх. В этой же вертикали отметим и все остальные треугольнички, ориентированные остриём вверх (рис.2).

    Всего в этой вертикали отмечено $(m+1)$ треугольничков. На второй горизонтальной полосе большого треугольника отметим $(2\cdot m+1)-й$ (считая слева) треугольничек, расположенный остриём вверх. Отметим и все остальные треугольнички этой вертикали, ориентированные остриём вверх. Всего в этой вертикали будет отмечено $n-1-2\cdot m$ треугольничков.
    Общее количество отмеченных треугольничков есть $m+1+n-1-2\cdot m=n-m=n-[\frac{n+1}{3}]=[\frac{2\cdot n+1}{3}]$.
    Чтобы проверить последнее равенство, достаточно разобрать три случая: $n$ равно $3\cdot a, 3\cdot a+1$ и $3\cdot a+2$.

M567. О разбиении единичного отрезка на $p+q$ равных отрезков

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

Условие

Натуральные числа $p$ и $q$ взаимно просты. Отрезок $\left[ 0;1 \right]$ разбит на $p+q$ одинаковых отрезков (рис. $1$). Докажите, что в каждом из этих отрезков, кроме двух крайних, лежит ровно одно из $p+q-2$ чисел $\frac { 1 }{ p } , \frac { 2 }{ p }, \dots \frac { p-1 }{ p }, \frac { 1 }{ q }, \frac { 2 }{ q }, \dots \frac { q-1 }{ q }$.

567-1

Решение

Приведём два решения.

Первое решение. Из условия следует, что каждое из чисел $p$ и $q$ взаимно просто с числом $n=p+q$, поэтому никакие две из точек $\frac { i }{ p } ,\frac { j }{ q } ,\frac { k }{ n } $ (отличные от $0$ и $1$) не совпадают. Поскольку $\frac { 1 }{ p } >\frac { 1 }{ n } $ и $\frac { 1 }{ q } >\frac { 1 }{ n } $, любые две из точек $\frac { i }{ p } $ лежат в разных отрезках $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right] $ и любые две из точек $\frac { j }{ q } $ — тоже. Нужно лишь доказать, что какие-то две точки $\frac { i }{ p } $ и $\frac { j }{ q } $ не могут попасть в один и тот же отрезок $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right]$ $\left( k=1,2,\dots,n-2 \right)$. Но это сразу следует из того, что дробь $\frac { k }{ n } =\frac { i+j }{ p+q } $ лежит между $\frac { i }{ p } $ и $\frac { j }{ q } $ (см., например, рисунок $2$: угловой коэффициент диагонали параллелограмма заключён между угловыми коэффициентами его сторон*).

M567-2

Второе решение. Нарисуем на клетчатой бумаге прямоугольник размерами $p\times q$ клеток и проведём в нём диагональ $OE$ (рис. $3$) — она и будет играть роль отрезка $\left[ 0;1 \right] $ нашей задачи. Линии одного направления (синие) делят её на $p$ равных частей, другого (красные) — на $q$ равных частей. Проведём через вершины клеток ещё ряд параллельных прямых — под углом $45^{\circ}$ к линиям сетки (на рисунке это — чёрные прямые $x+y=k$, где $k=1,2,\dots,p+q-1.$ Они делят $\left[ OE \right] $ на $n=p+q$ одинаковых отрезков. Утверждение задачи теперь становятся почти очевидным. В самом деле, на $\left[ OE \right] $ между любыми двумя сине-красными точками обязательно лежит чёрная точка: ведь, пересекая какую-то клетку, $\left[ OE \right] $ обязательно пересекает и её чёрную диагональ. (Можно вместо этого сказать и так: между любыми двумя точками пересечения $\left[ OE \right] $ с соседними чёрными прямыми лежит точка пересечения с синей или красной линией.)

В этом решении взаимная простота чисел $p$ и $q$ гарантирует, что $\left[ OE \right] $ не проходит через узлы сетки, отличные от $0$ и $E$ (глядя на наш маленький рисунок, в этом можно усомниться).

M567-3

Задача М567 допускает замечательное обобщение. Пусть $\alpha$ и $\beta $ — любые положительные числа, связанные соотношением $\frac { 1 }{ \alpha } +\frac { 1 }{ \beta } =1$. Отметим на числовой оси всевозможные числа вида $i\alpha $ и $j\beta \left( i\in Z,j\in Z \right)$. Тогда каждый отрезок $\left[ k;k+1 \right]$ оси $\left( k\in Z \right)$, ни в один из концов которого не попало отмеченное число, содержит ровно одно из отмеченных чисел $i\alpha$, $j\beta$. Наша задача эквивалента этому факту при рациональных $\alpha$ и $\beta$: нужно взять $\alpha =\frac { n }{ p } , \beta =\frac { n }{ q } $ (роль отрезка $\left[ 0;1 \right] $ будет играть теперь отрезок $\left[ 0;n \right])$. Этот же факт (для иррациональных $\alpha$ и $\beta$) упоминался недавно в решении задачи М538 («Квант», 1979, № $11$), очень похожем на наше второе решение М567.

Н.Васильев

(*) Тот факт, что «медианта» двух дробей $\frac { i }{ p }$ и $\frac { j }{ p }$ лежит между ними, использовался в статье «Близкие дроби» («Квант», 1975, №8).

Разбиение множества

Определение:
Пусть $A$ — некоторое непустое множество ($A \neq \emptyset$). Разбиением множества $A$ называется непустое множество подмножеств $A_j \subset A$, $j \in I$ ($I$ — некоторое множество индексов), такое, что выполняются два условия:

  1. $\underset {j \in I}{\bigcup}A_j = A$
  2. $A_i \bigcap A_j = \emptyset$, для любых $i, j \in I$ таких, что $i \neq j$

Пример 1:
Множество $\mathbb R$ можно разбить следующим образом:
$A_1 = \mathbb R^+$, $A_2 = \left\{0\right\}$, $A_3 = \mathbb R^-$
Графически это можно изобразить следующим образом:разбиение 1
Пример 2:
Аналогично множество $\mathbb Z$ можно представить в виде разбиения на множества четных и нечетных целых чисел:
$A_1 = 2\mathbb Z$, $A_2 = 2\mathbb Z + 1$
Графически это можно представить следующим образом:
разбиение 2
Пример 3:
Пусть задано множество $A$, состоящее из трех элементов $\left\{a, b, c\right\}$. Существует $5$ способов разбить это множество:

  • $\left\{\left\{a, b, c\right\}\right\}$
  • $\left\{\left\{a\right\}, \left\{b\right\}, \left\{c\right\}\right\}$
  • $\left\{\left\{a, b\right\}, \left\{c\right\}\right\}$
  • $\left\{\left\{a\right\}, \left\{b, c\right\}\right\}$
  • $\left\{\left\{b\right\}, \left\{a, c\right\}\right\}$

Литература:

  • Белозеров Г.С. Конспект лекций по линейной алгебре

Разбиение множества

Тест

Разбиение на попарно непересекающиеся классы. Примеры

Разбиение на попарно непересекающиеся классы

Пусть $latex A \not = \varnothing $, разбиением множества $latex A $ называется не пустое множество подмножеств $latex A_j \in A, j \in J $, такое, что выполняется два условия:
1. $latex \bigcup{} A_j= A, j \in J $.
2. $latex A_i \cap A_j= \varnothing $, для $latex i \not = j $.

 

 

 

 

 

 

Разбиение множества $latex S $ на классы $latex S_1, S_2, …,S_6 $.

Примеры

Приведем несколько примеров разбиения:

1. Множество четырехугольников $latex A $ разбито на два класса:
трапеции и прямоугольники. Данные подмножества попарно не пересекаются, а их объединения совпадают с множеством $latex A $.

2. Множество четырехугольников $latex B $ разбито на три класса:
квадраты, параллелограммы, прямоугольники. Так как прямоугольник и квадрат — частные случаи параллелограмма, то данные подмножества пересекаются, значит, не выполнено первое условие классификации, и разбиение множества $latex B $ не получено.

3. Дано множество прямых $latex C $ в пространстве, которое разбито на классы по их взаимному расположению: параллельные, пересекающиеся, скрещивающиеся. Данные подмножества попарно не пересекаются, а их объединения совпадают с множеством $latex C $.

4. Дано множество $latex N $, которое можно разделить на два класса: $latex N_1 $ и $latex N_2 $, где $latex N_1 $ — множество натуральных четных чисел, а $latex N_2 $ — множество натуральных нечетных чисел.

5. Множество $latex X $ разбито на три класса: $latex X_1 $, $latex X_2 $ и $latex X_3 $. $latex X_1 $ множество чисел, которые делятся на $latex 2 $, $latex X_2 $ — множество чисел, которые делятся на  $latex 3 $, $latex X_3 $ множество чисел, которые делятся на $latex 5 $. Но существуют числа, которые могут делится одновременно и на $latex 2 $, $latex 3 $ и $latex 5 $. Отсюда следует, что подмножества пересекаются, и разбиение не получено.

Литература:

Разбиение на попарно непересекающиеся классы

Вопросы по изложенной теме

M1231. О разбиении плоскости графиками многочленов второй степени

Условие

На какое наибольшее число частей могут разбить плоскость [latex]Oxy[/latex] графики [latex]n[/latex] квадратных трехчленов вида [latex]y=ax^{2}+bx+c (n=1, 2, 3, …)[/latex]?

Ответ: [latex]n^{2}+1[/latex].

Решение

Докажем по индукции, что число частей не превосходит [latex]n^{2}+1[/latex]. Для [latex]n=1[/latex] это ясно: парабола делит плоскость на две части.
Пусть доказано, что [latex]n-1[/latex] графиков делят плоскость не более, чем на [latex](n-1)^{2}+1[/latex] частей. Проведем последний, [latex]n[/latex]-й график. Он пересекается с каждым из [latex]n-1[/latex] предыдущих максимум в двух точках, т.е. он будет разбит не более чем на [latex]2(n-1)+1=2n+1[/latex] кусков (включая два крайних, уходящих в бесконечность). Каждый из этих кусков параболы делит одну из имеющихся частей плоскости на две. Таким образом, при проведении последней параболы число частей увеличится не более чем на [latex]2n+1[/latex], т.е. не превзойдет [latex](n-1)^{2}+1+2n+1=n^{2}+1[/latex].
К задаче M1231
Легко строится пример, когда все графики попарно пересекаются в двух точках (см. рисунок) — при этом получится максимальное число частей, указанное в ответе.
Точно такие же образом можно подсчитать максимальное число частей, на которые делят плоскость [latex]n[/latex] прямых, [latex]n[/latex] окружностей и т.п.

Н.Васильев