На рисунке представлен неориентированный граф, содержащий семь вершин и 12 ребер, суммарный вес которых составляет 243.

Тот же граф можно представить следующей матрицей:

Однако, некоторые ребра можно "сэкономить", не нарушая связности графа. Граф, в котором достигается максимальная экономия, представлен ниже. Его вес - всего 93, а "экономия" по сравнению с исходным графом составляет 243-93 = 150.

Пусть задан граф, содержащий 40 вершин, занумерованных числами от 0 до 39. Вес ребра, соединяющего вершины i и j, выражается формулой
w_ij =  w_ji = (69069(i - j)²(i + j))(mod 1000)

Какой максимальной экономии можно добиться, удаляя лишние ребра без потери связности графа?

Игроку выдается 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.

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

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

Будем строить последовательность строк D0, D1,… Dn …следующим образом.
Пусть D0, - двухбуквенная строка "Fa". Для n, больших нуля, построим строку Dn, заменяя все вхождения символов "a" и "b" в строке Dn-1 следующим образом:
"a"  "aRbFR"
"b"  "LFaLb"
Тогда получим, что D0 = "Fa", D1 = "FaRbFR", D2 = "FaRbFRRLFaLbFR", и так далее.
Теперь предположим, что полученная строка является программой для плоттера, в которой символ "F" означает движение пера вперед на единицу, "R" – поворот на 90 градусов направо, а "L" – поворот на 90 градусов влево. Символы "a" и "b" на рисунок не влияют. Начальное положение пера – в начале координат (0,0), а начальное направление движения – вверх (0,1).
Получив на вход строку Dn, плоттер вычертит замысловатую ломаную, называемую "Дракон Хартера – Хейтуэя порядка n". Например, на рисунке ниже показан дракон D10. Если по команде "F" перо сдвигалось на один шаг, то в отмеченную голубым точку оно попало после 500 шагов. Ее координаты – (18,16).

Теперь представим, что плоттер начертил дракона 50-го порядка. На нем отметили точки  L и M, в которые перо попало, соответственно, после 10¹² и 10¹³ шагов. Найдите расстояние |LM|. Результат округлите вниз до целого.

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

Игрок бросает пять шестигранных костей (т.е. кубиков, грани которых пронумерованы от 1 до 6), а затем подсчитывает сумму трех наибольших выпавших значений.
Ниже приведены четыре примера, когда игрок получает 15 очков:

D1,D2,D3,D4,D5 = 4,3,6,3,5
D1,D2,D3,D4,D5 = 4,3,3,5,6
D1,D2,D3,D4,D5 = 3,3,3,6,6
D1,D2,D3,D4,D5 = 6,6,3,3,3

Существует ровно 1111 вариантов для пяти шестигранных костей, когда три наибольших выпавших значения дают в сумме 15.

А сколько будет вариантов для 18 двенадцатигранных костей (т.е. додекаэдров, грани которых пронумерованы от 1 до 12), когда 10 наибольших выпавших значений в сумме дают полный квадрат?

Рассмотрим множество, состоящее из первых 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¹⁸.