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

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

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

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

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

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

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

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

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

Задача 21#86830Максимум баллов за задание: 7

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

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

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

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

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

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

Задача 22#86831Максимум баллов за задание: 7

Существует ли такая последовательность $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,$ мы получили. Аналогичными рассуждениями мы сможем строить последовательность сколь угодно долго, что и требовалось.

Ответ:

Да

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

Задача 23#108271Максимум баллов за задание: 7

При обработке числовых данных часто приходится вычислять среднее арифметическое

S(x,y)= (x +y)∕2

и решать уравнения, содержащие среднее арифметическое. Найдите все конечные (состоящие из конечного числа элементов) числовые множества $X$ такие, что для любых $a$ и $b$ из $X$ множество $X$ содержит корень $x$ уравнения

S(a,x)=b.

Источники: Надежда Энергетики - 2020, 11.4 (см. www.energy-hope.ru)

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

Подсказка 1

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

Подсказка 2

Подходит ли одноэлементное множество?

Подсказка 3

А давайте предположим, что у нас есть хотя бы 2 различных элемента. Какому равенству будет удовлетворять x?

Подсказка 4

x = 2a - b. То есть мы только что построили новый элемент нашего множества. Давайте строить дальше, используя найденные новые элементы множества ;)

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

Имеем

S(a,x)= b⇔ x= 2b− a. (1)

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

X = {a}, a∈ (− ∞;∞ ), (2)

так как $S(a,a)= a.$

Допустим далее, что множество $X$ содержит по крайней мере два различных элемента $c,d,$ причем $c< d$ (без ограничения общности). Для уравнения $S(d,x)= c$ находим, согласно (1), $x =2c− d.$ Затем для уравнения $S(d,x)= 2c− d$ получаем $x= 4c− 3d,$ после чего рассматриваем уравнение $S(d,x)= 4c− 3d$ и получаем $x= 16c− 15d.$ Продолжая таким же образом, получаем последовательность решений

c,2c− d,4c− 3d,16c− 15d,... (3)

Покажем, что все её члены $xn =2nc− (2n − 1)d, n =0,1,2,...$ попарно различны. Если допустить, что $xn =xm$ при $n ⁄=m,$ то, преобразуя равенство, получим $(2m − 2n)c= (2m − 2n)d,$ откуда $c= d,$ это невозможно. Итак, множество $X$ содержит бесконечное подмножество — последовательность (3), следовательно, множество $X$ бесконечно.

Ответ:

в точности все одноэлементные множества $X ={a},a∈(−∞; ∞).$

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

Задача 24#92876Максимум баллов за задание: 7

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

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

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

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

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

Ответ:

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

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

Задача 25#103207Максимум баллов за задание: 7

Пусть $S$ — некоторое непустое множество натуральных чисел. Будем говорить, что натуральное число $n$ является чистым, если оно имеет единственное представление в виде суммы нечетного числа различных элементов из $S.$ Докажите, что существует бесконечно много натуральных чисел, которые не являются чистыми.

Источники: IMO shortlist - 2015, C6

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Доказательство. Сначала мы покажем, что каждое целое число $n$ имеет не более одного четного представления. Поскольку $S$ бесконечно, существует $x ∈S$ такое, что $x> max{n,N}.$ Тогда число $n+ x$ должно быть чистым, и $x$ не должно фигурировать ни в одном четном представлении $n.$ Если $n$ имеет более одного четного представления, то мы получаем два различных нечетных представления $n+ x,$ добавляя $x$ к четным представлениям $n,$ что невозможно. Следовательно, $n$ может иметь не более одного четного представления. Аналогично, существуют два различных элемента $y,z ∈S,$ таких что $y,z > max{n,N}.$ Если $n$ имеет более одного нечетного представления, то мы получаем два различных нечетных представления $n+ y+z,$ добавляя $y$ и $z$ к нечетным представлениям $n.$ Это снова противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 2. Зафиксируем $s∈S.$ Предположим, что число $n> N$ не имеет четного представления. Тогда $n+ 2as$ имеет четное представление, содержащее $s$ для всех целых чисел $a >0.$

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Доказательство. Зафиксируем любой $s ∈S,$ и пусть $r$ — произвольный элемент в ${1,2,...,2s}.$ Тогда из свойства $2$ следует, что множество $Zr = {r+ 2as:a ≥0}$ содержит не более одного числа, превышающего $N,$ и не имеющего четного представления. Следовательно, $Zr$ содержит конечное число натуральных чисел без четного представления, как и $ℕ = ⋃2rs=1Zr.$

Учитывая свойства $1$ и $3$ , мы можем предположить, что $N$ выбрано таким образом, что каждое $n> N$ имеет ровно одно нечетное и ровно одно четное представление. В частности, каждый элемент $s> N,s∈ S$ имеет четное представление.

_________________________________________________________________________________________________________________________________________________________________________________

Свойство 4. Для любых $s,t∈S$ с $N < s< t$ четное представление $t$ содержит $s.$

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

_________________________________________________________________________________________________________________________________________________________________________________

Пусть $s1 < s2 < ...$ — все элементы $S,$ и зададим $∑n σn = i=1si$ для каждого неотрицательного целого числа $n.$ Зафиксируем целое число $k$ таким образом, что $sk > N.$ Тогда из свойства $4$ следует, что для каждого $i> k$ четное представление $si$ содержит все числа $sk,sk+1,...,si−1.$ Следовательно,

si = sk+sk+1+ ...+ si−1+ Ri = σi−1− σk−1+ Ri (1)

где $R i$ — сумма некоторых значений $s ,...,s . 1 k−1$ В частности, $0≤ R ≤ s +...+s = σ . i 1 k−1 k−1$

Пусть $j0$ — целое число, удовлетворяющее $j0 > k$ и $σj0 > 2σk− 1.$ Тогда $(1)$ показывает, что для каждого $j >j0,$

sj+1 ≥ σj − σk−1 > σj∕2 (2)

Далее, пусть $p> j0$ — такой индекс, что $Rp = mini>j0Ri.$ Затем,

sp+1 = sk+ ...+ Rp+1 = (sp− Rp)+sp+ Rp−1 ≥ 2sp

Таким образом, в $S$ нет элемента, большего, чем $sp,$ но меньшего, чем $2sp.$ Отсюда следует, что четное представление $τ$ для $2sp$ не содержит ни одного элемента, большего, чем $sp.$ С другой стороны, неравенство $(2)$ приводит к $2sp> s1 +...+ sp−1,$ поэтому $τ$ должно содержать слагаемое, большее, чем $sp−1.$ Таким образом, оно должно содержать $sp.$ После удаления $sp$ из $τ$ мы получаем, что $sp$ имеет нечетное представление, не содержащее $sp,$ что противоречит свойству $1,$ поскольку само $sp$ также формирует нечетное представление $sp.$

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

Задача 26#82936Максимум баллов за задание: 7

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

Источники: ММО-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

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

Ответ:

Можно