Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Положительно определенная форма
Ассоциативные алгебры
kukina_eg
Задача снова из пробного варианта ШАД Яндекс.

Задача. Есть неизвестная нам квадратичная форма Q(v) в n-мерном пространстве. Разрешается задавать вопрос вида "Чему равно Q(v)?" Какое наименьшее количество вопросов надо задать, чтобы определить, является ли форма Q положительно определенной?
Решение.Collapse )

Подсчеты перестановок
Ассоциативные алгебры
kukina_eg
Задача снова из пробного вступительного экзамена в ШАД Яндекса.

Задача. Рассмотрим случайную перестановку на n элементах. Докажите, что данные k элементов окажутся в одном цикле с вероятностью 1/k.
Решение.Collapse )

Знаменитости
Ассоциативные алгебры
kukina_eg
На этот раз задача из пробного варианта вступительного экзамена в Школу Анализа Данных Яндекс. Вариант можно посмотреть тут.

Задача. В компании из n человек каждый может знать или не знать другого (если А знает Б, то Б не обязательно знает А). Все знакомства заданы булевой матрицей nxn. В этом множестве может найтись или не найтись знаменитость: человек, который не знает никого, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что знаменитости нет. Сложность по времени О(n), сложность по памяти O(1).
решениеCollapse )

Размена нет!
Ассоциативные алгебры
kukina_eg
Задача. У Миши в кармане много 3-рублевых и много 5-рублевых монет. Какие суммы Миша не может набрать без сдачи?
решениеCollapse )
Теперь задачу обобщим.
Задача. У Миши в кармане много n-рублевых и много m-рублевых монет. Сколько есть сумм, которые Миша не может набрать без сдачи? Числа n и m взаимнопростые.
решениеCollapse )

Неприводимость
Ассоциативные алгебры
kukina_eg

В поле комплексных чисел неприводимы только линейные многочлены.

В поле действительных тоже все просто: неприводимы все линейные и квадратные с отрицательным дискриминантом.

В поле рациональных чисел все гораздо труднее, но зато есть хотя бы критерий Эйзенштейна.

А вот в поле вычетов Zp все еще труднее, общих теорем довольно мало.

задача. Доказать, что многочлен xp-x+a неприводим в Zp для любого ненулевого a.
решениеCollapse )


Фокусы с бесконечностью
Ассоциативные алгебры
kukina_eg
Задача. Полицейский участок расположен на прямой дороге, бесконечной в обе стороны. Некто угнал старую полицейскую машину, максимальная скорость которой составляет 90% от максимальной скорости новой машины. В некоторый момент в участке спохватились и послали вдогонку полицейского на новой полицейской машине. Однако вот беда: полицейский не знал, ни когда машина была угнана, ни в каком направлении вдоль дороги уехал угонщик. Сможет ли полицейский поймать угонщика?

Забавная задача, положительный ответ в которой возникает благодаря бесконечности дороги. Если бы дорога была конечна, то угонщик с существенной вероятностью успел бы доехать до пункта назначения. А поскольку угонщик обречен бесконечно ехать по дороге, полицейский в конце-концов его изловит.
решениеCollapse )

Боксеры
Ассоциативные алгебры
kukina_eg

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

Задача. 55 боксеров участвовали в турнире по системе "проигравший выбывает". Бои шли последовательно. Известно, что у участников каждого боя число предыдущих побед отличалось не более, чем на 1. Какое наибольшее число боев мог провести победитель турнира?
решениеCollapse )


Странные биномиальные суммы
Ассоциативные алгебры
kukina_eg

А следующая задача скорее из разряда математических фокусов, хоть и довольно стандартных.

Задача. Вычислить сумму 1+C3n+C6n+C9n...
решениеCollapse )


Интергалы
Ассоциативные алгебры
kukina_eg

Позавчера попросили студенты решить задачку по математическому анализу. Решила, куда деваться.

Задача. f(x) -- произвольная функция, непрерывная на [0,1]. Доказать, что

Решение.Collapse )


1972 год
Ассоциативные алгебры
kukina_eg

Многие интересуются, а что было до ЕГЭ? Почему наши учителя (особенно те, что постарше) так сетуют и негодуюут по поводу ЕГЭ? Спрашивали -- отвечаем. До ЕГЭ были письменные экзамены. Да-да, примерно все то же самое, что и в части С.
Ну, например, вступительные на мехмат МГУ 1972 года, задача номер последняя:

Даны три уравнения с действительными коэффициентами.
1) x2-(a+b)x+8=0;
2) x2-b(b+1)x+c=0;
3) x4-b(b+1)x2+c=0.
Каждое из них имеет по крайней мере один действительный корень. Известно, что корни первого уравнения больше единицы. Известно также, что все корни первого уравнения являются корнями третьего уравнения и хотя бы один корень первого уравнения удовлетворяет второму уравнению. Найти числа a,b,c, если известно, что b>3.

решениеCollapse )


?

Log in

No account? Create an account