30 мая 2015 (Минск)

  1. Докажите, что для любого натурального больше пяти лист бумаги квадратной формы можно разрезать на квадратных кусков.
  2. Рассмотрим случайную перестановку натуральных чисел от до . Пару чисел назовем «обменом», если выполняются соотношения . Вычислите математическое ожидание количества обменов в перестановке (перестановка выбирается случайно равновероятно из множества всех перестановок от до ).
  3. Докажите, что для любого неотрицательного целого существуют целые числа , и такие, что выполняется соотношение:
    Решение
    Пусть — наибольшее целое число, для которого . Тогда остаток (здесь мы учли, что ). Пусть — наибольшее целое число, для которого . Тогда и остаток (здесь мы учли, что ). Теперь — наибольшее целое число, для которого . Тогда .
  4. Трудоемкость алгоритма описывается следующим соотношением ( — время решения задачи размерности ): Найдите асимптотически как можно бо́льшую функцию, удовлетворяющую этому соотношению. Ответ представьте в -нотации, докажите, что функция удовлетворяет данному соотношению.
  5. Рассмотрим клетчатую доску размера . Раскрасим клетки доски в шахматном порядке в белый и черный цвета, причем левую верхнюю клетку покрасим в белый цвет. Найдите количество способов вырезать из этой доски содержащий не более черных клеток участок. Резать разрешается только по границам клеток.
    (a) и .
    (b) и .
    (c) Найдите ответ для произвольных натуральных и .
  6. Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Рассмотрим некоторую строку , состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом? Предложите алгоритм решения задачи, докажите его корректность, оцените трудоемкость.
  7. Рассмотрим четыре реализации одной и той же функции на языке программирования python. Определите, что должна вычислять функция. Какие из реализаций работают корректно?
    (a)
    def solve(n, k):
        if n < 0 or k < 0 or k > n: return 0
        if n == 0 or k == 0 or n == k: return 1
        s = 0
        step = k
        if n > 47: step = 10
        for i in range(n + 1):
            s += solve(n - step, i * solve(step, k - i)
        return s
    (b)
    def solve(n, k):
        A = [ 0 for i in range(n+1) ]
        for s in range(16**n)
            tmp = s
            odd = 0
            for t in range(n):
                if tmp % 2: odd += 1
                tmp = tmp // 16
            A[odd] += 1
        return A[k] // 2**(3*n)
    (c)
    def solve(n, k):
        if k == 0 or n == k: return 1
        return solve(n + 1, k) - solve(n, k - 1)
    (d)
    def solve(n, k):
        if k == 0 or n == k: return 1
        return solve(n, k + 1) * (k + 1) // (n - k)

    Замечание. Некоторые разъяснения к синтаксису python.
    range(x) возвращает массив [0,1,...,x-1]
    ** возведение в степень, например, 2**5 == 32
    % взятие остатка от деления, например, 7 % 3 == 1
    // целочисленное деление, например, 7 // 3 == 2