Посчитаем сначала общее количество способов распределить дни без учёта условия. Заметим, что нам нужно выбрать 4 голодных дня, остальные сразу станут обжорными. Значит, их количество

Теперь посчитаем способы, которые нам не подходят под условия, чтобы вычесть их. Понятно, чтобы не выполнялось условие задачи нужно иметь хотя бы 3 голодных дня подряд, но, т.к. голодных дней всего 4 возможно два варианта:

1) У нас 3 голодных дня подряд и 1 голодный, не стоящий с ними рядом. Будем воспринимать эти 3 дня как 1, назовём его большой голодный день, т.е. теперь у нас будет 8 дней и мы распределяем большой голодный день и голодный день так, чтобы они не стояли рядом. Если большой голодный стоит первым или последним, то у обычного есть 6 вариантов, в иных случаях у него их 5. В итоге

2) У нас 4 голодных дня подряд. Количество таких способов равно количеству способов выбрать место для первого голодного дня, оно равно 7.

В итоге количество способов распределения, подходящих под условия равно

Всего способов переставить 11 букв (из них по 3 У и по 2 А, Р, Б, З)

Чтобы слово было симметричным, на позиции должна стоять буква У (иначе не будет симметрии, так как оставшиеся буквы идут парами). На позициях с первой по пятую можно поставить способами любую последовательность букв. Тогда, чтобы была симметрия, буквы на оставшихся позициях определяются однозначно.

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

Обозначим вероятность хорошей погоды в день считая марта за первый день. Тогда

(Если в -й день погода плохая, то в -й она точно хорошая, а если хорошая, то в -м дне будет хорошей с вероятностью ). По условию . Находим последовательно

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером (нумерация по часовой стрелке), сидит на дереве по модулю 6 (то есть просто белку переместили на противоположное место). Нетрудно видеть, что это противоположное место является либо тем местом, на котором белка сидела утром, либо соседним с ним. Значит, можно решить задачу, в которой каждая белка либо осталась на своём месте, либо перешла на соседнее.

Пусть изначально белки сидели в порядке . Рассмотрим случаи:

Все остаются на своих местах. Тогда есть только один случай ().

Если перемещается вправо на место , у есть два варианта действий. может переместиться влево(на место ) или переместиться вправо на место .

Рассмотрим движение по кругу. Если перемещается на место , то единственный способ для — переход к , переход к , переход к и переход к , в результате чего достигается . Каждый бельчонок может также двигаться влево(). Таким образом, тут два случая.

Некоторые бельчата из соседних пар , , меняются местами, оставаясь в той же паре. Если перемещается на место , перемещается на место . может остаться на месте, или переместиться на , может остаться на месте, или переместиться на . Это даёт случаев, но бельчата не могут все оставаться на месте, поскольку мы уже посчитали такую возможность в случае , и, следовательно, здесь случаев. Кроме этого, могут быть пары что даёт еще случаев.

Меняются местами не в соседних парах, а в парах, разделённых одним бельчонком. Если бы и поменялись местами, и могли бы поменяться местами, и это не было бы учтено предыдущими группировками. При этом два бельчонка, разделяющие пары, сидят на прежних местах. Это может происходить в трёх случаях ( и не движутся, и не движутся, и не движутся).

Всего случаев .

Обозначим событие Произведение чисел не делится на , Среди чисел нет Среди чисел нет чётного Тогда

Вероятность искомого события равна

Понимаем, что при раскрытие скобок степень каждого одночлена будет иметь вид где — количество взятых — количество взятых Поэтому решим сначала уравнение в натуральных числах

Нетрудно заметить решение а также что это решение единственное, т.к. иначе, чтобы сохранить нужные остатки, будет изменяться на кратное 15 число, а на кратное 17, поэтому одно из них станет отрицательным.

Осталось лишь посчитать количество способов выбрать комбинацию из двух и одного в 6 скобках:

Начнём считать с вратарей. Место вратаря может занять только вратарь, поэтому у нас всегда всего 2 способа выбрать его.

Дальше рассмотрим три случая по количеству универсалов на месте защитников:

1. Среди выбранных защитников нет универсалов. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо универсалов, следовательно, способов

Следовательно, вариантов команд в этом случае

2. Среди выбранных защитников один универсал. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшихся универсалов, следовательно, способов

Следовательно, вариантов команд в этом случае

3. Среди выбранных защитников оба являются универсалами. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшегося универсала, следовательно, способов

Следовательно, вариантов команд в этом случае

В итоге способов выбрать команду равно

Будем выбирать 4 точки - вершины прямоугольника. Первую вершину можно выбрать произвольным образом в одном из узлов квадрата которых всего имеется так как в строке и в столбце по узлов. Далее выбираем точку в той же горизонтали одним из способов. После этого выбираем точку в той же вертикали, тоже одним из способов. Последняя вершина задается однозначно тремя предыдущими. Тогда получаем вариантов. Заметим, что каждый прямоугольник посчитан 4 раза, так как есть 4 способа выбрать первую вершину прямоугольника. Таким образом, всего прямоугольников

Рассмотрим любую очередь, в которой побеждает человек-паук. Тогда, поменяв местами человека-паука и человека-муравья, получим очередь, в которой победителем выходит человек-муравей. Получается, что все возможные очереди разбиваются на пары, в одной из которых побеждает человек паук, а в другой - человек-муравей. Значит, ровно половина всех очередей - те, в которых побеждает человек паук.

Всего возможных очередей имеется

Тогда победных очередей для человека-паука ровно

Будем последовательно выбирать цифры от первого места к последнему.

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

• Если то или
• Если то или
• Если то или
• Если то или
• Если то или

Заметим, что для каждого можно выбрать последнюю цифру двумя способами. Это значит, что последнюю цифру нашего числа можно выбрать двумя способами. Тогда количество чисел, сумма цифр которых делится на 5, равно

(a) На каждую позицию номера можно выбрать одну из цифр, поэтому всего номеров Так как четных цифр всего , то, выбирая на каждую позицию одну из пяти четных цифр, получаем, что номеров с четными цифрами всего

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

(c) Первую цифру можно выбрать ю способами. Вторую цифру - ю, так как нельзя использовать цифру, стоящую на первом месте. Третья цифра может быть выбрана ю способами, так как теперь не могут быть использованы цифры с первого и второго мест. Рассуждая аналогично, получаем, что для оставшихся мест имеется и способов соответственно. Получаем, что искомое число равно

(d) Выберем первую цифру произвольным образом (есть способов.) После того, как первая цифра была выбрана, была выбрана и четность оставшихся пяти цифр, и для каждой из них остается ровно вариантов выбора. Тогда количество номеров с четными или нечетными цифрами равно

(e) Если из общего числа номеров вычесть число номеров, в которых все цифры четны, получим число номеров, в которых есть хотя бы одна нечетная цифра. Тогда число номеров с нечетной цифрой равно

f Вычтем из числа номеров, не содержащих , число номеров, не содержащих цифр и Ясно, что это и будет искомым числом, так как тогда останутся номера, не содержащие но в которых есть Номеров без нулей всего так как каждую цифру можно выбрать девятью способами. Число цифр, в которых нет еще и цифры равно так как каждая из цифр может быть выбрана восьмью способами. Таким образом, искомое число номеров равно

Каждый из 5 элементов последовательности точек и тире можно выбрать двумя способами, поэтому количество символов, которые можно закодировать, равно

Символ может кодироваться последовательностью из одного, двух, трех, четырех или пяти элементов. В каждом случае ответ считается аналогично предыдущему пункту и равны соответственно Осталось сложить все эти числа:

Из отрезков можно сложить четырехугольник тогда и только тогда, когда . Рассмотрим четверку , заметим, что , следовательно, , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что .

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

Рассмотрим последовательность, состоящую из чисел, в котором каждое из чисел участвуют ровно два раза и назовем ее хорошей. Восстановим по хорошей последовательности способ разбиения интересной последовательности. На первом шаге рассмотрим первое число в каждой из последовательности. На каждом следующем шаге, если рассматриваемое число в хорошей последовательности встречается впервые, то ставим ему в соответствие рассматриваемое число в интересной последовательно, после чего рассматриваем следующий числа в каждой из последовательностей. Если рассматриваемое число в хорошей последовательности встречается во второй раз, то ставим ему в соответствие тройку из рассматриваемого элемента в интересной последовательности и двух элементов, идущих после него. Таким образом, к концу процесса, каждому первому вхождению числа в хорошей последовательности стоит в соответствие один элемент интересной последовательности, а каждому второму тройка подряд идущих элементов интересной последовательности.

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

Возьмем какое-нибудь число Тогда возможны два варианта:

1. Если то и

2. Предположим Тогда Иначе
(а) Если
(b) Если
И так как то

Таким образом, для любого либо либо есть три различных числа таких, что

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что Значит, для всех чисел верно Такая функция одна.

2. Есть одна тройка элементов, что Выбрать тройку можно способами. При этом есть два способа задать функцию в тройке. Итого функций.

3. Есть две тройки элементов, что Выбрать первую тройку можно способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку и выбрали все кроме одинаковые. То есть способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого функций.

Всего число функций равно

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

Итак, считаем пятизначные числа, в которых нет . На первом месте может стоять любая из цифр (кроме и ), на втором, третьем, четвёртом и пятом местах — любая из цифр (кроме ). Так как цифры выбираются последовательно и выбор очередной цифры не зависит от выбора предыдущих, то эти способы перемножаются. Значит, всего есть пятизначных чисел без в записи. Тогда пятизначных чисел с цифрой в записи всего

Замечание. Если бы мы считали сразу количество чисел с цифрой , то у нас возникло бы две проблемы. Во-первых, пятерка может стоять на любом из мест, и все эти способы надо учесть. Во-вторых, пятерок может быть несколько, и такие числа, как, например, мы можем посчитать несколько раз. Поэтому-то, чтобы решить эти две проблемы одним махом, мы считаем числа, в записи которых нет .

Найдём сначала количество троек натуральных чисел. Пусть

где — целые неотрицательные числа. Тогда получаем

Числа составляют в указанном порядке геометрическую прогрессию тогда и только тогда, когда , откуда

Из полученных уравнений получаем систему

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

Если рассматривать также отрицательные значения переменных, то можно заметить, что подходят все тройки чисел вида , где положительны и составляют геометрическую прогрессию. Таких троек ровно столько, сколько и в первом случае, поэтому окончательно имеем тройки.

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

Замечание. Поиск в глубину по корневому дереву осуществляется следующим образом: мы идём каждый раз влево-вниз, пока не придём в лист, затем поднимаемся до ближайшей вершины с более чем одним потомком, «отрезаем» рёбра и вершины, по которым мы прошли дважды, и вновь идём всегда влево-вниз до листа, после чего повторяем алгоритм, пока не сотрём весь граф.

Поскольку в дереве с вершинами ребер, мы получим скобочную последовательность длины Назовем скобки “парными”, если они отвечают проходу по одному и тому же ребру. Нетрудно видеть, что любая подпоследовательность между парными скобками является правильной. Поэтому наше отображение, во-первых, возвращает правильную скобочную последовательность и, во-вторых, имеет обратное. Так, чтобы построить дерево по данной скобочной последовательности, разобьем скобки на пары правильным образом и будем проводить ребро из текущей вершины в нового потомка вниз каждый раз, когда мы видим открывающую скобку, и подниматься по ребру вверх, когда видим закрывающую. Поскольку парные скобки соответствуют проходу по одному и тому же ребру, мы гарантируем, что в конце обхода мы получим дерево с вершиной. Таким образом, число корневых деревьев с вершиной равно числу правильных скобочных последовательностей длины то есть -му числу Каталана.

Рассмотрим таблицу из предыдущей задачи. Покажем как из такой таблицы получить расстановки учеников Анатолия и Василия. Вычеркнув из нее числа от до получим первую «таблицу» — расстановку учеников Анатолия. Если вычеркнуть, наоборот, числа от 1 до повернуть «таблицу» на и заменить каждое число на то получим вторую «таблицу» — расстановку учеников Виталия. Ясно, что такое отображение биективно, поскольку очевидно как построить к нему обратное. Количество расстановок, тем самым, равно

Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является