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)