понедельник, 9 января 2012 г.

суббота, 7 января 2012 г.

Симметрический многочлен от геометрической прогрессии


Обозначим k-ый элементарный симметрический многочлен от n переменных через Qk(x1,...,xn). Чему равно Qk(1,2,4,...,2^{n-1})?

Некая туманная подсказка: это число связано с числом плоскостей размерности k в конечном векторном пространстве размерности n над полем из двух элементов. У меня формула получилась при помощи подсчета функции Мёбиуса линейного матроида, ассоциированного с этим векторным пространством, двумя разными способами, однако тут есть и другое решение. Искомые числа, назовем их a_{k,n} можно естественным образом записать в треугольник, типа треугольника Паскаля, причем можно вывести правило, позволяющее из двух вышестоящих получить следующее (как в случае с биномиальными коэффициентами), однако это правило выглядит несколько сложнее. Такие правила называются грамматиками Дика. Похожее правило возникает и при подсчете k-мерных плоскостей в n-мерном бинарном пространстве.

Вероятность тотального беспорядка

Еще комба, обнаруженная в статье Уитни хрен знает какого бородатого года, где он по сути рассказывает о прелестях формулы включения-исключения, в том числе вводит хроматический многочлен графа. Но к графам задача отношения не имеет.


Даны две колоды из N карт - в каждой колоде все карты разные, но состав обоих колод одинаковый. Случайным образом выкладывают обе колоды в два ряда - одну колоду над другой. С какой вероятностью ни в одной позиции не будет совпадения карт? (порядки карт в обоих рядах равновероятны)

Задачка не то чтобы сложная, но ответ получается забавный)) Заодно можете посчитать при каких N он больше 1/e.

Прыжки по клеточному полю

Комбинаторика.

За один ход саранча прыгает в одну из четырех сторон: вверх, вниз, вправо или влево на метр. Сколько различных путешествий длиной в 2n ходов с началом и концом в одной точке может совершить саранча? Ответ не должен содержать сумм.

Задача не сложная, но по некоторым причинам, связанным с самодвойственностью двумерных фигур, эта задача в трехмерном пространстве усложняется.

Ну и заодно вопрос: как бы так посчитать количество возможных путешествий из точки (0,0) в точку (x,y)?

Жуки на ребрах многогранника


Хорошая задачка с последней ММО. 


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



На ММО давали вариант этой задачи, где жуки ползают по ребрам тетраэдра, но общая формулировка, конечно, интереснее.
В курсе алгебры изучается такой факт: группа собственных движений додекаэдра изоморфна группе четных перестановок. В свое время интересовал вопрос: как бы это так естественным образом доказать. На рисунке доказательство:


В додекаэдр вписываются пять тетраэдров. Каждое собственное движение додекаэдра осуществляет перестановку тетраэдров, т.е. перестановку на множестве из пяти элементов. Гомоморфизм из группы в группу построен, дальше - дело техники. 

Такое чудо можно собрать самому, что я разумеется и сделал. Вот оригинальная схема, придуманная Томом Халлом http://mars.wnec.edu/~th297133/fit.html

Задача о школьницах

Задача о школьницах. Ее можно решать не только перебором.

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast (в оригинальной формулировке)

("Пятнадцать школьниц каждый день в течение недели разбиваются на тройки и гуляют. Надо сделать так, чтобы каждая с каждой гуляла в одной тройке не более раза"). Занайдено в википедии.