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

kukina_eg


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


Десятиугольный крокодил
Ассоциативные алгебры
kukina_eg
Задача из весеннего-базового тура Турнира Городов 2017 для младших.
Т.е. задача не сложная, но мне показалась очень интересной и красивой.

На каждой стороне 10-угольника (не обязательно выпуклого) как на диаметре построили окружность. Может ли оказаться, что все эти окружности имеют общую точку, не совпадающую ни с одной вершиной 10-угольника?

Решить ту же задачу для 11-угольника.
решениеCollapse )

Не алгебра
Ассоциативные алгебры
kukina_eg
Следующая задача на первый взгляд чисто алгебраическая. Но только на первый!
Алгебраического решения этой задачи лично я не знаю.

Задача. Пусть р(х) -- многочлен с вещественными коэффициентами. Доказать, что многочлен xp(x)-p'(x) имеет хотя бы один действительный корень.
решениеCollapse )

Смерть изменникам
Ассоциативные алгебры
kukina_eg
В жж математического факультета недавно была задача.
Задача известная и не новая, что не делает ее менее интересной и даже немного парадоксальной.

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

И тут вдруг королева делает объявление:
— В нашем королевстве были зафиксированы случаи измен. Приказываю каждой женщине, как только она узнает о том, что ее муж ей не верен, в ближайшую же ночь его пристрелить.

Вопрос: сколько осталось жить мерзавцам?
решениеCollapse )

Диофантово уравнение
Ассоциативные алгебры
kukina_eg
Задача С6 одного из вариантов ЕГЭ прошлых лет.
Решить в натуральных числах уравнение 3n+4m=5k.
решениеCollapse )

Функциональное уравнение
Ассоциативные алгебры
kukina_eg
Задача. Найти все многочлены такие, что xf(x-2)=(x-2)f(x-1).
решениеCollapse )

Рассмотрим очень похожую с виду задачу:
Задача. Найти все многочлены такие, что (x-3)f(x-1)=(x-2)f(x).
Оказывается, что при похожести "с виду", эта задача гораздо сложнее.
решениеCollapse )

Задачи про алгоритмы
Ассоциативные алгебры
kukina_eg
Готовила для спецкурса подборку задачек про придумывание алгоритмов и про сложности алгоритмов. Решила сохранить тут, пусть валяются.
Read more...Collapse )
Задачи без решения специально. Некоторые решения встречаются в других постах этого же жж.

Алгоритм Боера-Мура
Ассоциативные алгебры
kukina_eg
Задача сегодня алгоритмическая. Иногда ее предлагают кандидатам для поступления в Яндекс. А я ее недавно разбирала со студентами на спец.курсе.

Задача. На вход подают поток чисел. Каждое число потока можно обрабатывать ровно один раз в связи с ограниченнностью памяти (дополнительной памяти можно использовать О(1)). Про поток заранее известно, что в нем будет n элементов, а один из элементов встретится больше, чем n/2 раз. Предложите алгоритм нахождения этого популярного числа.
РешениеCollapse )

Как выиграть у казино? Да точно так же, как и проиграть.
Ассоциативные алгебры
kukina_eg
В основном блоге написала около-математический пост, а здесь сделаю более расширенную с точки зрения математики версию.

Как с помощью математики строго и правильно доказать 2 прямо противоположных факта?
Никак! ответите вы -- и будете неправы.
Оказывается, для математики нет ничего невозможного.
доказываем 2 противоположных фактаCollapse )

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

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

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

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

?

Log in