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

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

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

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером (нумерация по часовой стрелке), сидит на дереве по модулю 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 пустых клетки (незанятых фишками), то аналогично получаем, что пустых клеток в таблице также не менее . И зн̆ачит, фишек в таблице не более

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

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

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

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