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

kukina_eg


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


Знаменитости
Ассоциативные алгебры
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 )


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

В этом году большинство студентов зашли в тупик при решении одной из задач по алгебре на гос.экзамене. Задачи по алгебре традиционно считаются легкими, что только усилило недоумение студентов.

Задача (гос.экзамен ОмГУ им.Ф.М.Достоевского, 2010год)
Вычислить определитель матрицы

Здесь a,b,c -- различные корни многочлена f(x)=x3-13x-18.

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


Наименьшее значение
Ассоциативные алгебры
kukina_eg

Задача (С5 одного из вариантов).
При каких значениях параметра а наименьшее значение функции f(x)=2ax+|x2-6x+5| меньше единицы?

При решении этой задачи никаких хитростей нет, надо просто проделать все предельно аккуратно.
решениеCollapse )


?

Log in