вотэтазадача 14. Симметрический многочлен от геометрической прогрессии

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

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

вотэтазадача 16. Про картишки и число e.

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

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

вотэтазадача 18. Прыжки по клеточному полю

Когда-то на досуге придумалась такая нехитрая комбинаторика.

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

Задача не сложная, но по некоторым причинам, связанным с самодвойственностью двумерного куба, задача оказывается проще в 2d чем в 3d.

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

вотэтазадача 21. Жуки на многограннике.

Видел эту задачу, когда проверял какую-то ММО, впечатлился. Авторство, если не ошибаюсь Антона Клячко, видел еще название лемма Винберга.

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

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

вотэтазадача 22. Группа додекаэдра

В курсе алгебры изучается такой факт: группа собственных движений додекаэдра изоморфна группе четных перестановок. Докажите геометрически.

Картинка тут ни на что не намекает, просто для красоты:)


вотэтазадача 25. Задача о школьницах

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

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 (в оригинальной формулировке)

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

И дополнение.

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

вотэтазадача 27. Тела, которые выглядят как эллипсоиды

Такая задача придумалась на досуге.

1) Доказать, что любая ортогональная проекция эллипсоида на плоскость --- эллипс.

2) Верно ли, что выпуклое тело, все ортогональные проекции которого --- эллипсы, является эллипсоидом?

И еще лайт-версия: верно ли, что выпуклое тело, все ортогональные проекции которого --- круги, является шаром?

Заметьте, что на плоскости аналог этого факта не верен. Релевантная ссылка.

вотэтазадача 28. Надувание квадратных файлов

Файл делается из двух квадратных листов нерастяжимого материала, приклеенных друг к другу со всех четырех сторон. Сторона квадрата равна единице. Вопрос: до какого наибольшего объёма можно такой файлик надуть?

вотэтазадача 30. Две ортогональных плоскости

Я долго тупил над этой задачей, хотя, возможно, она очевидна.

Рассмотрим координатное пространство R^n со стандартным скалярным произведением. Рассмотрим линейное подпространство L и его ортогональное дополнение K. Доказать, что в одном из этих пространств лежит ненулевой вектор с неотрицательными координатами.

Недавно обнаружил, что у прикладников встречается понятие систем Леонтьева. Возможно, это имеет отношение к сабжу, но это не точно.

вотэтазадача X. Красивый эксперимент по теории чисел и геометрии

Рекомендую всем тем, кто этого ещё не делал. Нарисуйте треугольник Паскаля, но вместо чисел в этом треугольнике записывайте их остатки при делении на 2. Должна получиться красивая картинка, вроде треугольника Серпинского. Попробуйте проделать тот же трюк с остатками от деления на другие простые числа и визуализировать это как-нибудь на компе. За этим делом сидит одна интересная закономерность, попробуйте найти ее.

Подсказка: чтобы найти биномиальный коэффициент Це из m по n по простому модулю p необходимо каждое из чисел m и n записать в p-ичной системе счисления, взять биномиальные коэффициенты "поциферно" и перемножить их по mod p.

Подсказка к доказательству. Тут явно сидит гомоморфизм Фробениуса.

Интересно, что этот факт про биномиальные коэффициенты по простому модулю играет важную роль в построении порождающих кольца комплексных кобордизмов.

вотэтазадача 29. О раскраске граней простого многогранника в 3 цвета

Вспомнилось давнее.

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

Грани должны быть обычными многоугольниками, без дырок. Отдельно: доказать, что таких выпуклых многогранников не бывает.

Интересующимся: изучить "монодромию" красок при путешествиях по рёбрам.

вотэтазадача 23. Про отношение миноров


Рассмотрим k независимых векторов в n-мерном вещественном пространстве. Выпишем их в kxn-матрицу. Выпишем под этой матрицей еще одну матрицу, составленную из каких-нибудь базисных линейных соотношений на исходные вектора.

Пример: k=2, n=4.

1  1  1  1
1  2  3  4
-------------
1 -1 -1  1
-1 2 -1  0

Выберем максимальный минор (какой-нибудь) верхней матрицы и "дополнительный минор" нижней матрицы. Например

|1  1|  1  1    минор {1,2}
|1  2|  3  4
--------------
1 -1 |-1  1|    минор {3,4}
-1 2 |-1  0|

или

1  |1|  1  |1|    минор {2,4}
1  |2|  3  |4|
--------------
|1 |-1 |-1| 1    минор {1,3}
|-1| 2 |-1| 0

Любопытный факт: модуль отношения верхнего минора к нижнему не зависит от минора.
Интересующимся: ищите по термину "определитель точной последовательности"

вотэтазадача 20. Задача про персидские ковры

Весь пол квадратной залы устлали персидскими коврами. Персидские ковры бывают прямоугольные, круглые, треугольные, в виде правильных шестиугольников и в виде правильных семнадцатиугольников. Посчитали числа a1 - сколько всего ковров, а2 - сколько пар ковров, накладывающихся друг на друга (хотя бы краешком), а3 - сколько троек ковров, покрывающих хотя бы одну общую точку, и т.д. Доказать, что а1 - а2 + а3 - а4 + ... = 1. 

Интересующимся: либо рассмотреть эйлерову характеристику как меру, либо заботать нервы покрытий в смысле П.С.Александрова.