Рассмотрим граф, составленный из блоков 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 последних цифр результата.

В зале театра 40 нумерованных мест, а продано всего 18 билетов. Сколькими способами можно рассадить зрителей так, чтобы ровно 8 из них сидели на своих местах?

Рассмотрим множество, состоящее из первых n натуральных чисел: {1,2,...,n}.
Обозначим через f(n,k) количество его k-элементных подмножеств, сумма элементов которых нечетна. Например, f(5,3) =4, поскольку множество {1,2,3,4,5} имеет четыре 3-элементных подмножества с нечетной суммой элементов: {1,2,4}, {1,3,5}, {2,3,4} и {2,4,5}.
Когда все три числа n, k и f(n,k) нечетны, будем говорить, что они образуют нечетный триплет, и обозначим через g(m) количество нечетных триплетов [n,k,f(n,k)] с n ≤ m.
Тогда g(10)=5, поскольку существует ровно 5 нечетных триплетов с n ≤ 10, а именно:
[1,1,f(1,1)=1], [5,1,f(5,1)=3], [5,5,f(5,5)=1], [9,1,f(9,1)=5] и[9,9,f(9,9)=1]
Найдите наименьшее m, при котором g(m) > 10¹⁸.

Рассмотрим игру на прямоугольной клетчатой доске. Одна клетка доски не занята, на остальных стоят фишки. Каждым ходом игрок передвигает на свободную клетку одну из соседних (по вертикали или горизонтали) фишек. В начале игры пустая клетка находится в правом нижнем углу, в левом верхнем углу находится красная фишка, а на остальных клетках стоят синие фишки. Цель игры — переместить красную фишку в правый нижний угол за наименьшее количество ходов. На рисунке ниже показана последовательность ходов для доски 2 х 2.

Пусть S(m,n) -минимальное количество ходов, необходимое для перемещения красной фишки в правый нижний угол для доски m х n. Можно проверить, что S(5,4) = 25.

Существует всего 256 различных досок с сторонами m и n, не превышающими 100, для которых S(m,n) является квадратом натурального числа.

Подсчитайте количество досок со сторонами m и n, не превышающими 10¹⁰, для которых S(m,n) является квадратом натурального числа.

Сэм и Макс решили сделать из электронных часов прибор для демонстрации последовательности математических вычислений. Для испытания они запрограммировали его на расчет однозначной суммы цифр натуральных чисел. Напомним, что для вычисления однозначной суммы цифр суммируют все десятичные цифры числа, затем все десятичные цифры результата, и так далее, пока не получится однозначное число.

Когда в прибор передают очередное число, оно отображается индикатором, затем отображаются все промежуточные значения, и, наконец, - результат.

Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа.

Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке.

Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине.

Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии.

Сэм и Макс предложили разные конструкции прибора.

Работа прибора Сэма показана на картинке слева. Когда  этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет

В таблице приведен расчет энергопотребления прибора Сэма для числа 137.

"137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается).

"11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается).

"2":(5) × 2 = 10 переключений ("2" включается и выключается).

Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии.

Прибор Макса (изображен справа) работает по-другому. Он не выключает каждый раз весь индикатор, а выбирает только те отрезки, которые не понадобятся для следующего числа.

Вот, как он будет работать с числом 137:

"137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит)

"11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2").

"2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2").

Итого: 30 переключений.

Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии.

Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих  2×10⁷.

Горизонтальная полоска состоит из 2n + 1 клеток. Средняя клетка оставлена пустой, слева от нее в n клетках стоят красные фишки, а справа – синие. На рисунке показано расположение фишек для случая n = 3.

Фишки могут совершать ходы двух видов: шаги, когда фишка перемещается на соседнюю незанятую клетку, и скачки, когда одна фишка перепрыгивает через другую в следующую непосредственно за нею пустую клетку.

Обозначим через M(n) минимальное количество ходов, необходимое для того, чтобы поменять местами синие и красные фишки, так, чтобы красные фишки оказались справа от центра, а синие – слева.

Легко проверить, что M(3) = 15, а 15 является треугольным числом.

Построим последовательность таких n, для которых M(n) является треугольным числом.

В этой последовательности ровно пять чисел, не превышающих 100, а именно 1, 3, 10, 22 и 63. Их сумма равна 99.

Найдите сумму всех n, не превышающих 10¹⁷, для которых M(n) является треугольным числом.

Обозначим через f(n) количество способов, которыми можно построить башню 3×3×n из блоков 2×1×1.

Блоки можно вращать произвольным образом. При этом башни, отличающиеся поворотом или симметрией, считаются различными.

Например, 

f(2) = 229,

f(4) = 117805,

f(6) = 64647289,

f(63) mod 123456789 = 75292539,

f(66) mod 123456789 = 56150940.

Здесь a mod q означает остаток от деления a на q.

Найдите f(6¹²³⁴⁵) mod 123456789.

Несколько комнат последовательно соединены автоматическими дверями, как показано на рисунке.

Двери открывают с помощью карт доступа. При этом каждую карту можно использовать лишь однажды: когда вы проходите в комнату, двери за вами автоматически закрываются, а карта не возвращается. Аппарат в начале маршрута может выдать вам в любое время любое количество карт без ограничений, однако система слежения не позволяет иметь на руках более трех карт одновременно. При нарушении этого правила срабатывает сигнал тревоги, а все двери запираются навсегда. Поэтому если вы возьмете при входе три карты и пойдете прямо к выходу, то в комнате №3 у вас карт не останется, и вы окажетесь в ней заперты с обеих сторон.

К счастью, в каждой комнате есть сейф, куда можно складывать карты в любом количестве.

Пользуясь этими сейфами, вы сможете достичь выхода. Например, вы можете войти в комнату № 1, использовав одну карту, положить вторую карту в сейф, а с помощью третьей карты вернуться к началу маршрута. Получив там в аппарате еще три карты, вы используете одну, чтобы войти в комнату №1 и взять там из сейфа оставленную карту. Теперь у вас в руках снова будет три карты, и этого достаточно, чтобы открыть три оставшиеся до выхода двери. Итак, вы можете пройти анфиладу из трех комнат, использовав всего 6 карт.

6 комнат можно пройти, используя 123 карты и не имея на руках более 3 карт одновременно.

Пусть C - максимальное количество карт, которые можно иметь при себе.

Пусть R - количество комнат, через которые нужно пройти от входа (“Start”) до выхода (“Finish”).

Обозначим через M(C,R) минимальное количество карт, необходимых для прохода через R комнат, имея при себе не более C карт в каждый момент времени.

Например, M(3,6)=123 и M(3,7)=366.

Поэтому ΣM(3,R)=489 при 6≤R≤7.

Можно подсчитать, что ΣM(5,R)=2841 при 1≤R≤15.

Найдите ΣM(5,R) при 1≤R≤60.

На каждую клетку доски N×N положили по шашке, окрашенной в белый цвет с одной стороны и в черный цвет с другой.

Каждым ходом разрешается перевернуть одну шашку, а вместе с нею N-1 шашек, стоящих  на одной с ней вертикали, и N-1 шашек, стоящих  на одной с ней горизонтали. Таким образом, каждым ходом игрок должен перевернуть 2×N-1 шашку. Игра заканчивается, когда все шашки будут стоять белой стороной вверх. Ниже приведен пример игры для доски 5×5.

Несложно проверить, чтобы закончить игру из данной начальной позиции, нужно как минимум 3 хода.

Пусть строки и столбцы перенумерованы целыми числами от 0 до N-1.

Построим на доске N×N начальную конфигурацию C_N. Для этого на клетку с координатами x и y положим шашку черной стороной вверх, если (N-1)²≤x²+y²<N², и белой стороной вверх в противном случае. Конфигурацию C₅ мы видели в приведенном примере.

Пусть T(N) – минимальное количество ходов, необходимых для окончания игры из начального положения C_N (если это невозможно T(N) = 0).

Ясно , что T(1)=T(2)=1. Мы видели, что T(5)=3. Можно проверить, что T(10)=29, а T(1000)=395253.

Найдите сумму T(k!) для 1≤k≤12.

Несколько чашек расставлены по кругу, и в каждой из них лежит одна горошина. Игрок совершает ходы следующим образом. Он берет все горошины из одной чашки и раскладывает их одну за другой в чашки, следующие за ней по часовой стрелке. При каждом следующем ходе горошины берут из той чашки, куда была положена последняя горошина на предыдущем ходе. Игра заканчивается, когда возвращается к исходному положению, т. е. в с каждой чашке снова оказывается по одной горошине. Вот игра для случая пяти чашек:

Как видно, для пяти чашек игра заканчивается за 15 ходов.

Обозначим через M(x) количество ходов в игре с  x  чашками. Тогда M(5) = 15. Можно проверить, что M(100) = 10920.

Найдите остаток от деления  на 7⁹.