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

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

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

(а) Для многочлена имеем

(b) Первое решение. Из условия следует, что многочлен раскладывается на линейные множители. Пусть

Тогда корнями многочлена являются числа При этом многочлен

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

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

то есть число также является корнем многочлена Но что противоречит максимальности корня Следовательно, такого многочлена не существует.

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

База индукции: при перебором убеждаемся, что .

Переход: Пусть неравенство верно для карточек каждого цвета. Докажем, что оно верно, если количество карточек каждого цвета равно . Рассмотрим, как может увеличиться сумма , если добавить по одной карточке каждого цвета.. Без ограничения общности можно считать, что белая карточка добавлена на самый верх стопки, а добавленные чёрная и красная карточки - самые верхние среди карточек своего цвета. Пусть выше первой сверху красной карточки расположено ранее лежащих чёрных, а выше первой сверху чёрной — ранее лежащих белых. Тогда белая карточка добавляет в сумму (учитывая все чёрные, лежащие под ней), чёрная карточка добавляет (учитывая все красные, лежащие под ней) и w, за счёт того, что она лежит под w старыми белыми карточками, а красная карточка добавляет не более, чем за счёт белых, лежащих под ней, и за счёт того, что она лежит под старыми чёрными карточками. Итого, . Учитывая, что , получим: .

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

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

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

Значит, мы хотим сравнить два произведения: и . Сделаем это:

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

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

Например, так:

______________________________________________________________________________________________________________________________________________________

Замечание. Проще всего такой алгоритм придумывается «с конца»: умножаем число на 2 и стираем последние двойки, как только можем.

Пример. Расставим сначала фишки на все чётные места, кроме -го (рядом по пустых), а затем — на все нечётные, кроме -го (рядом по пустых).

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

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

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

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

______________________________________________________________________________________________________________________________________________________

Замечание. Так как по условию сказано, что блоки привезли, то подразумевается, что данная ситуация возможна. Мы доказали, что ответ не более чем единственен, значит, этот единственный ответ подходит, и приводить пример не обязательно. Но можно и привести, достаточно задать вес всех блоков 10 пудов, кроме двух: самый легкий сделать 5 -пудовым, а самый тяжелый - 15 -пудовым.

Заметим, что у каждого ребенка в наборе есть буквы K, О и P, так как в данных словах эти буквы встречаются дважды, а у одного ребенка буквы не повторяются. Буквы, из которых составлялись слова, помимо и -Л, Т и H , каждая использована по одному разу. Значит, всего было использовано карточек, а у двух малышей карточек в сумме четное количество. Значит, хотя бы одна карточка не использована.

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

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

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

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

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

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

Обозначим первые слева мест в ряду буквой вторые третьи и четвёртые — и Каждый раз, выбирая детей, будем выстраивать их по убыванию роста. Сделаем это сначала с затем с и, наконец, с После первой перестановки самых низких детей окажутся в куске после второй — в после третьей — в Таким образом, самых низких детей уже расставлены правильно. Снова выполним перестановки и Они расставят в нужном порядке следующих по росту детей в куске Последняя перестановка расставит правильно самых высоких.