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

1. Докажите, что для любого натурального $n$ больше пяти лист бумаги квадратной формы можно разрезать на $n$ квадратных кусков.
2. Рассмотрим случайную перестановку $P = (p_1,p_2,\ldots,p_n)$ натуральных чисел от $1$ до $n$. Пару чисел $(i,j)$ назовем «обменом», если выполняются соотношения $p_i=j, p_j=i$. Вычислите математическое ожидание количества обменов в перестановке $P$ (перестановка выбирается случайно равновероятно из множества всех перестановок от $1$ до $n$).
3. Докажите, что для любого неотрицательного целого $n$ существуют целые числа $x$, $y$ и $z$ $(0 \leqslant x < y < z)$ такие, что выполняется соотношение: $$n = C_x^1 + C_y^2 + C_z^3.$$
   Решение
   Пусть $z$ — наибольшее целое число, для которого $C_z^3 \leqslant n$. Тогда остаток $r = n - C_z^3 < C_{z+1}^3 - C_z^3 = C_z^2$ (здесь мы учли, что $z \geqslant 2$). Пусть $y$ — наибольшее целое число, для которого $C_y^2 \leqslant r$. Тогда $y < z$ и остаток $\tau = r - C_y^2 < C_{y+1}^2 - C_y^2 = C_y^1$ (здесь мы учли, что $y \geqslant 1$). Теперь $x$ — наибольшее целое число, для которого $C_x^1 \leqslant \tau$. Тогда $0 \leqslant x < y$.
4. Трудоемкость алгоритма $A$ описывается следующим соотношением ($T(n)$ — время решения задачи размерности $n$): $$T(n) \leqslant T(\lfloor \sqrt{n} \rfloor ) + 1,\;\;\; T(1) = C_1 (\textrm{const}).$$ Найдите асимптотически как можно бо́льшую функцию, удовлетворяющую этому соотношению. Ответ представьте в $O$-нотации, докажите, что функция удовлетворяет данному соотношению.
5. Рассмотрим клетчатую доску размера $N\times M$. Раскрасим клетки доски в шахматном порядке в белый и черный цвета, причем левую верхнюю клетку покрасим в белый цвет. Найдите количество способов вырезать из этой доски содержащий не более $4$ черных клеток участок. Резать разрешается только по границам клеток.
   (a) $N=8$ и $M=8$.
   (b) $N=99$ и $M=101$.
   (c) Найдите ответ для произвольных натуральных $N$ и $M$.
6. Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Рассмотрим некоторую строку $S$, состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом? Предложите алгоритм решения задачи, докажите его корректность, оцените трудоемкость.
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