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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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