Треп о математике 2

Sergei Nickolaev написал(а) к All в Mar 23 15:08:08 по местному времени:

Привет, All!

Немного о конечных множествах.
Прежде, чем заниматься обобщением понятия количества элементов на бесконечные множества, поразбираемся с конечными. Чтобы было, что обобщать :-)

Есть весьма изящное соотношение количеств элементов в конечных множествах, в их объединии и пересечениях. Количество элементов в конечном множестве A будем обозначать |A|.
Для двух множеств: |A1 U A2| = |A1| + |A2| - |A1 П A2|
Обоснование очень простое: Если пересечение множеств непусто, то сложив количества элементов обоих множеств, мы посчитаем элементы пересечения дважды (лишнее - вычитаем).
Для трех множеств:
|A1 U A2 U A3| = |A1| + |A2| + |A3| -
|A1 П A2| - |A1 П A3| - |A2 П A3| +
|A1 П A2 П A3|
Можно обосновать похожим образом, но рассуждения несколько более сложные.
Формула обобщается на случай произвольного числа множеств: пересечения четных количеств множеств учитываются со знаком минус, нечетных - со знаком плюс.
Легко доказывается по индукции (оставляю в качестве задачки).

Есть другой способ доказательства, займемся им, потому, что он привлекает новое, очень полезное понятие: характеристическая функция подмножества.

Рассматриваем случай, когда все множества A1, ... An, входящие в выражение, являются подмножествами одного множества W, назовем его универсальным. Это не уменьшает общности, в качестве такого годится, например, объединение множеств A1,...An или любое более "широкое" множество.
Характеристическая функция подмножества Ai - это функция определенная на множестве W, принимающая значение 1 на элементах Ai и значение 0 на элементах W, которые не являются элементами Ai.
Операциям объединения и пересечения подмножеств соответствуют некоторые операции над их характеристическими функциями. Пересечению подмножеств соответствует произведение характеристических функций. С объединением не столь просто, но разобраться можно :-).
Добавим еще одну операцию - дополнение. Содержательно это те элементы, которые нужно добавить к подмножеству, чтобы получить универсальное множество W (то есть W \ Ai).
Характеристическую функцию буду записывать, указывая подмножество в квадратных скобках (принято записывать как нижний индекс, но здесь не получается).

Для пересечения A1 П A2: X[A1 П A2](u) = X[A1](u) * X[A2](u).
Для дополнения: X[W \ A1](u) = 1 - X[A1](u).

Есть замечательное утверждение (оставляется как задача):
Объединение нескольких подмножеств равно дополнению пересечений дополнений этих подмножеств.
Рассуждение на самом деле несложное, чтобы увидеть в чем дело можно взять диаграмму Венна для 3-х множеств (A1, A2, A3), нарисовать вокруг нее круг (он будет обозначать универсальное множество W). Найти на получившейся диаграмме дополнения к трем множествам A1, ... A3, увидеть их пересечение и будет понятно, почему дополнение к этому пересечению - объединение A1, ... A3.

Характеристическая функция объединения теперь получается такая:
X[A1 U A2 U ... U An](u) = 1 - (1 - X[A1](u))(1 - X[A2](u))*...(1 - X[An](u))

Если в правой части раскрыть скобки, единица сократится, останутся характеристические функции для всех Ai (с плюсом), попарные произведения функций (с минусом), произведения по 3 (с плюсом) и так далее. В точности как в формуле для количества элементов объединения. Остается сообразить, что количество элементов подмножества равно количеству 1 в значениях характеристической функции подмножества (другими словами - сумме значений характеристической функции по всем элементам универсального множества).

Кто разберется в этой технической штучке - хорошо, нет - основные идеи дальнейшего эта неудача понять не помешает. Можно помочь себе картинками. Взять W = {0,1,2,3,4,5,6}; A1={1,2,3}; A2={2,3,4}; A3={3,4,5}. Нарисовать эти точки на оси X, построить графики для характеристических функций (удобно использовать разные цвета). Скорее всего, по этой картинке идею доказательства можно понять без особых вычислений :-)

Самое важное насчет количества элементов конечных множеств: для выявления равенства количества элементов в двух множествах вовсе не обязательно пересчитывать элементы. Вместо этого можно построить взаимно-однозначное соответствие между элементами этих множеств. То есть, каждому элементу первого множества сопоставить ровно один элемент второго (каждому - свой отдельный) и наоборот. Если есть такое соответствие - число элементов в этих множествах равно. Это - основная идея для обобщения понятия числа элементов на бесконечные множества (об этом уже в другой раз). И полезная идея для решения некоторых задач :-)

Еще: количество элементов конечного множества называется также мощностью этого множества. Для общности терминологии для конечных и бесконечных множеств.

Вообще, задачи подсчета числа элементов в конечных множествах относятся к разделу математики, который называется комбинаторика. Но лезть в нее мне не хочется, там, в основном - техника. Идеи - интереснее :-)

Задачки:

1. На окружности выбраны 1000 белых точек и одна чёрная. Чего больше - треугольников с вершинами в белых точках или четырёхугольников, у которых одна вершина чёрная, а остальные три белые?

2. Докажите, что последовательностей длины n, составленных из нулей и единиц, столько же, сколько подмножеств у множества {1, 2, . . . , n}.

3. Пусть W - непустое конечное множество. Докажите, что подмножеств множества W, имеющих чётную мощность, столько же, сколько имеющих нечётную мощность.

4. Докажите, что способов расстановки скобок (указывающих порядок действий) в неассоциативном произведении из n элементов столько же, сколько способов разбить выпуклый (n + 1)-угольник на треугольники непересекающимися диагоналями. (Для произведения трёх множителей есть два варианта (ab)c и a(bc); с другой стороны, есть два способа разрезать четырёхугольник на два треугольника, проведя диагональ.
Для произведения четырёх сомножителей и для пятиугольника имеется по 5 вариантов.)

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 14:18:40 по местному времени:

Здpавствуй, Sergei!

Пятница 31 Марта 2023 15:08, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+64275b30:

SN> Самое важное насчет количества элементов конечных множеств: для
SN> выявления равенства количества элементов в двух множествах вовсе не
SN> обязательно пересчитывать элементы. Вместо этого можно построить
SN> взаимно-однозначное соответствие между элементами этих множеств. То
SN> есть, каждому элементу первого множества сопоставить ровно один
SN> элемент второго (каждому - свой отдельный) и наоборот.

Попытаюсь.

SN> 1. На окружности выбраны 1000 белых точек и одна чёрная. Чего больше -
SN> треугольников с вершинами в белых точках или четырёхугольников, у
SN> которых одна вершина чёрная, а остальные три белые?

Для каждого белого треугольника чёрная точка между двумя белыми. Если заменить отрезок между этими белыми точками на ломаную белая-чёрная-белая, каждому треугольнику будет соответствовать четырехугольник.

SN> 2. Докажите, что последовательностей длины n, составленных из нулей и
SN> единиц, столько же, сколько подмножеств у множества {1, 2, . . . , n}.

Две строки, одна под другой.
1,2,3,4,5....n
,*,*,*,....n
* означает 1 или 0. Если 1, то соответствующая цифра входит в первое подмножество, если 0, то не входит. Соответствие установлено.

SN> 3. Пусть W - непустое конечное множество. Докажите, что подмножеств
SN> множества W, имеющих чётную мощность, столько же, сколько имеющих
SN> нечётную мощность.

Подмножество из одного элемента имеет два подмножества: состоящее из этого самого элемента (одна штука, нечётное число элементов) и пустое множество (ноль - чётное число) Добавление каждого элемента удваивает число подмножеств: остаются те, что уже были и те, что уже были плюс новый элемент. Среди тех, что уже были, количества подмножеств, имеющих чётную и нечётную мощность, равны. Среди тех, к которым добавился новый элемент, тоже равны, поскольку чётное число + 1 = нечётное, а нечётное +1 = чётное.

SN> 4. Докажите, что способов расстановки скобок (указывающих порядок
SN> действий) в неассоциативном произведении из n элементов столько же,
SN> сколько способов разбить выпуклый (n + 1)-угольник на треугольники
SN> непересекающимися диагоналями. (Для произведения трёх множителей есть
SN> два варианта (ab)c и a(bc); с другой стороны, есть два способа
SN> разрезать четырёхугольник на два треугольника, проведя диагональ. Для
SN> произведения четырёх сомножителей и для пятиугольника имеется по 5
SN> вариантов.)

Глянув на формулу с факториалами, понял, что сходу мне эту задачу не решить и удалился думать.


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 14:29:52 по местному времени:

Привет, Alexander!

SN>> 1. На окружности выбраны 1000 белых точек и одна чёрная. Чего
SN>> больше - треугольников с вершинами в белых точках или
SN>> четырёхугольников, у которых одна вершина чёрная, а остальные три
SN>> белые?

AН> Для каждого белого треугольника чёрная точка между двумя белыми. Если
AН> заменить отрезок между этими белыми точками на ломаную
AН> белая-чёрная-белая, каждому треугольнику будет соответствовать
AН> четырехугольник.

Верно, но нужно было еще отметить, что и наоборот тоже.

SN>> 2. Докажите, что последовательностей длины n, составленных из
SN>> нулей и единиц, столько же, сколько подмножеств у множества {1,
SN>> 2, . . . , n}.

AН> Две строки, одна под другой.
AН> 1,2,3,4,5....n
AН> ,*,*,*,....n
AН> * означает 1 или 0. Если 1, то соответствующая цифра входит в первое
AН> подмножество, если 0, то не входит. Соответствие установлено.

Мне больше нравится вариант с характеристическими функциями. Последовательности a1, ... an из нулей и единиц сопоставляем функцию, определенную на элементах множества {1, ... n}: X(i)=ai. Соответствие - взаимно однозначное. Каждая из таких функций - характеристическая для некоторого подмножества множества {1, ... n}. Поскольку мы берем все_ последовательности из нулей и единиц, то мы получаем _все характеристические функции, получаем, в итоге, взаимно-однозначное соответствие между последовательностями из нулей и единиц и подмножествами множества {1, ... n}.

SN>> 3. Пусть W - непустое конечное множество. Докажите, что
SN>> подмножеств множества W, имеющих чётную мощность, столько же,
SN>> сколько имеющих нечётную мощность.

AН> Подмножество из одного элемента имеет два подмножества: состоящее из
AН> этого самого элемента (одна штука, нечётное число элементов) и пустое
AН> множество (ноль - чётное число) Добавление каждого элемента удваивает
AН> число подмножеств: остаются те, что уже были и те, что уже были плюс
AН> новый элемент. Среди тех, что уже были, количества подмножеств,
AН> имеющих чётную и нечётную мощность, равны. Среди тех, к которым
AН> добавился новый элемент, тоже равны, поскольку чётное число + 1 =
AН> нечётное, а нечётное +1 = чётное.

Здесь мне тоже больше нравится вариант с характеристическими функциями. Берем любой элемент w множества W (всегда есть, поскольку W - не пусто). Разбиваем все характеристические функции, определенные на элементах W на пары: в каждой паре значения обеих характеристических функций совпадают на всех элементах W, кроме w, на элементе w значения разные. Количество значений 1 у характеристической функции равно количеству элементов в соответствующем подмножестве. У любой из таких пар количество единиц отличается на 1, поэтому в любой паре мощность соответствующих подмножеств тоже отличается на 1, значит одно четной мощности, другое - нечетной.

SN>> 4. Докажите, что способов расстановки скобок (указывающих порядок
SN>> действий) в неассоциативном произведении из n элементов столько
SN>> же, сколько способов разбить выпуклый (n + 1)-угольник на
SN>> треугольники непересекающимися диагоналями. (Для произведения
SN>> трёх множителей есть два варианта (ab)c и a(bc); с другой
SN>> стороны, есть два способа разрезать четырёхугольник на два
SN>> треугольника, проведя диагональ. Для произведения четырёх
SN>> сомножителей и для пятиугольника имеется по 5 вариантов.)

AН> Глянув на формулу с факториалами, понял, что сходу мне эту задачу не
AН> решить и удалился думать.

После некоторых размышлений я решил, что задача требует дополнительных разъяснений. Автор предполагал больше знаний у решающего задачу. Я подумаю, решу, что еще нужно рассказать, тогда вернемся к этой задаче ... Аккуратного решения у меня пока нет, но я уверен, что факториалы не понадобятся :-). Нужно взаимно-однозначное соответствие между вариантами разбиения многоугольника на треугольники и вариантами расстановки скобок ...

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 13:44:28 по местному времени:

Привет, Alexander!

SN>> 4. Докажите, что способов расстановки скобок (указывающих порядок
SN>> действий) в неассоциативном произведении из n элементов столько
SN>> же, сколько способов разбить выпуклый (n + 1)-угольник на
SN>> треугольники непересекающимися диагоналями. (Для произведения
SN>> трёх множителей есть два варианта (ab)c и a(bc); с другой
SN>> стороны, есть два способа разрезать четырёхугольник на два
SN>> треугольника, проведя диагональ. Для произведения четырёх
SN>> сомножителей и для пятиугольника имеется по 5 вариантов.)

AН> Глянув на формулу с факториалами, понял, что сходу мне эту задачу не
AН> решить и удалился думать.

Я доразобрался с этой задачей. Никаких факториалов не требуется :-).
Сначала необходимые пояснения: автор задачи явно предполагал, что задачу будут решать более-менее математики, для остальных некоторые вещи нужно рассказать. А именно, что автор понимает под "способами расстановки скобок, указывающих порядок действий, в неассоциативном произведении из n элементов".

Термин "произведение" здесь использован только в том смысле, что символ операции не пишется (реальные произведения так часто и записываются).
"Неассоциативное" означает, что строки с разной расстановкой скобок считаются разными. Скажем, обычное произведение всех более-менее привычных чисел - ассоциативно, (ab)c и a(bc) дают одинаковый результат и выражения не считаются разными. А операция "разность" для множеств - неассоциативная, выражения
(A \ B) \ C и A \ (B \ C) - разные, то есть могут давать разные результаты.

В этой задаче операция - совершенно абстрактная, про нее известно только то, что она неассоциативна.

Некоторые способы расстановки скобок просто бессмысленны, они не рассматриваются:
1. Пустая пара скобок ().
2. Неуравновешенный комплект: число открывающих скобок не равно числу закрывающих.

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

Есть такая вещь, как порядок выполнения операций "по умолчанию". Часто допускается писать abc, подразумевая выполнение операций слева направо. Исключаем. Требуем явного указания порядка, то есть вместо abc должно быть (ab)c. Обеспечение этого требования приводит к следующим правилам:
1. Все выражения должны иметь вид:
ЭЭ или СЭ или ЭС или СС (Э - элемент, С - скобки с содержимым).
2. Скобки с содержимым должны иметь вид (ЭЭ) или (СЭ) или (ЭС) или (СС).

Примеры:
(ab)c(de) - неправильное выражение, правильным будет ((ab)c)(de)
(abc)de - неправильное выражение, правильным будет (((ab)c)d)e

Еще существенная вещь - все элементы в выражении различны. Автор об этом не упоминает, но без такого условия - не выйдет.

Теперь идея доказательства (без ряда подробностей, остается несколько задач для решения):
Пусть в выражении будет n элементов a[1], a[2], ..., a[n]. Номера соответствуют положению элементов в выражении.
Берем выпуклый (n+1)-угольник (для рисования картинки лучше взять похожий на правильный). Выбираем произвольную вершину и пририсовываем к ней номер 1. В том направлении (по часовой стрелке или против) которое нам нравится последовательно нумеруем вершины. Диагональ из вершины i в вершину k обозначим как пару <i,k>. Чтобы диагональ имела одно обозначение (а не два), будем соблюдать условие i<k. На самом деле, для реальной диагонали будет выполняться условие i<k-1. Диагонали <i,k> сопоставим пару скобок в выражении: открывающая скобка перед a[i] и закрывающая скобка после a[k-1]. Такое соответствие взаимно-однозначно и в нем не появляются бессмысленные и не влияющие на порядок выполнения операций скобки (задача - доказать) и невозможные диагонали (задача - доказать). Если мы выберем какое-нибудь разбиение многоугольника на треугольники непересекающимися диагоналями, то соответствующее расположение скобок даст "правильное" выражение (задача - доказать); если мы возьмем любое "правильное" выражение, соответствующие диагонали не будут пересекаться и разбьют многоугольник на треугольники (задача - доказать).

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)