Комбинаторика на Всесибе: игры, графы, конструктивы

Отсортируем числа из множества по возрастанию:

Для любых трех последовательных чисел число по условию лежит в . Но

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

По условию числа , то есть , где - разность прогрессии.

и в силу того, что , а натуральное. Имеем единственное решение .

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

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

Тогда Вася достигает своей цели при

То есть если , то Вася не сможет выполнить задуманное.

А при Васе достаточно разрезать полоску на кусков размера и кусок размера , при этом расположить кусков размера он должен на расстояний не более клеток друг от друга и от концов. (Чего он сможет достичь, так как )

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

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

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

1) Пусть в есть «крайняя» вершина из которой выходит ровно одно ребро В графе полученном из удалением вершины и ребра число вершин равно а рёбер – не больше выполнено предположение индукции, поэтому в можно построить красный путь длины с началом в вершине и концом в вершине Тогда ребро не соединяет вершину с одной из или проведя красное ребро из в эту вершину, получим красный путь длины в

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

База индукции - случаи графов с 3 и 4 вершинами - очевидна.

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

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

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

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

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

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

Предположим, Андрей выпил менее литров, то есть смог сделать не более ходов. Тогда Маша сделала не более ходов. Значит, на данный момент выпито не более то есть не выпито хотя бы мл сока.

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

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

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

Значит, никто не может обеспечить себе победу.

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

 Если ответ угадан и приведѐн пример турнира: 1 балл.

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

Не приведѐн пример турнира: минус 1 балл.

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

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

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

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

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

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

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

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

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

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

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

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

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

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