В кабинете министров Анчурии 100 министров. Среди них есть жулики и честные министры. Известно, что из любых десяти министров, по крайней мере, один министр — жулик. Какое наименьшее число министров-жуликов может быть в кабинете?
Ответ:
Решение:
В архипелаге Новая Гексания шесть островов. Каждый остров соединен мостами с четырьмя другими, как показано на рисунке. Если два острова соединены, то жители этих двух островов считают себя соседями. Всего на островах шесть обитателей — на каждом острове живет либо рыцарь, либо лжец. Рыцарь всегда говорит правду и не может солгать, а лжец — наоборот — не может сказать правду. Каждый островитянин утверждает, что если выбрать случайным образом одного из его соседей, то он с вероятностью 0,5 окажется лжецом и с вероятностью 0,5 — рыцарем. Даже рыцарь Персиваль утверждает то же самое. Сколько на островах рыцарей и сколько лжецов?
Ответ:
Решение:
Планета Гексания имеет форму куба. Всего на Гексании шесть жителей — на каждой из шести граней живет либо рыцарь, либо лжец. Рыцарь всегда говорит правду и не может солгать, а лжец — наоборот — не может сказать правду. Каждый гексанин утверждает, что если выбрать случайным образом одного из его соседей, то он с вероятностью 0,5 окажется рыцарем и с вероятностью 0,5 — лжецом. Даже рыцарь Ланселот утверждает то же самое. Сколько на Гексании рыцарей и сколько лжецов?
Ответ:
Решение:
На рисунке изображена схема трассы для картинга. Старт и финиш в точке $A$, причем картингист по дороге может сколько угодно раз заезжать в точку $A$ и возвращаться на круг.
На путь от $A$ до $B$ или обратно юный гонщик Юра тратит минуту. На путь по кольцу Юра также тратит минуту. По кольцу можно ездить только против часовой стрелки (стрелки показывают возможные направления движения). Юра не поворачивает назад на полпути и не останавливается. Длительность заезда 10 минут. Найдите число возможных различных маршрутов (последовательностей прохождения участков).
На путь от $A$ до $B$ или обратно юный гонщик Юра тратит минуту. На путь по кольцу Юра также тратит минуту. По кольцу можно ездить только против часовой стрелки (стрелки показывают возможные направления движения). Юра не поворачивает назад на полпути и не останавливается. Длительность заезда 10 минут. Найдите число возможных различных маршрутов (последовательностей прохождения участков).
Ответ:
Решение:
Шахматный король находится на поле a1 шахматной доски и хочет пройти на поле h8, двигаясь вправо, вверх или вправо-вверх. Сколькими способами он может это сделать?
Ответ:
Решение:
Из одинаковых квадратов составляется фигура: левый столбик состоит из одного-единственного квадрата, а в каждом следующем столбике на один или на два квадрата больше, чем в предыдущем. В самом правом столбике ровно $n$ квадратов. Докажите, что количество различных фигур, которые можно построить таким способом, равно $n$-му числу Фибоначчи. На рисунке показана одна из таких возможных фигур высотой 5 квадратов.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Ответ:
Решение:
У плиточника $n$ одинаковых плиток размером $1\times 2$ фута. Он должен выложить дорожку шириной 2 фута и длиной $n$ футов. Докажите, что количество различных способов укладки дорожки равно $(n+1)$-му числу Фибоначчи. Способы считаются различными, если они отличаются порядком укладки плиток вдоль и поперёк дорожки; на рисунке показан один из возможных способов выложить дорожку длиной 5 футов.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Ответ:
Решение:
Имеется резинка и стеклянные шарики-бусины: шесть одинаковых красных, две одинаковых синих и четыре одинаковых зелёных. Нужно все двенадцать бусин нанизать на резинку последовательно, чтобы получился браслет. Сколько различных браслетов можно составить так, чтобы бусины одного цвета не оказались рядом? (Считайте, что застёжки нет, а узелок на резинке незаметен).
Ответ:
Решение:
Имеется резинка и стеклянные шарики-бусины: четыре одинаковых красных, две одинаковых синих и две одинаковых зеленых. Нужно все восемь бусин нанизать на резинку последовательно, чтобы получился браслет. Сколько различных браслетов можно составить так, чтобы бусины одного цвета не оказались рядом? (Считайте, что застёжки нет, а узелок на резинке незаметен).
Ответ:
Решение:
Катя решила вышить себе на свитере узор: пять точек по кругу, причём каждые две точки соединены отрезком. Каждую точку Катя вышивает за 1 минуту, а каждый отрезок — ровно за 4 минуты. Сколько минут потребуется Кате, чтобы вышить весь узор (если она ничего не пропустит и нигде не запутается)?
Ответ:
Решение:
Лиза решила вышить себе на футболке узор: шесть точек по кругу, причём каждые две точки соединены отрезком. Каждую точку Лиза вышивает за 1 минуту, а каждый отрезок — ровно за 3 минуты. Сколько минут потребуется Лизе, чтобы вышить весь узор (если она ничего не пропустит и нигде не запутается)?
Ответ:
Решение:
Квадрат разбит на треугольники (см. рисунок). Сколько существует способов закрасить ровно треть квадрата? Маленькие треугольники нельзя красить частично.
Ответ:
Решение:
Сколько существует различных семизначных чисел, в записи которых ровно две цифры 7, две цифры 0 и три цифры 9?
Ответ:
Решение:
Сколько существует различных шестизначных чисел, в записи которых ровно две цифры 1, две цифры 0 и две цифры 3?
Ответ:
Решение:
Пусть натуральные числа $k$ и $n$ взаимно просты, причём $n\geqslant 5$ и $k\lt n/2$. Правильной $(n;k)$-звездой назовём замкнутую ломаную, которая получится, если в правильном $n$-угольнике каждые $k$ последовательных сторон заменить диагональю с теми же концевыми вершинами. Для примера на рисунке показана $(5;2)$-звезда. Эта звезда имеет 5 точек самопересечения — это жирные точки на рисунке. Сколько самопересечений у звезды $(2018;25)$?
Ответ:
Решение:
На рисунке справа изображена прямоугольная сетка $5\times 6$. Сколько всего существует прямоугольников, у которых вершины расположены в узлах сетки, а стороны лежат на линиях сетки? Один такой прямоугольник показан для примера.
Ответ:
Решение:
На рисунке справа изображена прямоугольная сетка $4\times 7$. Сколько всего существует прямоугольников, у которых вершины расположены в узлах сетки, а стороны лежат на линиях сетки? Один такой прямоугольник показан для примера.
Ответ:
Решение:
Рассмотрим двоичную последовательность, то есть последовательность нулей и единиц. Назовем $1,k-1$-словом фрагмент этой последовательности вида $1\underbrace{00\ldots0}_{k-1}$, за которым непосредственно следует единица или конец последовательности.
Пример. В последовательности $01000\underline{100}101\underline{100}$ ровно два $1, 2$-слова. Они подчеркнуты.
Докажите, что во всех бинарных последовательностях длины $n$, содержащих ровно $m$ единиц, общее количество $1,k-1$-слов равно $m\cdot C_{n-k}^{m-1}$ $(k\leqslant n)$.
Пример. В последовательности $01000\underline{100}101\underline{100}$ ровно два $1, 2$-слова. Они подчеркнуты.
Докажите, что во всех бинарных последовательностях длины $n$, содержащих ровно $m$ единиц, общее количество $1,k-1$-слов равно $m\cdot C_{n-k}^{m-1}$ $(k\leqslant n)$.
Ответ:
Решение:
2012 правильных игральных костей (кубиков) составили в ряд таким образом, что каждые две соседние кости прилегают друг к другу одинаковыми гранями (принцип домино). В остальном положение костей случайное. Найдите сумму очков, которые оказались на поверхности получившейся фигуры.
Ответ:
Решение:
Ковбои Билл и Джо стреляют без промаха. Они решили посоревноваться в удачливости. Каждый зарядил свой 10-зарядный револьвер пятью боевыми патронами и пятью холостыми.
Билл и Джо одновременно стреляют каждый по своей мишени. Они стреляют до тех пор, пока хотя бы одна из мишеней не будет поражена. Если попал в свою мишень кто-то один — он победитель. Если попали оба, то объявляется ничья. После каждого выстрела барабан револьвера автоматически поворачивается на одно гнездо, подставляя под боек следующий патрон. Билл случайным образом раскручивает барабан своего револьвера перед каждым выстрелом, а Джо решил раскрутить свой барабан наудачу только перед первым выстрелом.
В каком порядке Джо должен зарядить холостые и боевые патроны в барабан своего револьвера, чтобы вероятность его победы стала наибольшей?
Билл и Джо одновременно стреляют каждый по своей мишени. Они стреляют до тех пор, пока хотя бы одна из мишеней не будет поражена. Если попал в свою мишень кто-то один — он победитель. Если попали оба, то объявляется ничья. После каждого выстрела барабан револьвера автоматически поворачивается на одно гнездо, подставляя под боек следующий патрон. Билл случайным образом раскручивает барабан своего револьвера перед каждым выстрелом, а Джо решил раскрутить свой барабан наудачу только перед первым выстрелом.
В каком порядке Джо должен зарядить холостые и боевые патроны в барабан своего револьвера, чтобы вероятность его победы стала наибольшей?
Ответ:
Решение: