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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Имеем

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

так как

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

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

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

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

Определим нечетное (соответственно, четное) представление как представление в виде суммы нечетного (соответственно, четного) числа различных элементов .

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

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 1. Любое положительное целое число имеет не более одного нечетного и не более одного четного представления.

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

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 2. Зафиксируем Предположим, что число не имеет четного представления. Тогда имеет четное представление, содержащее для всех целых чисел

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

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 3. Каждое достаточно большое целое число имеет четное представление.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 4. Для любых с четное представление содержит

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

_________________________________________________________________________________________________________________________________________________________________________________

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

где — сумма некоторых значений В частности,

Пусть — целое число, удовлетворяющее и Тогда показывает, что для каждого

Далее, пусть — такой индекс, что Затем,

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

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

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

может быть либо пустым, либо являться точкой, либо отрезком.