Комбинаторика на МВ (Финашке): графы, турниры, множества, способы

Сначала подставим число, состоящее из всех единиц, чтобы узнать их количество в

Далее будем рассматривать пятерку чисел, о которой мы будем знать количество единиц в ней, подставив число, состоящее из 5 двоек на позициях рассматриваемой пятерки. Далее в нашей пятерке зафиксируем число на произвольной позиции, относительно которого будем рассматривать пары чисел, подставляя на их позиции число 2. Таким образом, проведя 3 таких операции, мы определим число единиц в каждой такой паре. Значит, если в какой-то паре мы получили ответ, что в ней 0 или 2 единицы, то их позиции определяются однозначно. Зная, какая цифра находится на фиксированной позиции, мы однозначно определяем позиции остальных чисел. Если на все три пары мы получили ответ, что в них находится одна единица, то у нас возможны 2 варианта: либо на фиксированной позиции стоит цифра 2, а в остальных 1, либо наоборот, на фиксированной позиции стоит цифра 1. Зная количество единиц в этой пятерке, мы можем однозначно определить, какой из этих случаев выполняется.

Разбив число на 20 таких пятерок, получим, что мы определяем его за ход, но зная общее количество единиц в числе и число единиц в каждой из 19 пятерок, мы можем определить количество единиц в последней пятерке, не тратя на это ход. Следовательно, узнав характеристики 80 чисел можно однозначно определить число

Сначала покажем, что последовательностей не хватит.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример на последовательностей опишем пример в терминах графа.

Разделим чисел на две равные группы: например, и .

Отдельно расставим первые чисел в последовательностей длиной , чтобы любые числа были соседями в хотя бы одной из последовательностей. (То есть на языке графов: нужно покрыть путями полный граф на вершинах). И аналогично поступим со второй группой чисел, а потом просто “склеим” последовательности. Например, если первая последовательность в первой группе это , а первая последовательность во второй - это , то склеиваем и получаем .

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

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

Пусть отмечены красные точки , синие точки , и зеленые точки .

Поскольку для каждой точки выполняется неравенство треугольника , то

Откуда .

Аналогично, просуммировав неравенства , получим .

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

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

Первый вариант:

Второй вариант: .

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

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

Допустим, что и Тогда то есть город соединён либо с либо с Но соединён с и а — с и

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Пронумеруем места за столом по часовой стрелке от до

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

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

В итоге, если один из выбранных людей сидит на первом месте, то существует способов подобного выбора.

Общее количество выбора троих людей указанным в условии способом равно:

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

Каждых двух учеников, которые учатся в разных классах и дружат между собой, назовём смешанной парой. Поскольку каждый из 25 учеников 11 «А» входит ровно в две такие пары, то всего имеется 50 смешанных пар.

Пусть в 11 «Б» учится человек, причем ровно из них имеют ровно по одному другу в 11 «А». Из условия задачи следует, что

Кроме того, в этом классе может найтись не более одного ученика, не имеющий друзей в 11 «А».

Каждый из остальных (если такой ученик один) или (если таких учеников нет) учеников 11 «Б» входит по меньшей мере в две смешанные пары. Значит, общее число смешанных пар больше или равно

Сложив неравенства и получим откуда

С другой стороны, построим пример, показывающий, что равенство возможно. Так как то, подставив в неравенство, найдем ограничение на снизу:

Совмещая с ограничением сверху, получаем, что Возьмем Пусть ученики класса «А» — это а класса «Б» — Тогда распределение следующее:

1.

не дружит ни с кем.

2.

Каждый ученик дружит с одним из соответственно.

3.

Ученики с по (их ровно 12) дружат так: — с и — с и и так далее. А так как в таком распределении останется без второго друга, то просто сделаем и дружественной парой. Тогда у будет три друга, но это не нарушает условие.

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

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

Пусть число участников турника равно а число попавших в -ю группу равно . Тогда число сыгранных партий равно:

где

откуда

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
при и

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
при и

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
- противоречие;
- решение.
при и

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

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

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

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

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

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

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

Первым ходом Петя может, например, стереть все цифры Оставшиеся группы одинаковых цифр можно разбить на пары:

После этого Петя (относительно средней черты) повторяет ходы Васи: стирает цифры “парные” ходу Васи и в таком же количестве.

По принципу Дирихле как минимум в одном филиале как минимум 41 участник и как минимум 21 из них одного пола. Требуется доказать, что по меньшей мере 5 из этих 21 участника одного возраста.

Если это не так, то существует не более 4 участников из каждой возрастной группы. В группе из 21 человека как минимум 6 возрастных групп, и если мы возьмем по представителю из каждой возрастной группы, то получим противоречие с одним из условий задачи.

Рассмотрим случаи.

1) Код содержит комбинацию цифр . Ее можно расположить в коде тремя способами: , или . В каждом из этих возможных кодов каждую из остальных цифр можно выбрать способами. Таким образом, получается вариантов.

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

3) Код содержит комбинации и , причем комбинация расположена правее. Аналогично - вариантов. Заметим, что числа , , , мы посчитали дважды. Таким образом, чтобы открыть сейф достаточно перебрать номеров.

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