Применение классических комбинаторных методов к разным задачам

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

откуда или 9.

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

Пусть — сумма чисел, полученная при данном процессе, при условии, что исходная куча содержит камней. Покажем по индукции, что

При разбиение на две кучи единственно и произведение количеств камней равно что доказывает выполнение базы индукции.

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

Таким образом, ответом на задачу является число

Обозначим Тогда

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

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

Если мы проделаем аналогичные рассуждения для других пяти положений а потом сложим, то в сумме получится

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

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

Сопоставим каждому числу в таблице пару весов где  — количество таких же чисел в одной строке с выбранным (включая его), а  — количество таких же чисел в одном столбце с ним. Назовем полным весом числа из таблицы сумму двух его весов. Для каждого оценим снизу сумму полных весов чисел, равных Пусть такие числа входят в строк и столбцов. Заметим, что тогда числа, равные могут стоять только в пересечении таких строк и столбцов, откуда Заметим, что в каждой строке из сумма первых весов чисел, равных равна Аналогично со вторыми весами и столбцами. Тогда вся сумма полных весов равна

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

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

Из первого условия следует, что ровно у точек оба соседа белые, а из второго — что ровно у точек оба соседа черные. Это означает, что у оставшихся точек соседи разного цвета.

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

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

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

Отметим на одном циферблате положения часовых стрелок всех часов. Циферблат разобьется на секторов. Занумеруем их по кругу. Пусть часовая стрелка проходит секторы за время соответственно (некоторые из этих чисел, возможно, нулевые). Заметим, что если мы станем устанавливать на всех часах время, соответствующее положению внутри сектора, то каждая часовая стрелка пройдет через начало сектора. Это значит, что суммарное время перевода окажется заведомо больше, чем если бы мы устанавливали все часы на начало сектора. Обозначим через суммарное время, необходимое для установки всех часов на начало -го сектора. Ясно, что время перевода отдельной стрелки является суммой некоторых Например, время перевода на начало первого сектора равно для пятых часов и для вторых. Тогда

Остальные выражаются аналогично. Тогда часов.

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

Ясно, что у каждого есть одинаковое количество друзей, обозначим его через Рассмотрим ребёнка и его друзей.

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

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

Этим решениям соответствуют и Примеры строятся в соответствии с решением: групп по ребят. Внутри групп ребята дружат, а ребята из разных групп враждуют.

(a) Докажем, что данный процесс не может продолжаться бесконечно. Пусть в начале на полосе лежат камней. За каждый ход общее количество камней уменьшается на следовательно общее количество ходов не превосходит то есть конечно.

Пронумеруем все клетки, начиная с крайней левой, в которой находится камень, натуральными числами от до Пусть в клетки с номером в начале лежит камней. Рассмотрим величину

Докажем, что значение является инвариантом. Действительно, пусть за ход два камня из клетки с номером переложили в клетку с номером Пусть — значение после хода, тогда

Осталось заметить, что в конце процесса в каждой клетке находится не больше одного камня. Тогда — двоичная запись числа в которой все цифры определены единственным образом, а значит и количество камней в каждой клетке в конце процесса определено единственным образом.

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

Пронумеруем все единицы, начиная с самой левой, натуральными числами от до Единице с номером поставим число где — количество нулей, которые находятся правее нее. Рассмотрим величину

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

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

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

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

Пусть знаки как-то расставлены. «Выпустим» машинку из дома. Пусть она движется согласно "правилам дорожного движения поворачивая попеременно то вправо, то влево. Тогда она не может "зациклиться"и когда-то выйдет за пределы квадрата

Отсортируем числа из множества по возрастанию:

Для любых трех последовательных чисел число по условию лежит в . Но

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

По условию числа , то есть , где - разность прогрессии.

и в силу того, что , а натуральное. Имеем единственное решение .

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

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

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

База индукции верна, поскольку после первого хода доска имеет вид прямоугольника причем следующих ход будет совершен Сергеем в нижнюю левую клетку.

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

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

Турнир задается выбором ориентации ребер, которых . Поэтому всего турниров . Рассмотрим вероятностное пространство, элементами которого будут все турниры на вершинах, причем для различных ребер их ориентации независимы. Это означает, что все турниры равновероятны.

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

Математическое ожидание равно вероятности того, что она равна 1 , т.е. , как произведение вероятностей независимых событий с вероятностью каждое.

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

Первое решение. Индукцией покажем, что для городов База очевидна.

Шаг индукции. Пусть для городов стёрто не более записей. Выберем город для которого стёрто хотя бы одно расстояние до другого города, и рассмотрим остальные городов. Между ними стёрто не более расстояний, и по предположению индукции можно восстановить все эти расстояния, а тогда и взаимное расположение этих городов на плоскости. Для города известны расстояния по крайней мере до трёх городов, и это позволяет однозначно восстановить его расположение. Увеличить до нельзя. Пусть неизвестны расстояния от точки до всех точек, кроме и Тогда положение точки определено с точностью до симметрии относительно прямой значит, расстояния от неё до остальных точек не восстанавливаются.

_________________________________________________________________________________________________________________________________________________________________________________

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

Расположим наши числа по убыванию, Имеем

Умножим первое равенство на получим, что

Следовательно,

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

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

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

(каждой бесконечной мелодии периода эквиваленты мелодий (включая саму с периодом, который будет циклическим сдвигом нот, дающих мелодию )

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(в скобках учтены запретные мелодии длины , полученные дописыванием символов к запретной мелодии длины , а за скобками — все остальные).

Таким образом, найдётся бесконечная мелодия, которая не содержит запретных мелодий, и для прохождения испытания Ивану достаточно сыграть её кусок длины

______________________________________________________________________________________________________________________________________________________

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

Пусть - число мелодий длины , не содержащих запретных последовательностей нот. Будем считать, что По индукции докажем, что для всех натуральных .

База индукции

Предположим, что неравенство верно для всех , меньших Покажем, что тогда Заметим, что

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

Из предположения индукции для также следуют неравенства:

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

Следовательно, и переход доказан.

Тогда из-за положительности последовательность возрастающая, а значит , откуда следует, что Иван справится с испытанием Кощея.