1 июня 2014

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