Бесконечные конструкции (игры, клетки, множества)

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

Согласно многомерной теореме Ван дер Вардена, для любой конечной раскраски плоскости существует одноцветный гомотетичный образ квадрата. Тогда имеем одноцветный квадрат со стороной в раскраске Это означает, что все прогрессии вида: имеют одинаковый цвет в

Это означает, что для любых последовательность:

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

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

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

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

______________________________________________________________________________________________________________________________________________________

Замечание. Мы сумели обобщить теорему Ван дер Вардена на случай, в котором у нас бесконечное число цветов.

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

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

Иррациональные же числа в интервале переводим в себя же в отерзке, то есть если то

Таким образом, получаем взаимно-однозначное отображение из в

Рассмотрим множество в котором лежат все числа из увеличенные на Тогда, если то согласно условию Получается, и Отсюда условие переписывается в виде:

содержит все натуральные числа от до

если то в лежат все члены арифметической прогрессии, первый член которой равен а разность равна

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

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

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

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

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

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

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

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

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

Зададим систему координат с точкой начала отсчета в одном из центров клетки доски и осями, параллельными прямым, содержащим стороны клеток. Назовем клеткой клетку, центр которой в заданной системе координат имеет координаты

Зафиксируем натуральное число Приведем стратегию игры за первого игрока. Проведем итерации следующего алгоритма:

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

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

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

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

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

После последней итерации алгоритма в особенном квадрате не более

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Почему этот алгоритм никогда не прекратится? Предположим, что когда-то мы не сможем его продолжить.

случай: мы выписываем нечётные числа и ожидаем, пока появится число, дающее в сумме с числом составное. Почему когда-нибудь такое число точно появится? Рассмотрим числа Нетрудно понять, что одно из них делится на и больше то есть является составным. Значит уже после одного из чисел мы сможем поставить и продолжить выписывать чётные числа. Случай, когда мы выписываем последовательно чётные числа и ищем возможность поставить нечётное, рассматривается аналогично.

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

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

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

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

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

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

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

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

Идейно довольно понятно: распределение пианистов становится все более “разреженным”. Когда оно станет совсем "разреженным переселения должны прекратиться, потому что соседствующих пианистов не останется. Нужно только придать этим рассуждениям строгости.

Рассмотрим произвольные три подряд идущие комнаты (с номерами ). Если в одной из них когда-нибудь окажется пианист, то эта тройка комнат уже никогда не опустеет: чтобы покинуть эту тройку, пианист должен переселиться из -й комнаты в -ю (или из -й в -ю, что рассматривается аналогично), но тогда кто-то переселяется из -й в -ю, и на этом шаге рассматриваемая тройка комнат непуста. Разобьём весь коридор на тройки (например, тройки вида для целых ). Количество “занятых” троек не превосходит количества пианистов, то есть и “занятые” тройки не освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора. С другой стороны, сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает, поскольку Но в силу ограниченности той части коридора, где находятся пианисты, сумма квадратов номеров не может возрастать бесконечно. Значит, когда-нибудь переселения прекратятся.

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

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

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

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

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

Пусть мы смогли построить конечную последовательность такую, что:

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

Числа можно представить в виде разности двух её членов.

Число нельзя представить в виде разности двух её членов.

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

Имеем

Требуемым в условии задачи свойством обладает любое одноэлементное множество

так как

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

Покажем, что все её члены попарно различны. Если допустить, что при то, преобразуя равенство, получим откуда это невозможно. Итак, множество содержит бесконечное подмножество — последовательность (3), следовательно, множество бесконечно.

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

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