Разбор задач вступительного теста в корпоративную магистратуру JetBrains на базе Университета ИТМО

    Мы уже анонсировали читателям Хабра набор на магистерскую программу «Разработка программного обеспечения / Software Engineering» на базе Университета ИТМО. Первый этап вступительных испытаний на программу — онлайн тест. И для того, чтобы помочь нашим абитуриентам к нему подготовиться, мы решили опубликовать разбор нескольких математических задач из прошлогоднего варианта.


    Задача 1

    Решите в натуральных числах уравнение: $2^n + 1 = k^2$.

    В ответе укажите максимально возможное значение произведения $k$ и $n$.

    Давайте перенесём единицу в правую часть и применим формулу разности квадратов.

    $2^n = k^2-1 = (k-1)(k+1).$


    Степень двойки $2^n$ делится только на степени двойки. Поэтому нас интересуют такие $k$, при которых $(k-1)$ и $(k+1)$ одновременно являются степенями двойки. При $k=3$ получаем значения $2$ и $4$ соответственно. Значений больше быть не может, т.к. расстояние между степенями двойки возрастает. Таким образом, получаем $k = 3$ и $n = 3$. Ответ $k\cdot n = 9$.

    Задача 2

    Чему равен предел последовательности $(1 + \frac{1}{n})^{5n + 4}$?

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

    Выделим замечательный предел:

    $ \left(1 + \frac{1}{n}\right)^{5n + 4} = \left( \left(1 + \frac{1}{n}\right)^n \right)^5 \cdot \left(1 + \frac{1}{n}\right)^4. $


    Предел первого множителя вычисляется по формуле замечательного предела:

    $ \lim_{n\to\infty} \left( \left(1 + \frac{1}{n}\right)^n \right)^5 = e^5. $


    Предел второго множителя очевиден:

    $ \lim_{n\to\infty} \left(1 + \frac{1}{n}\right)^4 = 1. $


    (Если нужно более формальное доказательство, то можно раскрыть скобки и заметить, что при $n\to\infty$ все слагаемые, кроме 1, стремятся к нулю.) Итак, оба предела существуют, следовательно

    $ \lim_{n\to\infty} \left(1 + \frac{1}{n}\right)^{5n + 4} = \lim_{n\to\infty} \left( \left(1 + \frac{1}{n}\right)^n \right)^5 \cdot \lim_{n\to\infty} \left(1 + \frac{1}{n}\right)^4 = e^5 \cdot 1 \approx 148.413. $



    Задача 3

    Упростите сумму:

    $1 - \frac{1}{4} + \frac{1}{3} - \frac{1}{16} + \frac{1}{9} -\frac{1}{64} + \frac{1}{27} - \dots - \frac{1}{4^n} + \frac{1}{3^n} + \dots $


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

    Представим этот знакопеременный ряд как разность двух положительных последовательностей:

    $ \begin{aligned} S_+ &= 1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots \frac{1}{3^n} + \dots\\ S_- &= \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \dots + \frac{1}{4^n} \dots \end{aligned} $


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

    $S_+ = \frac{1}{1 - 1/3} = \frac32, \quad\quad S_- = \frac{1}{4}\cdot\frac{1}{1 - 1/4} = \frac13. $


    Заметим, что $S_+ + S_- = \frac32 + \frac13 < \infty$, т.е. этот ряд является абсолютно сходящимся. Следовательно, мы можем вычислить его сумму, как разность $S_+$ и $S_-$:

    $1 - \frac{1}{4} + \frac{1}{3} - \frac{1}{16} + \frac{1}{9} -\frac{1}{64} + \frac{1}{27} - \dots - \frac{1}{4^n} + \frac{1}{3^n} + \dots = S_+ - S_- = \frac{3}{2} - \frac{1}{3} = \frac{7}{6} \approx 1.166. $



    Задача 4

    Двадцать пять человек выбирают числа, каждый наугад выбирает число от $1$ до $100$ независимо друг от друга. Далее участники объявляют выбранные номера по очереди (и делают это честно). Первый (если такой человек есть), кто объявляет номер, который уже был объявлен, получает приз.

    Какой человек по счету имеет наибольшую вероятность выиграть приз?

    Оценим вероятность того, что $k$-ый человек получает приз: он получает приз в том случае, если предыдущие $k-1$ участников назвали различные числа, а он — одно из предыдущих $k-1$ чисел. Вероятность назвать одно из прозвучавших $k-1$ чисел равна

    $p_k = \frac{k-1}{100}.$


    Для участника с номером $i$ вероятность назвать число, которое ещё не прозвучало, равна

    $q_i = \frac{100 - i + 1}{100}.$


    Тогда искомая вероятность равна:

    $ q_1 \cdot q_2\cdot\dotsb\cdot q_{k-1}\cdot p_k = \frac{100}{100}\cdot\frac{99}{100}\cdot\dotsb\cdot\frac{100- k + 2}{100}\cdot\frac{k-1}{100} = \frac{100!\cdot (k-1)}{(100 -k +1)!\cdot 100^k}. $


    Осталось вычислить это значения для всех $k\in\{1,\dotsb,25\}$ и найти минимум. Это можно сделать небольшим скриптом, табличкой в Excel или через WolframAlpha:
    {0, 0.01, 0.0198, 0.029106, 0.0376438, 0.0451725, 0.0514967, 0.0564747, 0.0600245, 0.0621254, 0.0628157, 0.0621875, 0.0603784, 0.0575607, 0.05393, 0.0496926, 0.0450547, 0.0402113, 0.0353386, 0.0305875, 0.0260799, 0.0219071, 0.0181307, 0.0147848, 0.0118793}

    Отсюда получаем $k = 11$ (максимум достигается на одиннадцатом элементе списка $0.0628157$).

    Задача 5

    Каждый из девяти единичных квадратов $3\times 3$-квадрата случайным образом окрашен в красный или синий цвет с вероятностью $\frac{1}{2}$. Определите вероятность того, что ни один из четырёх квадратов $2\times2$ не является полностью красным.

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

    В квадрате $3\times 3$ есть 4 различный квадрата $2\times 2$. Назовём их $A$, $B$, $C$ и $D$.



    Обозначим этими же буквами события, что в соответствующем квадрате все ячейки окрашены красным. Тогда

    $\Pr[A] = \Pr[B] = \Pr[C] = \Pr[D] = \frac{1}{2^4}.$



    Для начала вычислим вероятность обратного события — вероятность того, что один из квадратов является полностью красным $\Pr[A\cup B\cup C\cup D]$. Для того, чтобы её вычислить, воспользуемся формулой включений-исключений:

    $ \begin{aligned} \Pr[A\cup B\cup C\cup D] &= \Pr[A] + \Pr[B] + \Pr[C] + \Pr[D]\\ &- \Pr[A\cap B] - \Pr[A\cap C] - \Pr[A\cap D] - \Pr[B\cap C] - \Pr[B\cap D] - \Pr[C\cap D]\\ & + \Pr[A\cap B\cap C] + \Pr[A\cap B\cap D] + \Pr[A\cap C\cap D] + \Pr[B\cap C\cap D]\\ &- \Pr[A\cap B\cap C\cap D]\\ &= 4\cdot \frac{1}{2^4} - 4 \cdot \frac{1}{2^6} - 2 \cdot \frac{1}{2^7} + 4 \cdot \frac{1}{2^8} - \frac{1}{2^9}\\ &= \frac{1}{2^2} - \frac{1}{2^4} - \frac{1}{2^6} + \frac{1}{2^6} - \frac{1}{2^9}\\ &= \frac{1}{4} - \frac{1}{16} - \frac{1}{512} = \frac{128 - 32 - 1}{512} = \frac{95}{512}. \end{aligned} $


    Искомая вероятность, что ни один из четырёх квадратов $2\times2$ не является полностью красным, равна

    $1 - \Pr[A\cup B\cup C\cup D] = 1 - \frac{95}{512} = \frac{417}{512}\approx 0.814.$



    Задача 6

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


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

    В нашем случае задача упрощается тем, что верхняя часть фигуры вращения — это половинка шара радиуса 1. Поэтому объём верхней части можно выписать сразу — он равен $2\pi/3$ (объём сферы вычисляется по формуле $4\pi R^3/3$).

    Осталось разобраться с нижней частью, ограниченной параболой $y = 2(x-2)^2$. Объём фигуры вращения можно вычислить, если разбить объём на цилиндры маленькой высоты. Объём цилиндра равен произведению площади основания ($\pi R^2$) на высоту. Соответственно, нам нужно получить зависимость радиуса (роль радиуса играет $x$) от высоты (от $y$).

    $ y = 2(x-2)^2 \implies x = 2 \pm \sqrt{y/2}. $


    На интересует случай $x\le 2$, поэтому $x = 2 - \sqrt{y/2}$. Объём нижней части фигуры можно выразить следующим интегралом:

    $ \begin{aligned} \int\limits_0^2\pi (2 - \sqrt{y/2})^2\, dy &= \pi\int\limits_0^2\left(4 - 4\sqrt{y/2} + y/2\right)dy\\ &=\pi\left.\left(4y - \frac{4}{\sqrt{2}}\cdot \frac{2}{3}\cdot y^{3/2} + \frac{y^2}{2\cdot2}\right)\right\rvert_0^2\\ &=\pi\left(4\cdot 2 - \frac{4\sqrt{2}}{3}\cdot{2^{3/2}} + 1\right) = \pi(9 - 16/3) = 11\pi/3. \end{aligned} $


    Итого, в сумме получаем $2\pi/3 + 11\pi/3 = 13\pi/3\approx 13.613$.

    Заключение


    Надеемся, что этот разбор поможет абитуриентам подготовиться к онлайн- тесту.
    В этом году он состоит из 12 задач, на которые мы выделяем 2 часа. Стоит учесть, что помимо математических, в нём есть и задачи на программирование. Весь процесс поступления и подробности о следующих этапах описаны на сайте магистерской программы. Если у вас остались вопросы, кураторы с радостью ответят на них по почте или в телеграм канале.
    Образовательные проекты JetBrains
    Компания

    Комментарии 14

      0
      В стартовом скрине как-то интересно 2/3 превратилось в 3/2. Ну то есть 3/2 и должно быть везде)
        0
        Да, я исправил — это я ошибся при переписывании.
        +1
        В разборе задачи 5 при раскрытии формулы включений-исключений во второй строчке было вставлено:
        — Pr[A /\ B] 6 раз, вместо
        — Pr[A /\ B] — Pr[A /\ C] — Pr[A /\ D] — Pr[B /\ C] — Pr[B /\ D] — Pr[C /\ D].
          0
          О, спасибо! Я накопипастил, но не исправил.
          0
          Для первой задачи фраза «Значений больше быть не может, т.к. расстояние между степенями двойки возрастает» надо понимать не как«возрастает» а «уменьшается»?
          2^n = (k — 1) * (k + 1) => k — 1 = 2^x; k + 1 = 2^y; n= x + y
          k = 3: x = 1, y = 2;
          k = 5: x = 2, y = log2(6) = 2.584...;
          k = 7: x = 2.584..., y = 3;
          k = 9: x = 3, y = 3.321…
            0
            Нет, всё вроде верно написано. Имелось в виду, что между (k-1) и (k+1) расстояние 2, соответственно, нам нужны две степени двойки на расстоянии 2. Расстояние между 2^2 и 2^3 уже 6. И дальше расстояние между степенями двойки увеличивается, т.е. больших степеней двойки с таким расстоянием нет.
              0
              Путаница с определениями.
              Расстояние между 2^2 и 2^3 уже 6
              — это как понимать?
                0
                Это я считать не умею. Расстояние между 2^2 и 2^3 уже 4.
                  0
                  так 6 или 4?
                    0
                    Расстояние между 4 и 8 равно 8 — 4 = 4, что больше чем 2.
            +1
            В задаче №3 неободимо вначале проверить знакопеременный ряд на абсолютную сходимость, ведь для вычисления его суммы используется перестановка слагаемых, а с условно сходящими рядами такое делать нельзя.
              0
              Да, спасибо, большое. Забыл про это написать. Сейчас добавлю.
              0
              На сайте написано, что онлайн-тест не требует спец. подготовки, но как видно из заданий, они выходят за рамки школьной программы и обычного технического вуза (информ. и физ-матем. не в счет). Есть ли советы по какой литературе (мб задачники ) готовиться к такому типу заданий, вообще успешно подготовиться к онлайн-тесту?
                0
                А можете уточнить, про какие именно задачи идёт речь? Вроде бы первые две задачи решаются школьными методами. Третья — тоже (если забыть про возможность отсутствия предела, но в тесте требуется только ввести ответ). Для задач 4 и 5 достаточно начальных знаний из университетского курсов теории вероятностей и дискретной математики. Задача 6 — задача на интеграл, обычно это на первом курсе проходят.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое