Доказать что элементы ab и ba имеют одинаковый порядок

Задачи вступительного экзамена в ШАД 2014

При поступлении в ШАД проверяются знания в рамках общей программы, включающей базовые разделы высшей алгебры, математического анализа, комбинаторики, теории вероятностей, а также основы программирования. Под катом подробно разобраны задачи вступительного экзамена в ШАД 2014 года. Внимание! Пост довольно объёмный, поэтому устраивайтесь поудобнее, вооружайтесь карандашом, если нужно, доставайте чай с печеньем. Убедитесь, что сделали все дела на вечер! Велика вероятность, что рассматриваемые ниже задачи поглотят ваш разум на несколько часов, а кому-то помешают вовремя лечь спать. Во всяком случае сегодняшний вечер обещает быть интересным. Добро пожаловать под кат ↓

Задача 1

Найдите все квадратные вещественные матрицы порядка 3, удовлетворяющие уравнению X 2 + E = 0.

Так как характеристический многочлен матрицы X представляет собой полином (нечетной) степени 3, то он имеет по крайней мере один действительный корень и, следовательно, матрица X имеет по крайней мере одно вещественное собственное значение λ. Тогда есть ненулевой вектор v такой, что выполняется равенство:
X⋅v = λ⋅v.
Тогда, X 2 + E = 0 означает, что (X 2 + E)⋅v = 0, или X 2 ⋅v + E⋅v = 0, но
X 2 ⋅v = X⋅(X⋅v) = X⋅(λ⋅v) = λ⋅X⋅v = λ 2 ⋅v
таким образом:
(X 2 + E)⋅v = (λ 2 + 1)⋅v = 0.
Так как v – ненулевой вектор, то для выполнения равенства необходимо, чтобы λ 2 + 1 = 0, что возможно только при комплексном значении λ. Следовательно, вещественной матрицы X размерности 3×3 такой, что выполняется уравнение X 2 + E = 0 не существует.

2 способ решения
Обобщим задачу. Рассмотрим матрицу X размерности n×n. Существует теорема о произведении определителей квадратных матриц, которая формулируется следующим образом: определитель произведения двух квадратных матриц равен произведению определителей сомножителей. Тогда, если выполняется уравнение
X 2 + E = 0, обозначим это уравнение (1),
то справедливо следующее уравнение
det(X 2 ) = det(−E) , обозначим это уравнение (2).
Очевидно, что det(X 2 ) = det(X)⋅det(X) > 0 (т.к. det(X) > 0 или det(X) 2 ) = det(−E) несправедливо). Так как (−E) также является матрицей размерности n×n, то det(−E) = (−1) n . Таким образом, видим, что при четных значениях n уравнение (2) выполняется (существуют вещественные решения), а при нечетных n – не выполняется (существуют только комплексные решения). Следовательно, для нечетных n не будет выполняться и исходное уравнение (1), а значит и для n=3 равенство (1) несправедливо. Получаем тот же вывод, что и в первом способе решения задачи: вещественной матрицы X размерности 3×3 такой, что выполняется уравнение X 2 + E = 0 не существует.

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

Рассмотрим матрицу размерности 2×2, зная что в произведении на саму себя она должна дать (−E):

Из первого и четвертого уравнений получим: (a₁₁) 2 = (a₂₂) 2 , обозначим это уравнение *
А из второго и третьего уравнений получим: (a₁₂ + a₂₁)·(a₁₁ + a₂₂) = 0, а это уравнение обозначим **

1 случай
a₁₁ = a₂₂ = a, тогда a₁₁ + a₂₂ ≠ 0. Из этого следует, что для выполнения равенства ** необходимо, чтобы a₁₂ = −a₂₁. Пусть a₁₂ = b. Теперь можем записать произведение матриц:

Равенство для вещественных a и b будет выполняться только при a = 0, b = ±1. Таким образом искомые матрицы будут выглядеть следующим образом:

Можете убедиться, что при умножении каждой из них на саму себя получим (−E).

2 случай
a₁₁ = −a₂₂, тогда уравнение ** также выполняется. Обозначим a₁₁ = a. Запишем произведение матриц:

Необходимо, чтобы выполнялось равенство a 2 + a₁₂·a₂₁ = −1. Выразим из последнего равенства a₂₁ = −(1 + a 2 )/a₁₂. Пусть a₁₂ = b. Тогда искомая матрица будет выглядеть так:

Если из равенства a 2 + a₁₂·a₂₁ = −1 выразить a₁₂ = −(1 + a 2 )/a₂₁ и обозначить a₂₁ = b. Тогда искомая матрица будет выглядеть так:

Также необходимо написать, что a, b ∈ R, b ≠ 0. Также можно легко убедиться, что при умножении каждой из таких матриц на саму себя получим (−E).

Видим, что первый случай, рассмотренный выше, является частным случаем второго (при a = 0, b = 1). Поэтому в общем виде то, как выглядит искомая матрица, описывает именно второй случай.

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

Задача 2

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

Пусть n — число участников похода. Построим граф знакомств G=(V, E), в котором вершины обозначают участников похода, а ребра — их знакомства между собой. Также известно, что любой подграф C=(V_c, E_c), |V_c|=4 графа G имеет как минимум одну вершину v_c, степень которой d(v_c)=3 (из любых четырех как минимум один знаком с тремя другими). Необходимо доказать, что для всех вершин графа G, кроме максимум трех, степень d(v)=n-1 (каждый участник похода, кроме максимум трех, знаком со всеми остальными). Или, иначе говоря, нужно доказать, что граф G имеет полный подграф (клику) D, минимальное возможное число вершин |V_d| для которого равно n-3.

В известной задаче о клике ставится вопрос о том существует ли в графе G клика заданного размера (вариант задачи распознавания) или каков максимальный размер клики в графе (вычислительный вариант задачи). Задача относится к классу NP-полных в области теории графов и, строго говоря, не имеет эффективного алгоритма решения.

Здесь же у нас есть замечательное условие (1*), которое все сильно упрощает, поэтому для решения задачи необходимо построить все возможные удовлетворяющие (1*) графы (см. далее 1,2,3) и определить в них размер максимальной клики. Сделать это можно довольно быстро:

1. Если незнакомых между собой людей нет, иначе говоря, если граф знакомств G полный, то количество людей знакомых со всеми остальными равно n (максимальная клика имеет размер n).

2. Пусть некоторые две вершины графа G a,b є V несмежны, т.е. a,b незнакомы между собой. Пусть в графе G также существует еще одна пара несмежных вершин c,d є V. Тогда не выполняется условие, что в группе из любых четырех человек (например a,b,c,d) как минимум один должен быть знакомым с остальными тремя (1*). Следовательно, еще одной пары незнакомых между собой людей c,d при наличии пары a,b быть не может. Поэтому, если a,b незнакомы друг с другом, то все остальные люди (n-2 человек) знакомы между собой, подграф D имеет |V_d|=n-2 вершин (обведен синей линией на рисунке). Соответственно, если a,b знакомы со всеми остальными, то n-2 человек знакомы со всеми (вершины, соответствующие людям знакомым со всеми, раскрашены зеленым цветом) (максимальная клика имеет размер n-2):

3. Если a незнаком также и с с, то так как в любой группе (например a,b,c,d) только d может быть знаком с остальными тремя (ввиду того, что a незнаком с b,c), a,b,c знакомы со всеми остальными n-3 людьми, которые к тому же знакомы между собой. Таким образом, минимальное число людей знакомых со всеми n-3 (максимальная клика имеет размер n-3) ч.т.д.:

Ниже рассмотрим простой пример для пяти участников похода. Соответственно, есть пять вариантов выбора любых четырех из них (число сочетаний из 5 по 4). В графе G a незнаком с b и c. Трое участников незнакомы со всеми остальными. Это максимум при заданном условии (1*), которое выполняется в каждом подграфе.

Задача 3

Опишите все невырожденные вещественные матрицы A, для которых все элементы матриц A и A −1 неотрицательны.

Рассмотрим матрицы A и B размерности 2×2. Пусть B = A −1 – обратная матрица. Тогда, результатом произведения матриц A и B будет единичная матрица E:

Рассмотрим выражения (2) и (3). Когда они обратятся в ноль при условии неотрицательности элементов? Т.к. элементы матриц A и B должны быть неотрицательны, то выполнение тождеств (2) и (3) будет осуществляться т. и т.т, когда оба слагаемых в каждом выражении будут нулевыми. Рассмотрим возможные варианты. Сразу отбросим варианты, при которых «занулятся» элементы одной строки матрицы A или столбца матрицы B, т.к. в этом случае не будет соблюдено условие невырожденности матриц. Варианты, при которых результатом произведения будет нулевая матрица также отбрасываем (a₁₁=a₂₂=b₂₁=b₁₂=0, a₂₁=a₁₂=b₁₁=b₂₂=0).

Остаётся два варианта: a₁₂ = a₂₁ = b₁₂ = b₂₁ = 0 и a₁₁ = a₂₂ = b₁₁ = b₂₂ = 0. Тогда, очевидно, чтобы выполнялись равенства (1) и (4) и результатом произведения AB была единичная матрица, возможны два варианта:

Рассмотрим матрицы A и B размерности 3×3:

Рассмотрим выражения, которые должны обратиться в ноль, и проанализируем в каких случаях это происходит. Сразу же отбросим варианты равенства выражений нулю, при которых «занулятся» элементы одной строки (столбца) матрицы A (матрицы B). И т.д. по аналогии, отбросив все варианты, при которых в результате произведения AB получим нулевую матрицу. Останутся случаи, в которых ненулевые элементы в матрицах A и B окажутся на позициях, показанных красным:

При перемножении матриц именно такого вида, как показано выше, возьмём например вариант:

будем получать единичную матрицу.

Т.о. можно видеть, что искомая невырожденная матрица A, состоящая из неотрицательных элементов, будет иметь обратную матрицу B из неотрицательных элементов в том случае, если в каждой строке и столбце матрицы A будет по одному ненулевому элементу, а остальные элементы строки и столбца будут нулевыми. Такое описание матрицы напоминает нам матрицу перестановок, только вместо единичных элементов в ней могут быть любые ненулевые значения. Такие матрицы называют мономиальными или обобщёнными матрицами перестановок (почитать про них можно на википедии).

Существует теорема: пусть A – неотрицательная матрица. В таком случае матрица A будет иметь неотрицательную обратную матрицу тогда и только тогда, когда A – обобщённая матрица перестановок.

Зная такую теорему заранее, задачу можно решить быстрее:)

Задача 4

Дан числовой массив длины n. Предложите алгоритм, находящий максимальное значение сумм отрезков этого массива. Ограничение по времени — O(n), по дополнительной памяти — O(1).

Рассмотрим массив a[] из n элементов
a₀, a₁, a₂,… a_n-1
Будем идти по массиву и накапливать в некоторой переменной sum текущую частичную сумму. Если в какой-то момент sum окажется отрицательной, то мы просто присвоим sum = 0. Максимум из всех значений переменной sum, случившихся за время работы, и будет ответом на задачу.

Этот алгоритм называется Алгоритмом Кадана (Подробнее о нём можно почитать на википедии и здесь). Время выполнения — требуемые по условию задачи O(n), т.к. мы осуществляем один проход по массиву a[] из n элементов. Условие по дополнительной памяти — O(1) также соблюдены.

Примеры работы программы:

Задача 5

Есть 10 монет разного веса и некоторые весы. При помощи одного взвешивания на весах можно узнать для выбранных двух монет, какая тяжелее. Можно ли за 20 взвешиваний узнать, в каком порядке монеты идут по весу?

Осуществим замену переменной в каждом из интегралов. В первом интеграле:

Во втором интеграле:

Таким образом, сумму интегралов можно записать в виде:

Возьмем второй интеграл в сумме выше по частям:

Избавляемся от противоположных друг другу слагаемых и подставляем значения пределов интегрирования в оставшееся слагаемое, получаем:

2 способ решения, предложенный пользователем p53

Видно же, что функции под интегралами и пределы интегрирования выбраны не случайно, а именно:

А значит, сумма интегралов равна сумме площадей криволинейных трапеций, которую можно представить как разность площадей двух прямоугольников:

Задача 7

Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. Когда игрок выигрывает, он получает 1 доллар, а когда проигрывает — платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и удаляется из казино. Найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала k.

В нашем случае игрок A — это мы со стартовым капиталом k, игрок B — казино. Будем считать, что игрок удаляется из казино, когда выиграл у него все деньги (разорил его), т.е. N это сумма всех денег что были у игрока и у казино до начала игры. Тогда стартовый капитал игрока B (казино) составляет N–k. Таким образом, нам нужно найти вероятность P_b (того, что казино выиграет все деньги у игрока):
P_b = (1–(p/q) N–k )/(1–(p/q) N )

Решение простое и быстрое в том случае, если при взгляде на задачу №7 вы сразу говорите: «Да это же о разорении игрока, классика!» Если же нет, и вы хотите узнать почему формулы именно такие, то жмите на спойлер ниже.

Замечание: для игрока A обозначение стартового капитала i, потому что количество долларов это integer(целое) число. У игрока B стартовый капитал N−i, чтобы удобно было говорить, что мы ищем вероятность того, что у A станет N−i+i=N долларов (A выиграет у соперника).

При достаточно больших N можно рассматривать выражение выше, как разностное уравнение, а p_i искать как его решение. Из разностного уравнения формальной заменой p_i = x i получаем алгебраическое уравнение:

Дискриминант квадратного уравнения 1−4pq > 0 при p ≠ q. Найдём корни квадратного уравнения:

Так как дискриминант квадратного уравнения больше нуля, то решение разностного уравнения ищется в виде:

Тогда:

Подставив C₁ и C₂ в выражение для p_i, получаем:

Чтобы получить выражение для p_i при p = q, обозначим x = q/p, т.к. p = q, то x → 1. Найдём предел:

Таким образом, мы нашли формулу для вычисления вероятности того, что игрок A выиграет все деньги (N), в зависимости от его стартового капитала i.

Задача 8

Пусть a — действительное число. Для любого целого n ≥ 0 обозначим через a_n — расстояние от a до ближайшего рационального числа вида m/2 n , где m — целое. Найти наибольшую возможную сумму ряда:

Расстояние a_n от действительного числа a є R до ближайшего рационального числа вида m/2 n , где m,n є Z можно легко свести к функции вида «расстояние до ближайшего целого» S(x), x є R:

Очевидно, что значения этой функции лежат в пределах от 0 до 1/2, кроме того она является периодической. Для тех кто не успел прикинуть это в уме, вот ссылка на wolfram alpha.
Вследствие периодичности функции, для поиска максимума нам достаточно рассматривать ее на одном периоде, а именно на интервале [0,1], вместо того чтобы делать это на всей числовой оси. Неплохая оптимизация для начала)

Итак, запишем выражение для a_n, приведем слагаемые внутри модуля к общему знаменателю и вынесем 1/2 n , значение a_n при этом не изменится:

Таким образом, исходя из определения функции S(x), получаем новое выражение для a_n:

«Можно заметить», что искомый ряд представляет собой, как «очевидно» каждому читающему этот пост, функцию Бланманже (Такаги), похожую на одноименный десерт:

Функция (кривая) Бланманже, наряду с общеизвестной функцией Вейерштрасса, является непрерывной, но нигде не дифференцируемой функцией. Конечно, если решающий задачу знаком с ней, то он сразу может гордо писать, что это функция Бланманже и для неё, согласно теореме Кахане (3.1), максимальное значение составляет 2/3. И это готовый ответ! Беда в том, что на экзамене хоть и разрешается пользоваться печатными справочниками, информации по упомянутой функции там может попросту не оказаться. Поэтому продолжим поиски «адекватного» решения.

Итак, нам необходимо найти максимально возможную сумму ряда:

Для наглядности, приведем здесь график функции S(x):

Выделим в нем n-частичные суммы (фигурные скобки на рисунке выше), каждая из которых соответствует количеству итераций при построении кривой Такаги и задается выражением:

Распишем все частичные суммы и обратим внимание на суммы с четными номерами:

Обозначим T₂(x) как S₁(x) (это т.н. функция-«столешница») и заметим что для четных частичных сумм справедливо выражение:

Ну а дальше нам на помощь приходит математическая индукция. Кахане в своем доказательстве провел аналогичные рассуждения, рассматривая четные частичные суммы, построил первые две из них T₂(x) и T₄(x) и по индукции пришел к выводу, что максимальное значение для T_2n(x) равно:

Тогда максимальная сумма ряда M вычисляется как сумма ряда бесконечно убывающей геометрической прогрессии:

Ну и, собственно, сами графики для первых 6-ти итераций:

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

Как вариант, можно применить индукцию пораньше, обратив внимание на функцию-«столешницу» S₁(x). Рассмотрим опять же частичные суммы T₂(x) и T₄(x), и построим графики для S₁(x) и S₁(4x):

Ну и максимальная сумма ряда M:

Этот способ незначительно отличается от предыдущего, но объем построений в нем явно поменьше.

Можно решить задачу еще быстрее, применив индукцию еще раньше. Итак, вновь распишем сумму ряда:

Видим, что все эти функции с дальнейшим увеличением частоты в 2 раза, всегда будут пересекаться в одной точке с аргуметом x=1/3 (значения функций при этом совпадут и будут равны 1/3), следовательно искомая сумма ряда будет принимать максимальное значение именно в этой точке:

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

Источник