Тема Множества

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела множества

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#89261

Двое игроков ставят крестики и нолики на бесконечной клетчатой бумаге, причём на каждый крестик первого игрока второй отвечает $100$ ноликами. Докажите, что первый может добиться, чтобы некоторые четыре крестика образовали квадрат (со сторонами, параллельными линиям клеток).

Подсказки к задаче

Подсказка 1

Каким свойствами должен обладать предпоследний ход первого игрока, если последний является победным?

Подсказка 2

Ясно, что должно существовать не менее 101 свободной клетки, такие поставив крестик в любую из них, будет образован квадрат из крестиков. Довольно трудно следить за всеми клетками доски одновременно. Давайте ограничимся квадратом N на N - назовем его особенным, где N достаточно большое число (позже мы покажем, что оно существует) и будет ставить в остальные крестики в остальные поля. Наша цель - доказать, что после алгоритма заполнения остальных клеток появится искомая клетка.

Подсказка 3

Если a>=2, то за время его выполнения второй игрок поставит не менее 100N^2 ходов, следовательно, может заполнить квадрат, а значит такой алгоритм не поможет образовать искомую клетку. С другой же стороны если a<2, то при достаточно больших 100N^a < N^2, следовательно, после выполнения любого такого алгоритма в особенном квадрате еще останутся свободные клетки, что является необходимым условием для возможности победы. Теперь давайте определимся с тем, в какие клетки плоскости мы можем ставить остальные крестики.

Подсказка 4

Ясно, что в любом квадрате, который мы стремимся построить как минимум две противоположные вершины должны являться крестиками, клеток, стоящих в одной горизонтале или вертикале с клеткой особенного квадрата. Кроме этого, обе из этих клеток должны стоять на одной из диагоналей клеток нашей доски. Так, естественным будет попытка заполнить часть одной из диагоналей, которые лежат в одной вертикале/горизонтале с какой-то из клеток особенного квадрата. При каком a мы свободны заполнить по крайней мере n^a клеток этого множества, при необходимом a?

Подсказка 5

При любом a<1. Давайте не будет мелочиться и поставим в каждой из двух частей (первая часть - множество клеток, стоящих в одной вертикале с какой-то вертикалей особенного квадрата) каждой новой диагонали n^{0.99}. Это возможно, потому что каждый раз мы можем выбирать диагональ каждая клетка которой свободна. При каком a количество n^a диагоналей будет достаточно, для того, в особенном квадрате появилась клетка, для которой существует не менее 101 пары крестиков, стоящий в одной диагонале.

Подсказка 6

Пусть мы получили n^a диагоналей, в каждой из частей которой не менее n^0.99. Тогда общее количество пар крестиков, стоящих в одной диагонале, равно n^a n^{0.99} n^{0.99}, то есть n^{1.98+a}. Ясно, что если а <= 0.02, то общее количество пар меньше n^2, следовательно, возможна расстановка крестиков, когда для каждого клетки особенного квадрата стоит не более 1 квадрата - а значит искомых клеток может не найтись. Так a > 0.02. Тогда положим a = 0.03.

Подсказка 7

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

Подсказка 8

Число клетки не превосходит общего количества заполненных диагоналей - n^0.03. Сумма чисел всех клеток равна количеству пар, стоящих в одной диагонале, но в разных частях. Их количество, как было посчитано ранее, не менее n^{2.01}. Предположим противное - каждая из еще не занятых клеток имеет число не более 101. Какое противоречие теперь можно получить?

Подсказка 9

Предъявите оценку снизу для суммы чисел всех клеток особенного квадрата и покажите, что она больше, чем n^{2.01}.

Показать доказательство

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

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

Найдем натуральное число $k$ такое, что в каждом из множеств клеток $n {(i,k− i)}i=1$ и $n {(k − i,i)}i=1$ нет отмеченных.

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

Рассмотрим клетчатую бумагу после последней итерации алгоритма. Назовем множество клеток $(i,j)$ для всех $------ i,j = 1,...,n$ особенным квадратом.

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

$PIC$

Во-первых, для любой клетки $A$ число в $CA$ не превосходит числа $[n0.03]$ — количества диагоналей, на которой расставлены крестики. Во-вторых, сумма всех чисел в особенном квадрате не меньше, чем $[n1.98n0.03]= [n2.01]$ — число всевозможных пар клеток, стоящих на одной диагонали.

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

0.99 0.03 1.02 [ 1.03] 101⋅2n n = 202n < n

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

Предположим противное. Тогда существует не более $[n1.03]$ клеток, числа каждой из которых не превосходят $[n0.03],$ следовательно, в остальных $[n2]− [n1.03]$ клетках сумма не превосходит $101.$ Таким образом, сумма чисел всех клеток в особенном квадрате не превосходит

[1.03] [ 0.03] ([ 2] [ 1.03]) n ⋅ n + 101 n − n

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

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#90597

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

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 3#90601

Назовём множество арифметических прогрессий последовательным, если их длины равны, разности совпадают, а первые члены — последовательные натуральные числа. Докажите, что при любой покраске натурального ряда в $10$ цветов найдутся $100$ последовательных одноцветных арифметических прогрессий длины $1000.$

Подсказки к задаче

Подсказка 1

В задаче что-то говорится про арифметические прогрессии и покраску чисел натурального ряда. Похоже на теорему Ван дер Вардена. Найдите ее здесь.

Подсказка 2

Разбейте числа на сотни подряд идущих и примените теорему Ван дер Вардена.

Показать доказательство

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

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

Ошибка.
Попробуйте повторить позже

Задача 4#73692

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

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Показать ответ и решение

Первое решение. Возьмём натуральный ряд и разделим его на группы по $6$ чисел вида $1+ 6k,3+ 6k,6+ 6k,2+6k,4+ 6k,5+ 6k$ (в таком порядке), $k$ — целое неотрицательное. Заметим, что внутри группы суммы всех соседних составные: $4 +12k,9 +12k,8 +12k,6 +12k,9+12k.$ Все эти числа либо кратны $2$ и больше $2,$ либо кратны $3$ и больше $3.$ Расположим эти группы в порядке возрастания $k.$ Тогда число $5+ 6k$ соседствует с $1+6(k+ 1).$ Их сумма равна $12+ 12k,$ то есть она кратна $12,$ а значит тоже составная.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём алгоритм перестановки: начнём расставлять последовательные нечётные числа $1,3,5,...$ до тех пор, пока не появится такое нечётное число $2m +1,$ которое в сумме с $2$ даёт составное число. Далее расставляем подряд идущие чётные числа начиная с $2$ до тех пор, пока не появится такое чётное число $2k,$ которое в сумме с $2m + 3$ даёт составное. Далее пишем нечётные числа, начиная с $2m +3$ и т.д. Начало перестановки выглядит так: $1,3,5,7,2,4,6,9,...$

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

$1$ случай: мы выписываем нечётные числа $2s+ 1,2s+ 3,2s +5,...$ и ожидаем, пока появится число, дающее в сумме с числом $2r$ составное. Почему когда-нибудь такое число точно появится? Рассмотрим числа $2(s +r)+ 1,2(s +r)+ 3,2(s+r)+ 5.$ Нетрудно понять, что одно из них делится на $3$ и больше $3,$ то есть является составным. Значит уже после одного из чисел $2s+ 1,2s+ 3,2s+ 5$ мы сможем поставить $2r$ и продолжить выписывать чётные числа. Случай, когда мы выписываем последовательно чётные числа и ищем возможность поставить нечётное, рассматривается аналогично.

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

Ответ:

Да

Ошибка.
Попробуйте повторить позже

Задача 5#73693

Круг разделен на $2018$ секторов, и в каждом написано целое число. В один из секторов ставится фишка. Каждым ходом прочитывается число в секторе, где стоит фишка (пусть прочитано $k$ ), фишка сдвигается на $|k|$ секторов по часовой стрелке, и там, куда она придет, число увеличивается на $1.$ Докажите, что со временем все числа станут больше миллиона.

Подсказки к задаче

Подсказка

Стоит решать от противного. Пусть в секторе A фишка побывает меньше миллиона раз. Какое тогда количество раз она побывает в секторе, следующем за A? Конечное или бесконечное?

Показать доказательство

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

Заметим, что числа в секторах увеличиваются на единицу. Поэтому если сейчас в ячейке находится число с остатком $1$ при делении на $2018,$ то перед появлением в ней следующего числа с остатком $1$ при делении на $2018$ в ней появятся числа с остатками $2,3,4,...,2017,0$ при делении на $2018.$ Следовательно, если в ячейке конечное количество раз возникает число с остатком $1$ при делении на $2018,$ то в ней конечное количество раз возникнут числа со всеми другими остатками при делении на $2018.$ Таким образом, число в $B$ также всегда ограничено. Но тогда по аналогичным рассуждениям можно доказать, что число в секторе, находящемся перед $B,$ также всегда ограничено. Так мы сможем постепенно доказать это утверждение про все секторы. Получается, что во всех секторах числа ограничены, а значит фишка сделает конечное количество ходов, это противоречие. То есть такого сектора $A$ не существует.

Ошибка.
Попробуйте повторить позже

Задача 6#73694

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

Подсказки к задаче

Подсказка

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

Показать доказательство

Пусть Черномор оставит в строю богатыря, стоящего в самом начале. Далее каждого следующего богатыря он будет выбирать так. Пусть он оставил в строю $n≥ 1$ богатырей. Докажем, что после $n$ -го богатыря обязательно найдётся богатырь ростом выше, чем $n$ -й. Предположим противное, пусть все богатыри правее $n$ -го ниже его. Пусть рост $n$ -го равен $x.$ Поскольку, все богатыри имеют различный натуральный рост, то справа от $n$ -го может стоять не более $x− 1$ богатыря ростом $1,2,3,...,x− 1$ метров. Получили противоречие с тем, что количество богатырей бесконечное. Значит, Черномор сможет оставить в строю $n +1$ богатыря, что и требовалось.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#73695

Дана клетчатая доска $100× 100.$ В каждой клеточке нарисована стрелочка в одном из $4$ направлений: вниз, вверх, влево, вправо. Граница доски огорожена стеной, имеющей лишь один выход: верхнюю сторону правой верхней клетки. Жука ставят в одну из клеток. Каждую секунду жук переползает по направлению стрелочки в его текущей клетке в одну из соседних по стороне. При этом стрелочка в той клетке, откуда жук только что уполз, поворачивается на $∘ 90$ по часовой стрелке. Если двигаться в том направлении, в котором указывает стрелка, нельзя, жук остается в той же клетке, но стрелка все равно поворачивается. Возможна ли ситуация, при которой жук никогда не покинет пределы доски?

Подсказки к задаче

Подсказка

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

Показать ответ и решение

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

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 8#73697

Можно ли расставить в клетки бесконечной клетчатой плоскости натуральные числа так, чтобы каждое число встречалось ровно один раз, и чтобы любые два числа из одной строки или одного столбца были взаимно простыми?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Расстановка чисел чем-то напоминает змейку.

Показать ответ и решение

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

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

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

Ответ:

Да

Ошибка.
Попробуйте повторить позже

Задача 9#76059

По одной стороне бесконечного коридора расположено бесконечное количество комнат, занумерованных целыми числами по порядку. В комнатах живут $2016$ пианистов (в одной комнате могут жить несколько пианистов); кроме того, в каждой комнате находится по роялю. Каждый день какие-то два пианиста, живущие в соседних комнатах $K$ -той и ( $K + 1$ )-ой, приходят к выводу, что они мешают друг другу, и переселяются соответственно в ( $K − 1$ )-ую и ( $K+ 2$ )-ую комнаты (пианисты, живущие в одной комнате, друг другу не мешают). Докажите, что через конечное число дней эти переселения прекратятся.

Показать доказательство

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

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

Ошибка.
Попробуйте повторить позже

Задача 10#81860

Двое игроков ставят крестики и нолики на бесконечной клетчатой бумаге, причём на каждый крестик первого игрока второй отвечает $100$ ноликами. Докажите, что первый может добиться, чтобы некоторые четыре крестика образовали прямоугольник (со сторонами, параллельными линиям клеток).

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 11#81861

Из бесконечной клетчатой доски выкинули все клетки, обе координаты которых делятся на $100.$ Можно ли оставшуюся часть доски обойти шахматным конем?

Подсказки к задаче

Подсказка 1

Следить за тем, что конь обойдет все оставшиеся клетки бесконечной доски довольно трудно. Каким способом можно избавиться от рассмотрения бесконечности в данной задаче?

Подсказка 2

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

Подсказка 3

Ясно, что все выкинутые клетки одного цвета (пусть чёрного). Также понятно, что внутри здравого квадрата не меньше, чем [N/100]² выкинутых клеток, ведь вдоль каждой стороны точно поместится [N/100] клеток. Теперь необходимо с другой стороны оценить разность количества пройденных соответственно черных и белых клеток. Как будет выглядеть траектории движения коня внутри здравой доски?

Подсказка 4

Подсказка 5

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

Подсказка 6

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

Подсказка 7

Заметим, что количество искомых цепочек не больше, чем количество пар черных клеток из двухклеточной каёмки квадрата, которое равно 4N+8. Осталось показать, что неравенство 4N+8≥[N/100]² неверно при достаточно больших N.

Показать ответ и решение

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

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

Рассмотрим теперь цепочки, которые начинаются и заканчиваются белой клеткой, в них на одну белую клетку больше. Лишь за счёт этих цепочек конь может обойти в квадрате больше белых клеток, чем чёрных (это необходимо, поскольку часть чёрных клеток выкинули). Однако заметим, что в каждую такую цепочку конь входит из чёрной клетки двухклеточной каёмки квадрата. Аналогично выходит из этой цепочки конь в чёрную клетку двухклеточной каёмки. То есть количество таких цепочек не превосходит количества чёрных клеток в двухклеточной каёмке, которое равно $4N − 8$ (для удобства возьмём чётное $N$ ). То есть посредством этих цепочек получится пройти максимум на $4N − 8$ больше белых клеток, чем чёрных, однако разница между ними не меньше $[1 100 ⋅N]2.$ Понятно, что при выборе достаточно большого $N$ величина $4N − 8$ будет меньше $(1100 ⋅N − 1)2,$ что, в свою очередь, меньше $[1100-⋅N]2.$ Пришли к противоречию.

Ответ:

Нет

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#86830

Докажите, что множество упорядоченных пар натуральных чисел $(a,b)$ счётно.

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 13#86831

Существует ли такая последовательность $M = {a,a ,...} 1 2$ натуральных чисел, что каждое натуральное число представляется единственным образом в виде разности двух чисел из $M?$

Показать ответ и решение

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

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

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

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

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

Ответ:

Да

Ошибка.
Попробуйте повторить позже

Задача 14#92876

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

Источники: Лига открытий - 2017

Показать ответ и решение

Пусть число $1$ окрашено в красный цвет. Докажем, что все нечетные числа окрашены в красный. Пусть есть нечетные синие числа, рассмотрим наименьшее из них $n.$ Но $n= 1+ 1+ (n − 2)$ представляется в виде суммы трех красных.

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

Ответ:

Две шахматные раскраски

Ошибка.
Попробуйте повторить позже

Задача 15#82936

Можно ли так раскрасить все клетки бесконечной клетчатой плоскости в белый и черный цвета, чтобы каждая вертикальная прямая и каждая горизонтальная прямая пересекали конечное число белых клеток, а каждая наклонная прямая — конечное число черных?

Источники: ММО-2013, задача 11.4(см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Показать ответ и решение

Введем такую систему координат $Oxy,$ чтобы вертикальные и горизонтальные линии сетки имели уравнения $x =n$ ( $n$ — целое) и $y = m$ ( $m$ — целое). Раскрасим в черный цвет те и только те клетки, все точки которых удовлетворяют одному из четырех неравенств $2 2 2 y ≥x ,y ≤ −x ,x ≥y$ или $2 x≤ −y$ (см.рис.), остальные клетки покрасим в белый цвет.

$PIC$

Тогда всякая вертикальная прямая будет пересекать конечное число белых клеток между параболами $y = ±x2,$ всякая горизонтальная прямая будет пересекать конечное число белых клеток между параболами $x = ±y2.$ Заметим также, что всякая наклонная прямая будет пересекать лишь конечное число черных клеток, так как ее пересечение с каждой из областей

y ≥ x2, y ≤ −x2, x ≥y2 и x≤ −y2

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

Ответ:

Можно

Предыдущий раздел

Следующий раздел