Авторы:
Жучков Борис (6 класс)
Казанцева Варвара (7 класс)
Ковцур Лев (6 класс)
Руководитель команды:
Зинцова Анастасия Сергеевна
По кругу расставлены К девочек и К мальчиков. Пара детей называется хорошей, если между ними расположено поровну мальчиков и девочек. Какие значения может принимать число хороших пар?
Введение:
Когда мы думали над этой задачей, то у нас появились разногласия. Аня думала, что есть разные варианты определения хороших пар:
1. Определить по короткой стороне.
2. Определить по длинной стороне.
3. Определить по обе стороны.
Дима полагал, что хорошая пара - это пара из двух элементов “круга”, количество соседей, которых равно.
Хорошие пары из противоположных детей
Возьмём пару, соединим их диаметром и смотрим:
На рисунке 2 я соединил мальчика и девочку, дальше смотрю: по “левому” полукругу 0 мальчиков, 0 девочек, так как они равны между собой (детей разного пола одно кол-во), то есть претензия на хорошесть этой пары; теперь мы смотрим на правый полукруг: там тоже 0 мальчиков, 0 девочек.
Если пары соединяются противоположно, то короткой и длинной дугой не попользуешься. Сначала мы определяем, равны между собой мальчики и девочки или нет. Если выясняется, что равны, то мы смотрим на то, соответствует ли кол-во детей на одном полукруге кол-ву на другом. Если у нас на одном полукруге мальчик и девочка, то на другом полукруге должен быть точно такой же набор. Тогда рассматриваемая пара будет считаться хорошей.
Приходится тогда ввести левый и правый полукруги. То, на рисунке 3 в данном случае по левому полукругу у нас хорошая пара, а по правому плохая.
Поэтому будем считать следующим образом:
Если мы соединяем однополую пару, стоящих напротив друг друга детей, то эта плохая, потому что полукруги “не равны”.
Подводя итог вышесказанному выводим формулу.
В круге должно быть (4х+2) человек, чтобы имелась хотя бы одна хорошая пара. Здесь х∊N∪{0}
Пояснение:
2х у нас берётся из-за того, что кол-во человек в одном полукруге может быть толькочётное, чтобы были теоретические шансы на победу, а из-за того, что полукруга два, мы получаем (2*2)х=4х.
А 2 в конце, это два человека, относительно которых мы меряем, то это пара, которой мы будем присваивать статус хорошей или плохой.
Наблюдение:
Если я соединяю однополых детей, то эта пара плохая, т.к. на полукругах не смогут получиться одинаковое по полу кол-во детей.
Далее будем рассмартивать только К - нечетное, так как если К четное, а поэтому формула 4х+2 не соблюдается, то хороших пар - 0, а плохих - все имеющиеся, то есть К пар. Из-за 4х=2К (см. в пояснении “Первые 2х у нас берутся из-за того, что…”)
Расстановка 1: сначала все мальчики, затем все девочки.
Рассмотрим ситуацию, когда сначала все мальчики стоят, а затем все девочки.
В случае 6 детей, как на рис. 4, мы наблюдаем ситуацию, что хорошая пара - это пара детей, которые стоят в центре стоящих подряд детей одного пола. Староста стоит в центре мальчиков/девочек, если они расположены подряд. Детей одного пола должно быть нечётное кол-во, чтобы у них был староста. Если есть староста, то есть минимум 1 хорошая пара. Подтверждение нашей формуле: у каждого пола будет 2х человек и тот, относительно которого слева и справа одинаковое количество детей его пола (староста).
Вывод:
При расстановке 1 “сначала все мальчики, затем все девочки”, если К нечетное, то хороших пар - 1, а плохих - (К-1).
Расстановка 2: мальчики и девочки чередуются.
В случае, подобном рис. 5 (повторение) все пары хорошие, потому что они чередуются, и в каждый полукруг попадает равное кол-во м и д.
Вывод:
При расстановке 2 “мальчики и девочки чередуются”, если К нечетное, то хороших пар - К, а плохих - 0.
Расстановка 3: К-s мальчиков, затем s девочек, s мальчиков, К-s девочек.
Рассмотрим s=1.
Если К нечетное, то хороших пар - 1, а плохих - K-1.
Та же самая история, что и со старостами. Средний мальчик организует хорошую пару, как на рис. 7. Средний мальчик - староста. Т.е. староста - это тот человек, слева и справа от которого одинаковое количество детей его пола, поэтому у него всегда будет хорошая пара. Началом отсчета старосты мы принимаем границу между (К-s) мальчиков и (К-s) девочек. Предоставим картинки для 6, 10. Граница (точка отсчёта) обозначена линией. ⇒ Мы отчерчиваем линию, пересекающую круг. Потом ставим К-s мальчиков, потом К-s девочек, затем s мальчиков и затем s девочек.
Рис. 7
Отступление:
Мы решили создать систему пленников. Пленники обведены в красный кружок, а старосты - в зелёный кружок. Пленников у нас будет 2s.
Примечание: Пленники “принимают участие” в определении старосты.
Рассмотрим s=2.
Если К нечетное, то хороших пар - 1, а плохих - К-1.
В К-2 случае у нас 4 пленника, 2 мальчика, 2 девочки. Они стоят так: м-м-д-д.
Рассмотрим s=3.
Если К нечетное, то хороших пар - 1, а плохих - К-1.
Из вышеприведенного следует следующая теорема.
Теорема:
При К нечетном в расстановке вида “К-s мальчиков, затем s девочек, s мальчиков, К-s девочка, где s - натуральное число” хороших пар - 1, а плохих - (К-1).
Доказательство: Одна хорошая пара будет образовываться старостой, только у них слева и справа будет одинаковое кол-во детей своего пола. А так как у двух старост детей будет одинаковое кол-во слева и справа, то и хорошая пара будет образовываться двумя старостами.
Расстановка 4: Винегрет. “Чередующиеся пленники”.
s должен быть больше 1, т.к. “Чередующиеся пленники” будут точной копией “Повторения мальчиков и девочек”.
Если К-s=1, то это такая же расстановка, как и в повторяющихся м. и д.
Рисунки для К=5:
Рисунки для К=7:
Поправка: Вместо фразы “К-s<K/2” или “К-s>K/2” должна быть фраза: “s - хороших, К-s - плохих”. (У нас не было времени менять скриншоты, поэтому мы поправляемся)
Вывод: Если К нечётное и расстановка произведена следующим образом, то хороших пар - s, плохих - К-s.
Хорошие пары по коротким или длинным дугам.
Наблюдения:
- Если дети в паре держатся за руку, то эта пара хорошая по короткой дуге, т.к. у нас 0 девочек и 0 мальчиков, то эта пара хорошая.
- Детей можно соединять так, как на рисунке 1 (в самом верху). Если между детьми в парах нечётное кол-во детей, то эта пара по короткой стороне будет плохая, как на рис. 1, более того, эта пара будет плохая и по длинной стороне.
Для шести хорошесть по короткой дуге:
Примечание: При том считаем по короткой дуге пару хорошей, если при равенстве дуг хотя бы на одной количество мальчиков и девочек совпадает.
Наблюдение: Все соседние дети образуют хорошие пары. Их будет 2К.
На третьем рисунке мы видим, что однополые пары по длинной дуге плохие, что лишний раз подтверждает то, что если мы соединяем по длинной дуге, к которым в какой-то мере можно отнести соединение противоположных пар.
Чередующиеся дети
Рассмотрим чередующихся детей и будем смотреть по всем дугам. Тут черным обозначены хорошие пары.
Из этого можем сделать вывод, что хороших соседних пар (плохих не бывает) 2К (т.е. все), “через одного” - 0, по противоположным парам - К.
Конкретизация насчёт “через одного”: По короткой дуге и по длинной пара плохая, потому что мы смотрим по обеим дугам, т.к. здесь чередование, то результаты по короткой и по длинной дугам одинаковые.
Обозначения:
Далее зеленым обозначены хорошие, а красным - плохие
Хорошие пары - пары, где выполняется условия по короткой и по длинной стороне.
Примечание:
Получается, что мы смотрим по обеим дугам, т.к. все повторяется, то результаты по короткой и по длинной дугам одинаковые.
Теорема:
При чередовании детей хороших пар будет К^2, плохих пар будет К*(К-1)
Доказательство:
Лемма о рукопожатиях: пара “девочка-мальчик” равна паре “мальчик-девочка”, поэтому в фигурных скобках ниже мы будем делить 2К пар на 2, чтобы получить К пар.
Лемма о рукопожатиях детей (Далее: “лемма о рукопожатиях): пара “девочка-мальчик” равна паре “мальчик-девочка”.
В фигурных скобках мы показали лемму о рукопожатиях.
При К=2:
Плохих - 0 (0*1)
Хороших - 1=1*1=1^2 {2/2}*{2/2} К^2
При К=4:
Плохих пар (красных) - 2=1*2 {4/2}
Хороших пар (зелёных) - 4=2*2=2^2. {4/2}*{4/2} К^2
При К=6:
Красных - 6 (2*3)
Зелёных - 9=3*3=3^2. {6/2}*{6/2} К^2
При К= 8:
Красных - 12=3*4
Зелёных - 16=4*4=4^2 {8/2}*{8/2} К^2
При К=10:
Красных - 20=4*5
Зелёных - 25=5*5=5^2 {10/2}*{10/2} К^2
Предположения:
При К=12:
Красных - 30=5*6
Зелёных - 36=6*6=6^2 {24/2}*{24/2} К^2
Теорему можно было бы считать доказанной, если бы был сделан рекурсивный переход.