Задачи в ШАД и их решения
Итак, неделю назад я пытался поступить в школу анализа данных Яндекса, и у меня ничего не вышло. Это был второй этап отбора из трёх. В первом предлагалось решить представленные на сайте задачи и отправить анкету, с чем я в общем справился. Второй этап — письменный экзамен в Москве, третий - собеседование среди показавших хорошие результаты на экзамене. Экзамен проходил в здании МФТИ в Климентовском переулке. Всего было где-то около сотни экзаменующихся, так что, с учётом того, что экзамен проходил в три дня (три воскресенья подряд), всего решило попробовать поступить где-то около трёхсот человек. Экзамен состоял из семи задач, вот таких:
- Определим последовательность \({x_n}\) начальным условием \(x_1 = a\), \(x_2 = b\) и рекуррентной формулой \(x_{n+1} = \frac{1}{2}(x_n + x_{n-1})\). Найдите \( \lim\limits_{n \to \infty} x_n \).
- Рассмотрим функцию \( \phi(x)\ =\sum\limits_{k=1}^{\infty} \frac{1}{2^{2[log_2 k]}}x^k \), где квадратные скобки означают целую часть числа. Найдите \( \int\limits_0^1 \phi(x) \phi’(x)dx \).
- Рассмотрим всевозможные непустые множества \({1,…,n}\). В каждом подмножестве перемножим числа, обратные его элементам. Потом сложим полученное \(2^n-1\) число. Найдите полученную сумму.
- Улоф Пальме и Рави Шанкар подбрасывают правильную монетку (вероятность выпадения орла 0.5). Улоф подбрасывает её \(n\) раз, а Рави — \(n+1\). Найдите вероятность того, что у Рави орлов выпало больше, чем у Улофа.
- Дано некоторое множество положительных чисел мощности континуум. Докажите, что из него можно выбрать счётное подмножество с бесконечной суммой.
- Дан массив из \(n\) чисел. Предложите алгоритм, позволяющий за \(O(n)\) операций определить, является ли этот массив перестановкой чисел от 1 до \(n\). Дополнительной памяти не более \(O(1)\).
- Пусть \(A_1, A_2, …, A_n\) — конечные множества и \(a_{ij}=|A_i\cap A_j|\). Докажите, что матрица \( (a_{ij})_{i=1,2..n}^{j=1,2..n} \) неотрицательно определена.
Не решил я правильно, к сожалению, ни одной задачи. Однако для интересующихся (и себе на память выкладываю их решения).
Итак, задача №1. Как легко заметить, если бы не \(\frac{1}{2}\), то это была бы формула чисел Фибоначчи. Вообще же задано линейное рекуррентное отношение с постоянными коэффициентами. Найдём его производящую функцию, то есть формулу общего члена. Для этого составим характеристический многочлен (прямо как по ссылке в википедии). Он будет таким: \(p(t)=t^2-\frac{1}{2}t-\frac{1}{2}\). Найдём его корни: \[ t^2-\frac{1}{2}t-\frac{1}{2} = 0 \]\[ 2t^2-t-1=0 \]\[ D = 1-4\cdot 2 \cdot (-1) = 9\]\[ \sqrt{D} = 3 \]\[ t_1 = \frac{1+3}{4} = 1, t_2 = \frac{1-3}{4} = -\frac{1}{2}. \]
Корни действительны и различны, и формула общего члена выглядит так: \( x_n = k_{1}r_1^n+k_{2}r_2^n \), где \(r_i\) – \(i\)-тый корень уравнения. Зная начальные условия, мы можем найти \(k_1\) и \(k_2\). Для этого подставим в формулу общего члена найденные корни, а \(n\) зададим равным 1 и 2. Итак, \[x_1 = k_1\cdot1^1 + k_2\cdot(-\frac{1}{2})^1 = k_1 - \frac{1}{2}k_2 = a, \] \[ x_2 = k_1 \cdot {1}^2 + k_2\cdot(-\frac{1}{2})^2 = k_1 - \frac{1}{4}k_2 = b. \] Решая эту систему уравнений, получим, что \( k_2 = \frac{4}{3}(b-a), k_1 = a+\frac{1}{2}k_2 = \frac{1}{3}(a+2b) \). Итак, итоговая формула общего члена последовательности равна: \( x_n = \frac{1}{3}(a+2b) + \frac{4}{3}(b-a)(-\frac{1}{2})^n \). Очевидно, что при \(n \to \infty\) второе слагаемое стремится к нулю. Значит, \( \lim\limits_{n \to \infty} x_n \ = \frac{1}{3}(a+2b) \).
Задача №2.
В принципе, довольно просто заметить, что интеграл \( \int \varphi(x)\varphi’(x)dx \) равен \( \frac{\varphi(x)^2}{2} + C \). Можно или вспомнить формулу дифференцирования сложной функции \( (\varphi(x)^2)’ = 2\varphi(x)\varphi(x)’ \), или попробовать проинтегрировать по частям: \( \int udv = uv-\int vdu \), полагая \(u=v=\varphi(x) \), получаем \( \int \varphi(x)\varphi’(x)dx = \int \varphi d\varphi = \varphi\varphi-\int \varphi d\varphi \). Обозначим интеграл за \(\Phi\). Получим \( \Phi = \varphi^2-\Phi \). Отсюда \(\Phi = \frac{\varphi(x)^2}{2} \). Итак, \( \int\limits_0^1 \varphi(x)\varphi’(x)dx = \frac{\varphi(x)^2}{2}|_0^1 = \frac{\varphi(1)^2}{2} \), так как \(\varphi(0)\) очевидно равно \(0\). Осталось найти \(\varphi(1) = \sum\limits_{k=1}^{\infty} \frac{1}{2^{2[log_2 k]}}\). Здесь нужно задуматься о том, чему равно \([log_2 k]\). Это не что иное, как количество значащих разрядов в двоичной записи числа k. Если выписывать натуральные числа по порядку, то \([log_2 k]\) будет иметь вид ряда \(0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, …\). Ряд состоит из натуральных чисел, каждое (обозначим его за \(n\)) из которых повторяется \(2^n\) раз. Так что \(\varphi(1) = \sum\limits_{k=1}^{\infty} \frac{1}{2^{2[log_2 k]}} =\sum\limits_{n=0}^{\infty} \frac{2^n}{2^{2\cdot n}} = \sum\limits_{n=0}^{\infty} \frac{1}{2^n} =2 \), так как получили сумму геометрической прогрессии. Итак, ответ равен \(\frac{\varphi(1)^2}{2} = \frac{4}{2} = 2 \).
Задача №3.
Не знаю, как до этого можно догадаться, но искомое число равно \((1+\frac{1}{1})(1+\frac{1}{2})\cdot…\cdot(1+\frac{1}{n}) - 1. \) Достаточно мысленно представить, как мы раскрываем скобки. На каждой итерации раскрытия скобок мы получаем сумму результата предудущей итерации плюс сумму дробей с очередным числом, участвующим в знаменателях. Однако число \((1+\frac{1}{1})(1+\frac{1}{2})\cdot…\cdot(1+\frac{1}{n}) - 1 = \frac{2}{1}\frac{3}{2}\frac{4}{3}\cdot…\cdot\frac{n+1}{n} - 1 = n+1-1=n. \) Итак, ответ \(n\).
Задача №4.
Будем рассуждать следующим образом. Допустим, Улаф и Рави бросили монету по \(n\) раз каждый. Существует три случая:
- У Улафа больше орлов
- У Рави больше орлов
- Они выбросили одинаковое количество орлов
Очевидно, что эти случаи покрывают все возможности, поэтому сумма их вероятностей равна единице. Кроме того, ясно, что вероятности случаев 1 и 2 равны. Обозначим эту вероятность за \(p\). Тогда вероятность случая 3 равна \(1-2p\). Теперь рассмотрим событие из условия задачи. Очевидно, что после \(n+1\)-го броска стать больше орлов у Рави может в двух несовместимых случаях:
- После \(n\)-ного броска у Рави уже было больше орлов, и бросок не повлиял на соотношение количества орлов
- После \(n\)-ного броска у Рави было столько же орлов, сколько у Улафа, а в \(n+1\)-ом броске выпал орёл.
Вероятность первого случая равна \(p\). Вероятность второго случая равна половине вероятности случая 3, то есть \(\frac{1}{2}\cdot (1-2p)\). Поскольку события 1 и 2 несовместимы, искомая вероятность равна сумме вероятностей случаев 1 и 2, то есть \(p+\frac{1-2p}{2}\ = \frac{1}{2} \).
Итак, ответ: \(\frac{1}{2}\).
К сожалению, решение задачи №5 я недопонял. Начало было таким: для решения нам достаточно найти такое число \(\epsilon\) и такую последовательность, что начиная с некоторого \(n\) \(x_n \ge \epsilon \). А дальше в моих записях идёт такая формула: \( A = \bigcup\limits_{n=1}^{\infty}(\underbrace{A \cap [\frac{1}{n};\infty)}_{счётно}) \).
Задача №6.
В общем-то идея состоит в том, чтобы рассматривать очередное число как индекс массива, а сам массив как подстановку. Единственная сложность в том, что надо отслеживать циклы. Для этого будем менять знак у элементов массива на минус. (Делаем это в массиве, а не в дополнительной памяти, так как дополнительная память ограничена \(O(1)\), а никаких условий сохранения массива в целости и сохранности в условии не стоит.)
В принципе, проще всего продемонстрировать алгоритм программой на питоне:
# -*- coding:utf-8 -*-
def is_permutation(array):
loop_index = index = n = 0
while (n < len(array)):
try:
curr_el = array[loop_index]
except IndexError:
return False
if curr_el > 0:
array[loop_index] = -curr_el
n += 1
loop_index = curr_el-1
else:
index += 1
if index == n == len(array):
return True
try:
if array[index] > 0:
loop_index = index
except IndexError:
return False
return n == len(array)
def test(array, expected):
print 'PASSED' if is_permutation(array) == expected else 'ERROR'
if __name__ == '__main__':
test([1, 3, 2], True)
test([4, 5], False)
test([1, 2, 4, 3], True)
test([1, 2, 0, 3], False)
test([3, 1, 2, 4], True)
Задача №7 вызвала сложности у большинства экзаменующихся. Тут нужно осознать следующее.
Рассмотрим все элементы всех множеств, то есть \(x \in A_1 \cup A_2 \cup … \cup A_n \). Для каждого из элементов можно построить матрицу \( B_x \), где
\[(B_x)_{ij} = \begin{cases} 1 & \textrm{если } x \in A_i \cap A_j \textrm{,} \ 0 & \textrm{иначе} \end{cases}. \]
Матрица \(A\) будет являться суммой всех матриц \(B_x\). В свою очередь каждая из матриц \(B_x\) после перестановки строк и столбцов имеет вид
\( \begin{matrix} 1 & 1 & … & … & 0 \ 1 & 1 & 0 & … & 0 \ …………… \ 0 & 0 & … & 0 & 0 \end{matrix} \), то есть все единицы “сгружаются” в левом верхнем углу в виде квадрата.
Отсюда неким неведомым мне способом следует, что матрица \(A\) неотрицательно определена.
Если кто-то из читателей поможет мне окончательно понять решение задач 5 и 7, я буду ему весьма благодарен -)
