Комбинаторика на Ломоносове: способы, логика, игры

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

Дальше рассмотрим три случая по количеству универсалов на месте защитников:

1. Среди выбранных защитников нет универсалов. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо универсалов, следовательно, способов

Следовательно, вариантов команд в этом случае

2. Среди выбранных защитников один универсал. Значит, количество так выбрать двух защитников в команду равно

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

Следовательно, вариантов команд в этом случае

3. Среди выбранных защитников оба являются универсалами. Значит, количество так выбрать двух защитников в команду равно

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

Следовательно, вариантов команд в этом случае

В итоге способов выбрать команду равно

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

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

Вопрос о целых точках на треугольнике, получается, стоит так: при каких целых система:

имеет решения , удовлетворяющие условиям выше.

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

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

Проецируем треугольник на — получается треугольник на плоскости с вершинами Внутрь него точки попадут такие:

Решаем систему, состоящую из двух первых уравнений:

Получаем следующие решения:

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

то есть должна быть чётной. Из кандидатов подойдут только .

Плюс точки на сторонах, и всего точек на треугольнике

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

Теперь берём пару отрезков. Пусть это отрезки с концами и считаем В каком случае они пересекается? В том, когда Учитывая, что могут быть любой парой, замечаем следующее: общее количество пересечений отрезков равно количеству случаев, когда в перестановке большее число стоит раньше меньшего (не обязательно по соседству). Как сказали бы старшие товарищи, число пересечений равно числу инверсий в перестановке. Так и будем говорить дальше.

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

Как посчитать число перестановок с заданным количеством инверсий? Подойдём к задаче индуктивно. В фигурных скобках будем указывать различные перестановки, а в квадратных перечислим количества перестановок, имеющих соответственно инверсий.

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

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

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

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

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

Здесь в строке (нумерация начинается с ) приводятся числа для равные количеству перестановок из чисел с инверсиями.

Вспоминая, как происходит добавление нового получим

Действительно, — количество перестановок из (n-1) чисел, в которых уже есть инверсий. В них мы вынуждены поставить новое на последнее место ( инверсий). Раз мы ставим на единственно возможное место, количество перестановок не изменится.

Далее, — количество перестановок с инверсией, и, чтобы добавить недостающую, мы вынуждены ставить на предпоследнее место ( инверсия).

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

Заметим, что так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем ) количеством инверсий.

Итак, имеем следующий способ построения коллекции

Первая строчка:

По строчке ползёт «окно» шириной Попавшие в «окно» числа складываются и выписываются в следующую (2-ю) строку:

Вторая строка:

По ней будет ползти окно шириной Сложение попавших в окно чисел даст третью строку:

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

Выпишем (без нулей) первые строк нашей коллекции и выберем в ней нужное нам

Получаем ответ

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

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

троек гномиков (первый гномик может быть выбран не более, чем способами, второй — способами, третий — способами, при этом порядок выбора гномиков не важен).

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

В каждой грани есть вершина, в которой стоит число, не меньшее 6. Действительно, в противном случае одна из троек даже из оставшихся наибольших чисел даёт сумму, меньшую (а именно тройка с суммой

Рассмотрим грань, содержащую вершину, в которой стоит число Поскольку сумма чисел, стоящих в остальных трёх вершинах, не меньше сумма всех чисел в вершинах этой грани не меньше

Пример расстановки, при которой наименьшая сумма чисел, стоящих в вершинах одной грани, равна приведён на рисунке: сумма чисел в передней грани равна

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

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

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

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

Всего в -угольнике

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

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

1) Одноцветные раскраски – их всего . (Каждый поворот на переводит их в себя)

2) Разноцветные раскраски с противоположными секторами одинакового цвета – их , по числу способов выбора пары цветов из семи. (Каждый поворот на переводит такие раскраски в себя)

3) Прочие раскраски, не переходящие в себя ни при каком повороте.

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

Тогда общее число способов раскраски, с учётом отождествлений, получается как сумма .

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

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

В итоге получаем ответ

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

Так как число делится на 5, то на 9-м месте может стоять только пятёрка. После этого нужно на оставшиеся 8 мест распределить 8 цифр: 3 семёрки, 3 тройки, пятерку и двойку. Всего перестановок будет 8!, но так как есть повторяющиеся цифры, то ответ будет:

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

Если или то номера Пети и Васи совпадут во всех клетках. Значит, и Пусть тогда где Получаем Поэтому так как аналогично с Следовательно, количество клеток, получивших одинаковые номера, равно

Так как то или, наоборот, (чтобы убедиться, что других вариантов нет, достаточно перебрать остатки по модулю 4). В любом случае,

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

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

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

Остаётся привести пример. Пусть Саша ворует шары в начале циклов, а Паша — в начале циклов. Нетрудно видеть, что разнциа между номерами циклов соответствует скорости ребят.

Если треуогльник прямоугольный с гипотенузой , то по т.Пифагора

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

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

для каждого из которых есть троек , т.е. всего способов.

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

Всего получаем способов.

Докажем, что n не может быть больше 1006. Действительно, если то в точку с координатой 1007 можно попасть только из начала отрезка. Но если блоха прыгнет из точки 0 в точку 1007, то вперёд она прыгнуть не может, так как но и обратно прыгнуть блоха тоже не может, следовательно, должна закончить свой путь в этой точке и не побывать в других.

При подходит, например, такой путь:

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

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

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

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

(a) Пусть Ваня сможет за конечное количество ходов добиться Вначале

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

Иначе Таня вынуждена сделать или и опять-таки Ваня выигрывает.

(b) Стратегия Тани — держать коэффициент при равным 10 или 11.

В этом случае значение многочлена будет не кратно трем и, следовательно, не равно нулю.

Действительно, многочлены

не кратны трем при любом целом

При остаток от деления на три равен 2; при остаток от деления на три составляет 1 и 2, соответственно; при остаток от деления на три составляет 2 и 1, соответственно.