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

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

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

Переход: Первые две попытки Вася пошлёт строчки и После них Вася узнает правильный ответ на последний вопрос, а также за эти два вопроса учитель сообщит Васе, сколько ответов «Да» на первые вопрос правильные. Каждый следующий вопрос Вася будет посылать правильный ответ на вопрос, а для остальных вопросов он будет действовать по алгоритму для вопроса. По предположению индукции за оставшиеся попытки Вася сможет правильно правильно на все вопросы.

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

А вот сумма цифр 2 возможна. Например, “обратным ходом” можно найти пример получения записи 00011 (или 10001):

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

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

Оценка. Выделим все числа, минимальные в своих столбцах и все числа, максимальные в своих строках. Такие числа не могут быть седловыми. Мы хотим сказать, что выделено хотя бы число, тогда оценка будет доказана. Если это не так, то нашлось два числа и которые одновременно и минимальные в столбцах и максимальные в строках. Но тогда, Противоречие.

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

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

Предположим, что в -буквенном алфавите существует хорошее слово длины Тогда какая-то буква (скажем, встречается в нём хотя бы три раза. Отметим её второе и предпоследнее вхождение в слово (тогда стоит не правее, чем

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

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

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что длина хорошего слова не превосходит Индукция по В базовом случае буквы в слове чередуются, и слово длины хотя бы содержит фрагмент вида из которого вычёркиванием букв можно получить Для перехода предположим, что в -буквенном алфавите есть хорошее слово длины, не меньшей Тогда какая-то буква встречается в этом слове хотя бы три раза. Предположим, что букв, встречающихся хотя бы раза, две — и Пусть, без ограничения общности, второе вхождение стоит раньше второго вхождения тогда вычёркиванием букв можно получить слово что невозможно. Значит, буква встречается в слове раз, а все остальные — максимум по два раза. Тогда длина слова не меньше, чем и не больше, чем откуда Между вторым и третьим вхождением буквы есть какая-то буква Эта буква не может встречаться в других местах: если она встречается после второго вхождения то вычёркиванием букв можно получить а если до него — то (поскольку Пусть соседи буквы различны. Тогда, удалив её из слова, мы получим хорошее слово в -буквенном алфавите (без буквы Длина этого слова будет не меньше что противоречит индукционному предположению. Если же соседи буквы одинаковы, удалим из слова и букву перед ней; тогда на этом «стыке» останутся различные буквы. Поэтому мы опять получим хорошее слово в -буквенном алфавите, длина которого не меньше, чем это опять же невозможно по индукционному предположению.

Пример. Рассмотрим все слов, у которых начиная с -ой все буквы Ш, а первые — У или Я. Этот набор слов удовлетворяет условию.

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

______________________________________________________________________________________________________________________________________________________

Замечание. Оценку можно получить по-другому.

Способ 1. Подкинем монетку раз. Для каждого слова рассмотрим такое событие: при всяком если на некоторой позиции стоит буква У, то при -м подбрасывании выпала решка, а если буква Я, то орёл. Вероятность такого события равна и они не совместные, поэтому количество слов не больше чем

Способ 2. Пусть выбрано более слов. Присвоим каждому слову вес Пусть первая буква у слов У, у слов — Я и Удвоим веса всех слов с первой буквой У, и обнулим — с первой буквой Я. Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения -ой буквы. Пусть — сумма весов слов, у которых -ая буква У, — сумма весов слов, у которых -ая буква Я. Если удваиваем веса у слов с -й буквой Я и обнуляем — с -й буквой У. Иначе — наоборот. В результате таких операций сумма весов не уменьшается. После операций сумма весов всех слов будет больше В каждом слове только букв У или Я, поэтому вес каждого слова не больше Значит, найдутся два слова с одинаковыми весами. Тогда для них не найдется позиции, в которой у одного У, а у другого Я или наоборот, противоречие.

1) Упорядочим длины палочек

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

2) Пусть изначально были два равных треугольника со сторонами и Тогда в группе самых коротких палочек окажутся палочки из которых треугольник составить нельзя.

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

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

Заметим, что если разность полученной прогрессии имеет общий простой делитель с каким-нибудь её членом, то все члены этой прогрессии делятся на а тогда и все числа красивого набора, за исключением, быть может, одного, также делятся на Разделим все эти числа на (кроме, возможно, того, которое не делится); все выписанные на доску числа тоже разделятся на и по-прежнему будут последовательными членами непостоянной арифметической прогрессии, то есть также получится красивый набор. Это противоречит минимальности суммы чисел выбранного набора. Следовательно, взаимно просто со всеми выписанными на доску числами.

Пусть — максимальное число нашего красивого набора; тогда В прогрессии на доске будет не менее членов, кратных У каких-то двух из них номера отличаются не более, чем на

то есть разность этих членов (также делящаяся на ) равна при некотором

Но взаимно просто с поэтому не может делиться на — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть разность арифметической прогрессии натуральных чисел взаимно проста с числом Тогда числа, кратные идут в этой прогрессии с периодом (то есть существует такое что члены, кратные — это в точности ).

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

______________________________________________________________________________________________________________________________________________________

Пусть теперь — простой делитель какого-то числа из нашего набора, а — наибольшая степень делящая число набора. Пусть — число из набора, делящееся на Хотя бы член прогрессии делится на (и, как следствие, на ). Но разность прогрессии не делится на значит, лишь каждый -й её член делится на Значит, в прогрессии хотя бы членов, то есть

откуда

С другой стороны, ни один из как минимум членов прогрессии, делящихся на не делится на Это значит, что количество таких членов меньше то есть или Это противоречит неравенству выше.

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

Рассмотрим человека, который наловил больше всего рыб, назовём его Петрович.

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

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

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

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

Кроме того,

Решая систему, последовательно находим

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

Заметим следующий полуинвариант: количество плюсиков во всей таблице после операции увеличивается. Действительно, рассмотрим строчку или столбец в котором мы проводили операцию, во всей доске, кроме рассмотренной линии, количество плюсов не изменилось, а в самой линии увеличилось, поэтому и во всей доске увеличилось. Теперь поймем, что количество плюсиков не может стать больше , поэтому количество проделанных операций конечно (за каждую операцию количество плюсиков увеличивается хотя бы на 1 и ограничено числом )). Осталось теперь рассмотреть момент, когда мы не можем сделать операцию, если бы нашлась линия, в которой минусов больше чем плюсов, то мы бы смогли применить к ней операцию и увеличить число плюсов, что противоречит рассмотренному моменту.

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

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

Пусть окрашено чисел. Упорядочим их по возрастанию:

Заметим, что для любого справедливо неравенство

Действительно, в противном случае при , имеем

и мы не сможем представить в виде суммы двух красных чисел. Тогда

Значит, и . Осталось привести пример покраски 10 чисел: .

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

поэтому оба показателя возрастут. Если , то

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Докажем по индукции, что после перекладываний количества камней в кучках имеют вид

для некоторого целого числа .

База индукции при очевидна:

то есть .

Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет , а в правой останется камней, при этом , либо мы перекладываем камни из левой кучки в правую, тогда в левой останется , а в правой станет камней, при этом .

Если после некоторого -ого перекладывания раскладки останется всего одна кучка, то число камней в другой станет равным 0 , следовательно, выполнится равенство одно из равенств или . В обоих случаях N будет делителем числа , то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае . Следовательно, при любом N , отличном от степени двойки, раскладка не может быть собрана в одну кучку.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Объединяя оба случая и , получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N .

Рассмотрим множество состоящее из всех возможных -регулярных(степени всех вершин в графе равны 100) графов на данном множестве вершин (наши две схемы дорог — среди них). Докажем что любые два графа из можно перевести друг друга серией перестроек. Для двух графов пусть - множество необщих рёбер этих графов, а . Очевидно, что число всегда четно, и в множестве поровну рёбер из и

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

Итак, не умаляя общности будем считать, что все вершины различны, причем и Рассмотрим три случая.

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

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

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

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

А ещё не забудем изначальный набор по возрастанию, в котором никаких перестановок сделано не было.

Окончательно получаем

______________________________________________________________________________________________________________________________________________________

Второе решение. Подходят исходная расстановка и любая строка, полученная переносом любого числа с исходного места на любое другое. При этом перенос на соседнее место равносилен обмену местами двух соседей, то есть, может быть получен двумя способами; каждый из остальных переносов дает уникальную строку. На не соседнее место можно переставить 99 способами крайние числа 1 и 101 и 98 способами каждое из 99 остальных чисел. Учитывая, что есть 100 пар соседей, всего получаем хороших порядков .