Комбинаторика на Бельчонке: способы, вероятности, графы, турниры, клетки

Сосчитаем способы без учёта ограничений на повторы и максимум у Бори. Метод шаров и перегородок даёт способов деления.

Теперь вычтем способы с повторами. Так как 1001 не кратно 3, число орехов может совпасть только у двоих, это число может быть любым от 1 до 500. Для каждого возможного есть 3 способа распределить и орехов между троими. Значит, число способов с повторами равно а без повторов —

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

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

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

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

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

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

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

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

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

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

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

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

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

Первое решение.

Выложим в ряд орехи и грибы — сделать это можно способами. Далее рассмотрим позиции между выложенными орехами и грибами и по краям от них — получим 14 мест для ягод. Остаётся выложить их туда способами.

Второе решение.

Сначала объединим орехи и грибы в неягоды, откуда получим 13 неягод и 11 ягод. Далее назовём нейтроном пару (неягода, ягода).

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

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

Получаем расстановки. Остаётся вспомнить, что неягоды делятся на два вида. Чтобы учесть это, домножим все способы на то есть число способов расставить орехов среди тринадцати неягод, откуда и получаем ответ.

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

Оценка: Докажем по индукции, что число ничьих не превосходит

База индукции: При это очевидно. При все три игры не могли закончиться вничью, иначе у всех команд было бы одинаковое число очков.

Шаг индукции: Рассмотрим две команды и сыгравшие вничью. С каждой из остальных команд хотя бы одна из них сыграла не вничью, иначе образуется запрещенная тройка команд. Значит, общее число ничьих в играх с участием этих двух команд не больше По предположению индукции в играх между остальными командами было не более ничьих. Следовательно, общее число ничьих не превосходит

Пример: Пронумеруем команды числами от до Пусть каждые две команды с номерами разной чётности сыграли вничью, а в играх между командами с номерами одной чётности победила команда в меньшим номером. Если то команд имеют нечётный номер и команда - чётный, поэтому количество ничьих равно При получаем по команд с номерами каждой чётности и ничьих. В обоих случаях полученное число равно При этом каждые три команды в играх между собой набрали либо 0, 2 или 4 очка, если имеют номера одной чётности, либо очка, если две из них имеют номера одной чётности, а третья - другой.

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

Подставим и получим ответ.

Число способов рассадки, когда Андрей и Боря сидят рядом, равно (достаточно объединить их в одного человека двумя способами). Способов рассадки, при которых и Андрей-Боря, и Вася-Гриша окажутся рядом, равно Поэтому они могут сесть способами.

Оценка: До пересчёта у команды «Бельчата» было хотя бы на 2 очка больше, чем у команды «Метеор», а после пересчёта - хотя бы на 2 очка меньше. Кроме того, чтобы после пересчёта оказаться первой, команда «Метеор» должна иметь хотя бы одну победу. Действительно, в каждом матче разыгрывается 2 очка, поэтому если бы у команды «Метеор» не было побед, то она набрала бы не более половины возможного числа очков и не могла бы стать первой. Аналогично, для того чтобы команда «Бельчата» стала последней, у неё должно быть поражений больше, чем побед. Таким образом, после пересчёта команда «Метеор» потеряет как минимум 1 очко. Следовательно, команда «Бельчата» должна потерять не менее 5 очков, т. е. у неё должно быть не меньше пяти побед и не меньше шести поражений. Поэтому она сыграла как минимум 11 матчей, значит, в турнире участвовало не менее 12 команд.

Пример: Приведён в таблице (первой буквой В обозначен выигрыш, два последних столбца — количество очков до и после пересчета соответственно).

Команда													Сумма 1	Сумма 2
		B	B	B	B	B	0	0	0	0	0	0	15	10
	0		1	1	1	1				0	0	1	14	11
	0	1		1	1	1	0				0	1	14	11
	0	1	1		1	1	0	0				1	14	11
	0	1	1	1		1		0	0			1	14	11
	0	1	1	1	1				0	0		1	14	11
		0			0	0		1	1	1	1	1	14	11
		0	0			0	1		1	1	1	1	14	11
		0	0	0			1	1		1	1	1	14	11
			0	0	0		1	1	1		1	1	14	11
				0	0	0	1	1	1	1		1	14	11
		1	1	1	1	1	1	1	1	1	1		13	12

Борис положит в первую коробку 1 белый шарик, а во вторую все остальные. Тогда вероятность вынуть белый шарик равна

Рассмотрим уравнение

Расставим единиц в ряд, выберем два промежутка между единицами и поставим в них по чёрточке. Число единиц слева от первой чёрточки равно (число яблок в первой корзине), справа от второй равно (число яблок в третьей корзине). Число способов выбрать два промежутка равно

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

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

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

Число равно числу упорядоченных троек различных . Но нужен порядок , поэтому разделим на число перестановок трёх элементов:

Пусть Владимир два раза встречается с более слабым соперником, то есть рассмотрим схему БАБ. Тогда вероятность равна

Пусть Владимир выбирает схему АБА. Тогда получим

Если — четное число, то вся таблица разбивается на квадратов , в каждом из которых находится ровно 2 фишки. Поэтому общее число фишек равно .

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

так, как показано на рисунке:

В любой такой фигуре должна стоять хотя бы одна фишка, иначе в квадрате , примыкающем к данной, должно быть не менее 3 фишек — противоречие.

Таким образом, общее число фишек в таблице не менее

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

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

(В этом примере число фишек равно , где .

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

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

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

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

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