Блоха запрыгнула на круглый стол для игры в "Что? Где? Когда?" незадолго до начала очередной игры. На секторах стола уже были разложены конверты с вопросами. Блоха решила заранее прочитать все вопросы, чтобы у нее было больше времени подумать над ответами.

Круглый игровой стол поделен на 10⁹ секторов, занумерованных по часовой стрелке числами от 1 до 10⁹. Блоха запрыгнула на первый сектор. С него она может либо перебежать на соседний, либо перепрыгнуть через 2 сектора (например, если стол делится на 12 секторов, то с сектора номер 1 блоха может за одно действие попасть на сектора с номерами 2, 4, 10 и 12). Блоха хочет побывать на каждом секторе ровно 1 раз и вернуться обратно на первый сектор, откуда она спрыгнет и убежит думать над вопросами. Определите, сколькими способами она сможет совершить свое путешествие. Выведите в качестве ответа количество способов по модулю 10⁹+9.

Для передачи сообщений используется алфавит из 32 прописных русских букв (не используется «Ъ»). Все передаваемые слова содержат ровно по 8 букв. Каждое передаваемое слово начинается с одной из четырех букв (К, Л, М, Н). Остальные буквы в каждом слове могут быть любыми из используемого алфавита. Какое количество информации (в битах) несет произвольная фраза из 10 слов, если для ее кодирования использовалось минимальное количество бит в рамках описанных выше правил.

Игроку выдается 9 карт и он упорядочивает их по мастям в порядке Пики, Трефы, Бубны, Червы, а внутри масти по старшиству 2, 3,..., 10, В, Д, К, Т. Комбинация называется неубывающей, если младшая карта в следующей масти, не ниже старшей карт в предыдущей масти. Найдите количество неубывающих комбинаций из 9 карт.

Сколько существует различных расстановок 8 ферзей на шахматной доске, таких, что никакие 2 ферзя не бьют друг друга?

Сколько существует различных расстановок 8 ферзей на шахматной доске, таких, что ровно 2 ферзя бьют друг друга?

Матрица размером 100 на 100 элементов заполняется таким образом: в позиции с координатами (i,j) размещается цифра, находящаяся на i*j месте после запятой в записи числа π, если эта цифра четная, то она записывается с положительным знаком, если нет - с отрицательным.

Рассмотрим "внутренние" матрицы 10 на 10, состоящие из элементов:

a_m,n, a_m+1,n,...,a_m+9,n,
a_m,n+1, a_m+1,n+1,...,a_m+9,n+1,
...
a_m,n+9, a_m+1,n+9,...,a_m+9,n+9.

Суммой матрицы назовем сумму ее элементов. Найдите максимальное значение суммы среди всех "внутренних" матриц.

Правильный треугольник со стороной 8 можно разбить на 64 одинаковых правильных треугольника, как показано на рисунке:

Раскрасим теперь то, что получилось, в три цвета: красный, синий и зеленый. Будем считать допустимой такую раскраску, при которых никакие два соседних (имеющих общую сторону) единичных треугольника раскрашены в разные цвета. Треугольники, имеющие общую вершину, но не имеющие общей стороны, не считаются соседними.
Вот пример допустимой раскраски для треугольника со стороной 8:

Обозначим через f(n) число различных допустимых раскрасок для треугольника со стороной n.
Если для получения одной раскраски из другой необходимы преобразования симметрии или повороты, мы будем считать такие раскраски различными.
Тогда f(1)=3, f(2)=24, f(3)=528.
∑f(n)=555 для 1 ≤ n ≤ 3.
Найдите ∑ f(n) для 1 ≤ n ≤ 8.

Рассмотрим граф, составленный из блоков A и B, показанных на рисунке:

Блоки соединяются вдоль вертикальных ребер в различном порядке, например, вот так:

Вершины графа будем раскрашивать, используя не более c цветов таким образом, чтобы связанные ребром вершины были окрашены в разные цвета.

Теперь подсчитаем, сколько разноцветных графов можно составить, используя a блоков A, b блоков B и не более c цветов.
Используя один блок A и три цвета, можно получить 24 различных графа. (a=1, b=0, c=3)
Используя два блока B и четыре цвета, можно получить 92928 различных графа. (a=0, b=2, c=4)
Используя два блока A, два блока B и три цвета, можно получить 20736 различных графа. (a=2, b=2, c=3)
А сколько различных графов можно получить, используя не более c=2011 цветов и 100 блоков A или B (a+b=100), так, чтобы a и b были четными числами?
В качестве ответа укажите 8 последних цифр результата.

Оля и Дима играют в кости.
У Оли шесть костей в форме октаэдра, и грани каждой из них занумерованы числами от 1 до 8.
У Димы четыре кости в форме додекаэдра, и грани каждой из них занумерованы числами от 1 до 12.
В каждом туре игроки бросают все свои кости по одному разу. Побеждает тот, у кого сумма выпавших очков больше. При равенстве фиксируется ничья.
Каково математическое ожидание количества побед Оли после миллиона туров?
Результат округлите вниз до целого.

В данной задаче мы будем рассматривать "ориентированные" тетраэдры, координаты вершин которых имеют вид:
{(x, y, z), (x+a, y, z), (x,y+a,z), (x,y,z+a)}, a>0, и x,y,z,a – целые числа. Объем такого тетраэдра равен a³/6.
Если мы захотим найти общий объем объединения нескольких ориентированных тетраэдров, то, возможно, он окажется меньше суммы их объемов, если некоторые из тетраэдров пересекаются.
Построим последовательность ориентированных тетраэдров T₁, T₂, …, T_n,… следующим образом:
x_n = S_4n-3 (mod 10000)
y_n = S_4n-2 (mod 10000)
z_n = S_4n-1 (mod 10000)
a_n = 1+S_4n (mod 699),
а S_k  получены при помощи генератора случайных чисел Фибоначчи с запаздываниями:
При 1≤k≤55, S_k = [100003 - 200003k + 300007k³] (mod 1000000), и при 56≤k, S_k = [S_k-24  + S_k-55 ] (mod 1000000).
(p (mod q) означает остаток от деления p на q.)
Таким образом, у тетраэдра T₁ x =7, y=53, z=183, a=655, у тетраэдра T₂ x =863, y=1497, z=2383, a=112 и т.д.
Объем объединения первых 300 ориентированных тетраэдров T₁ … T₃₀₀ равен 3999927695 (по счастливому совпадению это число оказалось целым).
Найдите объем объединения первых 50000 ориентированных тетраэдров T₁ … T₅₀₀₀₀ (благодаря еще одному счастливому совпадению это число тоже целое).