7 июня 2015

  1. Постройте график функции
    Решение
    Рассмотрим несколько случаев:
    1) . Тогда и стремятся к нулю при и, следовательно, 2) . Тогда и мы имеем 3) . Тогда и мы имеем Получается следующий график (правый участок графика представляет собою часть параболы):
    Ответ
  2. Найдите собственные значения матрицы , где — некоторый вектор-столбец.
    Решение
    Пусть — стандартное евклидово скалярное произведение Заметим, что . Пространство , на котором действует наш линейный оператор, раскладывается в прямую сумму . Нетрудно видеть, что оба слагаемых являются собственными подпространствами для с собственными значениями и соответственно:
    Ответ
    и .
  3. Найдите математическое ожидание числа неподвижных точек подстановки на элементах.
    Решение
    Рассмотрим индикаторные случайные величины: Тогда число неподвижных точек подстановки равно сумме .
    Найдем математическое ожидание каждого из слагаемых: В самом деле, элемент фиксирует перестановок.
    Теперь воспользуемся линейностью матожидания:
    Ответ
    .
  4. Пусть и — квадратные матрицы одинакового размера, причем для некоторых . Докажите, что матрицы и коммутируют.
    Решение
    Преобразуем наше равенство: Поскольку , сомножители левой части обратимы, и мы можем сопрячь обе части, к примеру, матрицей : Раскрывая скобки в левой части, получаем что и требовалось доказать.
  5. Электрическая цепь представляет собой связный неориентированный граф без кратных ребер, в котором ребра (числом ) — это провода, а вершины — либо лампочки, либо единственный источник тока. На каждом ребре размещено реле. Лампочка горит, если существует путь, соединяющий ее с источником тока, вдоль которого все реле находятся в положении «включено». Известно, что ровно одно из реле бракованное и никогда не пропускает ток. Вы можете включать и отключать реле (и видите, горят ли лампочки). Изначально все выключатели находятся в положении «включено». Опишите способ нахождения неисправного реле за операций включения-выключения.
    Решение
    Это тот редкий случай, когда решение проще записать в виде псевдокода.

    FindBug(Node* root):
        Если граф — дерево, то бракованное реле находится перед
        первой (от корня) не горящей лампочкой.
        Если такого нет, отключаем все ребра графа. Return.
        Отключаем все ребра, выходящие из root.
        for (ребра j, выходящие из корня):
            Включаем j
            Его другой конец обозначим через new_root.
            FindBug(new_root). Если успешно — return.
            Выключаем j.

    Важное замечание. После выхода из FindBug все ребра в обработанном подграфе оказываются отключены и не мешают в дальнейшем.

    Оценим время работы алгоритма. Пусть — максимальная сложность FindBug для графа с ребрами. Пусть, далее, — все ребра, выходящие из источника. В худшем случае нам пришлось включить и выключить каждое из ребер и запустить процедуру FindBug для каждого из них.
    Тогда где
    Нетрудно видеть, что , . В любом случае, при .
    Примем это за рабочую гипотезу. По индукции тогда можно заключить, что что и требовалось доказать.
  6. Пусть — дифференцируемая функция, причем и . Докажите, что для всех имеет место неравенство
    Решение
    Мы будем активно пользоваться следующим правилом: Пусть , . Отметим, что .
    Продифференцируем обе функции: Снова видим, что и снова дифференцируем: Здесь уже можно немножко облегчить себе жизнь, заметив, что . Значит, нам достаточно сравнить и , а поскольку , то и просто и .
    Заметим, что в нуле и то, и другое, равно , и продифференцируем:
  7. Для произвольных положительных и вычислите сумму
    Решение
    Немного преобразуем выражение: Знаменатель можно проинтерпретировать как количество последовательностей из и длины . Пусть — множество последовательностей, в которых хотя бы единица, а — множество последовательностей, в которых хотя бы ноль. Ясно, что , а — множество всех последовательностей.
    Найдём мощность множества . Пусть -я единица стоит на месте с номером , где . Тогда первые членов последовательности полностью определяются выбором позиций, на которых стоят единицы (это можно сделать способами), а последние могут быть любыми, то есть их можно выбрать способами. Таким образом, число последовательностей, содержащих хотя бы единицу, равно .
    Аналогично число последовательностей, содержащих хотя бы ноль, равно . А поскольку каждая последовательность принадлежит к одному и только одному из этих видов, то мы делаем вывод, что Таким образом,
    Ответ
    .
  8. На сфере случайным образом выбираются четыре точки ,, и . С какой вероятностью кратчайшие дуги и пересекаются?
    Решение
    Проведем через точки и экватор. Тогда, очевидно, для выполнения условия задачи необходимо, чтобы точки и относительно этого экватора лежали в разных полусферах. Вероятность такого события равна . Пусть теперь точка — точка пересечения этого экватора и кратчайшей дуги, соединяющей точки и . Ясно, что ее вероятность равномерно распределена по экватору. Таким образом, задача свелась к нахождению вероятности того, что случайная точка на окружности (экваторе), попадет в случайную дугу : Тогда полная вероятность равна:
    Решение 2
    Рассмотрим случайную четвёрку точек , , и . Прежде всего надо заметить, что ситуации, когда три и более точек лежат на одной большой окружности (в частности, если какие-то две из них диаметрально противоположны), имеют место c вероятностью ноль и потому не заслуживают рассмотрения. Далее, рассмотрим точки , , и , диаметрально противоположные исходным. Имеются четвёрок точек , , , , из которых лишь нам подходят (это легко увидеть, если предположить, что исходные точки лежат в одной полусфере). Понятно, что появление случайных точек , , и можно представить, как появление восьми точек, включая диаметрально противоположные, а затем реализацию одной из четверок. Поскольку только нам подходят, вероятность равна .
    Ответ
    .