Комбинаторика на Высшей пробе: клетки, комбигео, игры, графы

Из отрезков можно сложить четырехугольник тогда и только тогда, когда . Рассмотрим четверку , заметим, что , следовательно, , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что .

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

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

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

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

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

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

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

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

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

Пойдём от противного, предположим, что такое возможно. Без ограничения общности можно считать, что число 1 покрашено в красный. Выберем произвольное число покрашенное в синий. Заметим, что тогда должно быть зелёного цвета, — синего, — зелёного и т.д. Таким образом, все числа, большие покрашены в синий или зелёный цвет. С другой стороны, так как покрашен в синий цвет, a — в зелёный, то число должно быть покрашено в красный цвет, противоречие. Значит, такое невозможно.

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

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

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

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

Легко видеть, что на каждом шаге уравновешенность доски сохраняется. А так как мы всегда можем сделать шаг в нашем алгоритме, то в конце получится шахматная раскраска.

Оценка. Приведём пример ситуации, в которой 4 дней не хватит. Пусть у каждого из 45 людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из 10 предложенных равно , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то 4 дня так, чтобы каждый узнал все новости. Но тогда существует человек , который не может присутствовать в первые два дня из этих четырёх, а также человек , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда не сможет узнать новостей . Противоречие.

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

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

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

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

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

То есть

Иными словами, в интересующей нас клетке должно стоять число

Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:

Докажем оценку

______________________________________________________________________________________________________________________________________________________

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

Перепишем в виде

Заметим, что при неравенство неверно:

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Теперь построим код таким образом: в первые 11 бит запишем те биты, которые хотим передать (первые 11 позиций будем называть информационными). В последние 4 бита запишем следующие контрольные суммы. В 12-й запишем сумму по модулю два тех из первых 11 бит, приписанное 4-значное число которых имеет 1 в первом разряде, то есть биты № 3,5,6,8,9,10,11. В 13-й — сумму тех из первых 11 бит, приписанное 4-значное число которых имеет 1 во втором разряде, в 14-й сумму бит, имеющих 1 в третьем разряде приписанного слова, в 15-й — в четвертом. Покажем, почему этот код позволяет исправить одну ошибку при передаче.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть Получатель получил кодовое слово, возможно искаженное в одном бите. Получатель точно так же по первым 11 битам посчитает 4 контрольные суммы, и сравнит их с четырьмя полученными. Если совпали все четыре — то слово дошло без искажений. В самом деле, если бы исказился контрольный бит — в нем было бы расхождение, а если информационный — то расхождения были бы во всех контрольных, в которые он входит. Аналогично, если расхождение есть ровно в одном контрольном бите, то исказился именно он. В самом деле, если исказился другой контрольный — то все информационные дошли правильно, тогда в этом контрольном расхождения бы не было; а если исказился информационный, то все контрольные дошли правильно, и тогда расхождения были бы во всех контрольных, в которые входит искаженный информационный, а таких контрольных хотя бы два (именно за этим мы приписывали комбинации нулей и единиц, содержащие хотя бы две единицы). По аналогичным соображениям если получатель видит не менее двух расхождений с контрольными битами, то искажен точно информационный. Тогда достаточно из 11 информационных позиций выбрать ту, в приписанном 4-битном слове которой единицы стоят ровно на тех местах, на которых есть расхождения с контрольными суммами — это и есть искаженная позиция.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь подумаем в других терминах, что же мы построили. У нас есть код из кодовых слов. Каждое из этих слов можно исказить 16 способами (ничего не менять, или изменить один из 15 бит). Все полученных в результате слов будут разными. В самом деле, если бы какое-то слово получалось двумя разными способами: искажением кодового слова и искажением кодового слова (в обоих случаях — не более чем в одном бите), то код бы не исправлял одну ошибку — Получатель может получить слово но в этом случае не может понять, посылали ему или Итак, все слов разные, но это означает что вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одном бите.

На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем 60-битное слово, режет его на четыре 15-битных слова Как доказано выше, для них найдутся кодовые слова такие что отличается от не более чем в одном символе. Тогда Ассистент выбрасывает из каждого кодового слова контрольные символы, получает четыре слова длины 11, то есть одно слово длины 44. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово отличающееся от исходного максимум в четырех битах — победа.

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Назовем 38-блоком следующую конструкцию: подряд стоят 38 домов, пары домов на расстоянии 19 (т.е. такие, между которыми ровно 18 других домов)покрашены в один цвет, и больше этого цвета домов нет (не только в блоке но вообще из участвующих домов); 2-блоком назовем стоящие подряд два дома, покрашенные в уникальный цвет. 84 дома надо раскрасить так: 2-блок, 38-блок, два 2-блока, 38-блок, 2-блок.

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

_________________________________________________________________________________________________________________________________________________________________________________

б) Этот же пример позволяет реализовать 42 цвета на 86 домах — в конец добавим еще два дома, цвет которых совпадает с последним 2-блоком. Теперь постараемся доказать оценку в условиях данного пункта.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Докажем еще два полезных неравенства: — иначе нет отрезка из 20 домов, в который попали оба из и — иначе каждый отрезок, содержащий , также содержит или или .

_________________________________________________________________________________________________________________________________________________________________________________

Среди первых 20 номеров ровно одна -шка, это : иначе, если там есть и , среди домов от 1 до 20 есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого (поскольку только отрезок содержит два дома первого цвета, но он содержит и два дома второго). Значит, среди первых 20 домов ровно 19 -шек. Значит, из соответствующих им -шек 18 лежат среди 19 номеров от 21 до 39 , то есть там максимум одна -шка, это может быть только . Мы доказали, что . Повторив то же самое рассуждение с другого конца, получим, что . Но это противоречит неравенству (частный случай доказанного выше для ).

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

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

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

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

Соответственно, если все точки лежат в но не в , то все вектора равны .

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Объем тетраэдра с ребром 8 есть поскольку этот тетраэдр получается если взять не соединенные ребром вершины куба с ребром Заметим, что значит если удастся тетраэдр разрезать на 64 тетраэдра с вершинами в отмеченных точках, то один из тетраэдров разбиения будет иметь объем меньше

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

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

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

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

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

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

Будем представлять партию в виде ориентированного графа: партийцев — в виде вершин, а если партиец доверяет партийцу то соединим вершину с ребром со стрелкой, направленной от к Условие того, что никакие два партийца не доверяют друг другу, эквивалентно условию того, что никакие две вершины не соединены двумя противоположно направленными ориентированными рёбрами. Будем называть это условием одного ребра.

Построим пример партии из человек, удовлетворяющей условию задачи. Разместим человек в вершинах правильного -угольника Для каждой вершины направим по ориентированному ребру из неё в каждую из пяти вершин, следующих за ней по часовой стрелке. Утверждается, что условие одного ребра выполнено. Действительно, для каждого ориентированного ребра, идущего от некоторой вершины к имеется не более вершин, следующих от к в направлении по часовой стрелке. А остальных вершин -угольника, отличных от и вышеупомянутых последовательных вершин между ними не меньше, чем и они идут последовательно от к по часовой стрелке «с другой стороны». Предположим противное: условие одного ребра не выполнено, то есть некоторая пара вершин и соединена двумя противоположно направленными рёбрами. Тогда в силу предыдущего, имеется два набора последовательных вершин, каждый из не более, чем 4 вершин: вершины одного набора идут от к по часовой стрелке, а вершины другого — от к по часовой стрелке. Следовательно, эти наборы не пересекаются, и вместе с вершинами и (итого не более, чем вершин) они покрывают все вершин -угольника. Полученное противоречие доказывает, что условие одного ребра выполнено.

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

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

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

Пусть тогда за «Локомотив» по-настоящему болеют человек, за «Зенит» — , за «Спартак» — , за «Динамо» — . Получается, что после опроса за «Локомотив» болеют , за «Зенит» болеют , за «Спартак» болеют , а за «Динамо» — . Итого: болельщиков «Локомотива» , болельщиков «Зенита» , болельщиков «Спартака» , болельщиков «Динамо» .

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

Предположим, что на поле можно разместить фигуры при , тогда можно разместить и при . Разобьём поле на 16 квадратов , тогда ровно в 12 из них будут стоять по 1 королю («к»), а в 4 других - 12 коней-лошадей («л») и 1 мяч, т.е. 13 фигур, значит, пустых квадратов быть не должно. Соответственно, квадраты будем называть к-квадраты и л-квадраты. Заметим, что если хотя бы в одном из л-квадратов две «л» стоят у общей стороны с другим квадратом, то этот соседний квадрат не будет содержать «к», значит, он должен быть л-квадратом, но тогда в сумме в этих двух квадратах разместится не более 4 фигур, т.к. клетки прямоугольника разбиваются на пары в виде хода «л», а во всех 4 л-квадратах разместится не более фигур, а должно быть 13. Кроме того, не существует л-квадратов с 4 «л» (аналогичные рассуждения). Значит, в каждом л-квадрате будет ровно 3 «л» и никакие 2 «л» не могут стоять парой у общей стороны с другим квадратом, следовательно, такие л-квадраты находятся в углах поля и 3 «л» стоят с краю всего поля, причём в одном из них ещё стоит и мяч.

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

Для уже можно построить пример. Отметим слоном мяч и поставим королей и коней.