Тема КОМБИНАТОРИКА

Множества → .04 Аддитивная комбинаторика

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

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

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

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

Подтемы раздела комбинаторика

Разделы подтемы Множества

Соответствия, сравнения, количества

Формула включений-исключений

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

Аддитивная комбинаторика

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

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

Задача 1#104770

Пусть $A$ и $B$ — два множества вычетов по простому модулю $p.$ Определим сумму $A+ B = {a +b|a ∈A,b∈ B}.$ Докажите, что тогда выполнено $|A +B |≥min(p,|A |+|B|− 1).$

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

Разберем случай, когда $min(p,|A|+ |B|− 1)=p,$ то есть $|A |+ |B |>p.$ Достаточно показать, что при этом $|A + B|= p,$ то есть множество $A +B$ содержит каждый вычет. Предположим противное, тогда существует остаток $r∈∕A +B,$ в этом случае для любого $i$

(i,r− i) ∕∈A ×B

т.е. $i$ не принадлежит $A$ или $r− i$ не принадлежит $B,$ следовательно, количество элементов $A+ B$ не превосходит числа $p$ количество пар, чем получено противоречие.

Если мощность хотя бы одного из множеств равна $1,$ без ограничений общности можем считать, что это множество $A,$ то неравенство так же верно, поскольку $|A+ B|≥ B = |A|+|B|− 1.$

Таким образом, осталось проверить неравенство при $|A|,|B|> 1,$ для которых $|A|+ |B|≥ p.$ Вернемся к доказательству исходного утверждения. Предположим противное, то есть существует непустое множество пар множеств вычетов $A,B,$ для которых выполнены условия выше и неверно доказываемое неравенство. Сформулируем и докажем два предложения.

Предложение 1. Пусть дано целое число $c$ и $Ac = {a+ c | a∈ A},$ тогда

|A +B |= |Ac+ B|

Доказательство. Существует биекция между множествами $A+ B$ и $Ac +B,$ которая каждому остатку $x$ первого множества ставит в соответствие остаток $x +c$ второго.

Предложение 2. Пусть $AB$ — множества вычетов, причем $1<|A|≤ |B|< p.$ Тогда существует целое число $c,$ для которого

0<|Ac∩ B|< |Ac|

Доказательство. Пусть $x$ — произвольный элемент $A,r$ — элемент $B,$ тогда множество $A r−x$ пересекается с $B$ хотя бы по одному элементу. По условию, $A$ содержит еще по крайней один элемент, пусть разность между ним и $x$ равна $k.$ Если элемент $x+ k$ не лежит в $B,$ то искомое значение $c$ найдено, иначе лежит. Рассмотрим следующий процесс, на каждом шаге которого ко всем элементам текущего множества будем добавлять $k.$ Достаточно показать, что существует момент времени $t,$ при котором ровно один из элементов $x+ tk,x+ (t+ 1)k$ содержатся в множестве $B.$

Предположим противное. Если при этом существует момент, когда ни один из данных элементов не лежит в $B,$ то мы можем рассмотреть момент $t 0$ перед тем, когда это случилось впервые, но тогда в момент $t − 1 0$ в $B$ лежит ровно один из них.

Иначе, в любой момент времени, каждый из них лежит в $B.$ Но в силу простоты $p,$ множество ${x+ tk | t∈ℕ}$ образует множество всех остатков, что невозможно, поскольку $|B|< p.$

Предложение 3. Если $A ∩B ⁄=∅,$ то

A∩ B +A ∪B ⊆ A+ B

Доказательство. Достаточно показать, что произвольный элемент $z$ множества $A ∩B + A∪ B$ лежит в $A +B.$ Элемент $z$ представим в виде суммы $x+ y,$ где $x∈A ∩B; y ∈ A ∪B,$ без ограничений общности можем считать, что $y ∈ B,$ но тогда $x∈ A$ и вычет $x+ y ∈ A+ B.$

______________________________________________________________________________________________________________________________________________________

Вернемся к доказательству задачи. Из множества пар множеств $A,B$ выберем такую, что мощность множества меньшей мощности минимальна по всем парам. Без ограничений общности, $|A|≤ |B |,$ но тогда, в силу предложения $2,$ существует целое $c$ при котором

0<|Ac∩ B|< |Ac|

Тогда, по предложению $1$ и предложению $3,$ поскольку множество $A ∩ B c$ непусто,

|Ac|+ |B |− 1= |A |+|B|− 1 >|A+ B|= |Ac +B|≥ |Ac ∩B |+ |Ac ∪B|

при этом $|Ac∩ B|< |Ac|,$ а значит, существуют множества вычетов $Ac ∩B$ и $Ac ∩B,$ для которых неравенство по прежнему неверно, а мощность минимального из множеств меньше, чем $A$ , чем получено противоречие с минимальностью.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Утверждение задачи суть теорема Коши-Дэвенпорта. Известно следующее утверждение, в доказательстве которого она полезна.

Утверждение. Сравнение $x2 +y2 ≡ k$ по простому модулю $p$ имеет решение для любого $k.$

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

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

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

Задача 2#85751

Пусть $n,m$ — натуральные числа, $n< m.$ Костя взял $2m$ карточек и выписал все подмножества множества ${1,2,...,m},$ каждое — на лицевой стороне отдельной карточки. Оказалось, что как ни разложи эти карточки на две кучи, всегда удается выбрать в одной из куч $n 2$ карточек и выписать на их обратных сторонах все подмножества ${1,2,...,n}$ (по одному на карточке) так, что записи на всех выбранных карточках окажутся согласованными: для любых двух карточек $(A,a),(B,b)$ (где $A,B$ — записи на лицевых сторонах, $a,b$ — на обратных) верно, что если $a ⊂b,$ то $A ⊂ B.$ Докажите, что $m ≥2n.$

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

Заметим, что на обратных сторонах карточек встречается возрастающая по включению последовательность из $n+ 1$ множеств:

∅⊂ {1}⊂ {1,2}⊂ {1,2,3} ⊂...⊂{1,2,...,n} (∗)

Если $m ≤2n− 1,$ разложим карточки на две кучи: в одной куче карточки, на лицевой стороне которых выписаны множества с четным числом элементов, а в другой — с нечетным. Тогда в каждой из куч величина «число элементов множества на лицевой стороне карточки» принимает лишь $n$ различных значений, поэтому ни в одной из куч на лицевых сторонах карточек не найдётся согласованная с последовательностью ( $∗$ ) возрастающая цепочка из $n+ 1$ множества. И даже более цинично: расслоим карточки на 2n слов по числу элементов, после чего $n$ слоев целиком помещаем в одну кучу, а другие $n$ слоев в другую. Ни одна из куч не содержит цепь длины $n +1.$

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

Задача 3#82284

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

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

Подсказка 1

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

Подсказка 2

Верно! Если мы берем i+1 чисел, то по предположению индукции среди первых i уже есть не менее i различных остатков. Как из них построить новый остаток?

Подсказка 3

Точно! Прибавим ко всем имеющимся i остаткам новое (i+1)-ое число. Тогда мы снова получим i различных остатков. Могут ли все они совпасть с первыми i остатками?

Подсказка 4

Попробуем рассмотреть сумму всех вновь получившихся чисел. Она сравнима с суммой имеющихся i остатков. Могло ли так получиться?

Подсказка 5

Очевидно, это невозможно, ведь это противоречит взаимной простоте (i+1)-го числа и n. Какой вывод можно теперь сделать?

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

Докажем индукцией по $i,$ что среди сумм всевозможных подпоследовательностей $a,a ,...,a 1 2 i$ есть хотя бы $i$ различных остатков по модулю $n.$ Для $i= 1$ это очевидно, так как $a1$ даёт один остаток.

Пусть утверждение верно для $i$ чисел ( $i< n$ ), добавим к ним $ai+1.$ Пусть до этого среди сумм подпоследовательностей встречались различные остатки $r1,r2,...,ri.$ Рассмотрим остатки

r1+ ai+1,r2 +ai+1,...,ri+ai+1

Ясно, что они различные. Предположим, что это просто перестановка остатков $r,r,...,r. 1 2 i$ Тогда получаем, что

r1 +r2+ ...+ ri ≡ (r1 +ai+1)+ (r2 +ai+1)+ ...+ (ri+ ai+1)≡ r1+r2+ ...+ ri+ iai+1 (mod n)

Получается, что $iai+1$ кратно $n.$ Однако $i< n,$ а значит, $(n,ai+1)> 1,$ что противоречит условию. Следовательно, среди чисел

r1+ ai+1,r2 +ai+1,...,ri+ai+1

есть новый остаток. Переход доказан.

Тогда среди сумм всевозможных подпоследовательностей чисел $a1,a2,...,an$ есть любой остаток по модулю $n,$ что и требовалось.

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

Задача 4#82297

Пусть $p$ — простое число. Дано множество $S$ из $2p − 1$ чисел, причем остатки чисел $a,a ,...,a 1 2 n$ попарно различны. Докажите, что в $S$ существует подмножество из $p$ элементов с суммой, делящейся на $p,$ содержащее не более одного числа из $a1,a2 ...,an.$

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

Подсказка 1

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

Подсказка 2

Верно! Все остатки чисел a₁, a₂, ... можно объединить во множество A₁, чтобы в будущем применить теорему Коши-Дэвенпорта (это гарантирует, что они будут входить ровно 1 раз в суммы). А как распределить остальные числа?

Подсказка 3

Точно! Можно распределить остальные числа в p-1 множество A₂, ... A_p. А именно, будем брать остаток и последовательно его класть в множества A₂, ..., A_p и так для каждого остатка(почему всё будет хорошо?). Какой теперь можно сделать вывод по теореме Коши-Дэвенпорта?

Подсказка 4

Верно! Тогда мощность суммы построенных p множеств не меньше p. А что это означает?

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

Заметим, что если какой-то остаток встречается $≥ p$ раз, то мы можем взять этот остаток $p$ раз и условие будет выполнятся. Будем считать, что каждый остаток встречается меньше $p$ раз. Давайте положим в множество $A1$ элементы $a1,a2...an.$ Теперь будем последовательно заполнять множества $A2,...Ap$ оставшимися остатками. А именно, будем брать остаток и последовательно его класть в множества $A2,...Ap$ и так для каждого остатка. Заметим, что два раза мы в одно множество один и тот же остаток положить не можем, так как тогда этого остатка было бы хотя бы $p$ штук. Также заметим, что пустых множеств не будет, ведь у нас остался хотя бы $p− 1$ элемент (в силу того, что $n≤ p).$ Тогда по теореме Коши-Дэвенпорта получаем, что

∑ |A1+ A2+ ...+ Ap|≥min(p, |Ai|− p+1)= min(p,2p− 1 − p+ 1)= p

Что и требовалось.

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

Задача 5#82298

Пусть $S$ — множество из $502$ чисел, причем оно содержит ровно $10$ различных по модулю $541.$ Докажите, что в $S$ найдется подмножество с суммой, делящейся на $541.$

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

Подсказка 1

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

Подсказка 2

Верно! Они точно отличаются от всех 502-m сумм последних r элементов, где r не меньше m+1. Попробуем теперь выбрать m с хорошим свойством: так, чтобы можно было гарантировать, что первые m членов будут определять достаточно большое количество различных сумм. Какое число сумм, зависящее от m, можно наверняка гарантировать?

Подсказка 3

Докажем, что можно гарантировать не менее m+39 сумм! Как это можно показать?

Подсказка 4

Всего в последовательности только 10 различных элементов, а потому есть и ненулевой элемент, входящий не менее 51 раза (если бы он был нулевым, то задача не имела бы смысла). Можно ли теперь сделать так, чтобы работать не с абстрактным элементом a, встречающимся 51 раз, а с более конкретным?

Подсказка 5

Конечно! Очевидное сведение к случаю a = 1 состоит в том, что можно разделить на обратный элемент к ненулевому a все числа последовательности. Тогда остальные числа можно считать просто какими-то числами от 1 до 540 (поскольку нас интересуют только ненулевые остатки по модулю 541). Попробуем теперь рассмотреть два случая: найдется число большее 51 и все числа не превосходят 51. Что можно сказать о наборе во втором случае?

Подсказка 6

Точно! В виде сумм наших чисел представимы все натуральные числа от 1 до суммы всех чисел. Однако самая большая из таких сумм не меньше суммы первых 10 натуральных чисел и 492. Тогда вся сумма больше 541, что невозможно! Перейдем к первому случаю. Каким ограничениям удовлетворяет число, большее 51?

Подсказка 7

Верно! Оно точно меньше 488, ведь у нас в запасе есть 51 единица (после деления на a в множестве остатков по модулю 541). Какое теперь можно выбрать m, чтобы получить не менее m+39 различных сумм первых m членов?

Подсказка 8

Точно! Положим m = 52. Тогда у нас на самом деле есть не менее 103 различных сумм. Решена ли теперь задача?

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

Число $502$ будем для ясности обозначать через $n,$ а $541$ — через $n +39.$ Пусть $a ,a ,...,a 1 2 n$ — данная последовательность. Допустим, что никакая её подпоследовательность не даёт в сумме $0.$ Пусть $1≤ m≤ n$ — некоторое число. Заметим, что тогда все суммы, которые можно получить, выбирая слагаемые только из $m$ первых членов последовательности, отличны от всех $n− m$ сумм вида $∑r i=1ai,$ где $m + 1≤ r≤n$ (иначе вычтем одну сумму из другой — останется как раз подпоследовательность c суммой, кратной $541).$ Покажем, что можно выбрать $m$ так, что первые $m$ членов последовательности будут определять не менее $m +39$ различных сумм.

Так как в последовательности встречается всего $10$ различных элементов, какой-то элемент $a⁄= 0$ входит в неё не менее $51$ раза. Так как $541$ — простое число, в $Z541$ возможно деление (засчёт взятия обратного остатка), значит, мы можем поделить все элементы последовательности на $a;$ результат каждого деления можно интерпретировать как число от $1$ до $540.$

Таким образом, мы можем считать, что $a1 = a2 = ...= a51 = 1,$ а остальные элементы последовательности — какие-то натуральные числа от $1$ до $540.$ Если ни одно из чисел $ai$ не превосходит $51,$ то в виде сумм чисел $ai$ представимы все натуральные числа от $1$ до $∑ ni=1ai,$ последняя сумма никак не меньше чем сумма первых $10$ натуральных чисел плюс $n − 10.$ Все вместе — больше $n +39.$ Противоречие.

Если же в последовательности имеется число, большее $51,$ мы можем считать, что $a52 > 51.$ (При этом $a52 <488,$ так как иначе при помощи $a52$ и нескольких единиц можно сразу получить подпоследовательность с суммой, кратной $541$ ) Полагая $m =52,$ мы видим, что первые $m$ членов последовательности представляют не менее $m +51$ сумм, что и требовалось.

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

Задача 6#82299

Опишите все множества из $n− 2$ элементов, для которых не найдется подмножества с суммой, делящейся на $n.$

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

Подсказка 1

Будем считать, что n≥6. Тогда можно рассмотреть множество из каких-нибудь n сумм чисел из множества, причём никакая из этих сумм не даёт остаток 0, так что найдутся две совпадающие по модулю n.

Подсказка 2

Если в этом множестве будут префиксные суммы перестановки множества (а₁+а₂+а₃, а₁+а₂+а₃+a₄, ...), то они между собой совпасть по модулю не могут. Добавим к ним, например, а₁, а₂, а₁+а₃ и а₂+а₃.

Подсказка 3

Такие суммы позволяют нам понять, что независимо от выбора а₃ оно совпадёт по модулю n с разностью а₁-а₂, так что почти все числа должны совпадать. Аналогично, можно получить и совпадение всех чисел с а₂.

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

Случаи $n ≤5$ разбираются вручную. Пусть есть элементы $a ⁄=a . 1 2$ Для любого другого элемента $a 3$ рассмотрим суммы $a1,a2,a1+ a3,a2+ a3$ и

a1+ a2+ a3,a1+ a2+a3+ a4,...,a1+ a2+a3+ ...+ an−2

Их $n$ штук, значит, какие-то две дают один и тот же остаток при делении на $n.$ Если одна из этих сумм имеет вид $a1 +a2+ a3+ ...,$ то их разность делится на $n$ и является суммой какой-то подпоследовательности, пришли к противоречию.

Следовательно, возможны только следующие равенства: $a = a + a 1 2 3$ и $a =a + a , 2 1 3$ то есть $a = ±(a − a) 3 1 2$ для любого элемента $a . 3$ Если в множестве есть как элемент $a − a, 1 2$ так и $a − a , 2 1$ то их сумма равна $0,$ что противоречит условию. Значит, одновременно для всех элементов $a3$ реализуется один и тот же знак. Таким образом, все элементы последовательности, кроме $a1$ и $a2,$ равны некоторому числу $a.$

Предположим, что хотя бы одно из чисел $a1$ и $a2$ не равно $a,$ например, $a1.$ Тогда для чисел $a1$ и $a$ можно проделать аналогичные рассуждения, то есть все остальные числа будут также равны $a.$ То есть при $n> 5$ получаем $a2 =a3 = ...=an−2 = a.$ Также заметим, что условие $a3 = ±(a1− a2)$ выполняется лишь когда $a1 = 2a.$ Также подходит случай, когда оба числа $a1$ и $a2$ равны $a.$

Ответ:

Либо все числа равны между собой, либо $n− 3$ числа равны между собой, а оставшееся в два раза больше.

Курсы

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

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

Задача 7#82301

Пусть $k$ и $r$ — натуральные числа и пусть $A = {a,...,a } 1 k+r$ —множество целых чисел, причём ( $r≤ k− 1$ ). Докажите, что если в $A$ нельзя выбрать $k$ элементов, сумма которых делится на $k,$ то существует не меньше $r+1$ различного остатка по модулю $k,$ которые принимают суммы из $k$ элементов множества $A.$

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

Подсказка 1

Добавление ко всем элементам множества по k не меняет задачи, так что можно считать, что чаще всего встречаются нули и их l(какая для l оценка?). Пусть самая длинная подпоследовательность длины меньше k без нулей и с суммой, кратной k, имеет длину s. Тогда l+s≤k-1, значит, оставшихся элементов хотя бы r+1.

Подсказка 2

Выберем r элементов из этого остатка, разобьём их на подмножества, состоящие из различных элементов, их получится не более чем l. Теперь добавим в каждое из этих множеств 0. Теперь к этим множествам можно применить теорему Кемпермана-Шерка.

Подсказка 3

Сформулируем теорему Кемпермана-Шерка: Пусть n — натуральное число, A и B — два подмножества последовательностей из d вычетов по модулю n, содержащие 0, и пусть уравнение a +b= 0, где a∈ A,b∈B, имеет относительно a и b единственное решение a=b=0. Тогда |A+B| ≥ min{n^d, |A|+|B|-1}. Для её доказательства можно рассмотреть наименьшее А, которое противоречит условию задачи.

Подсказка 4

Чтобы завершить доказательство теоремы нужно найти в B элемент b такой, что A+b не вложено в B. Тогда уберём из А все элементы a такие, что a+b не лежит в B, и перекинем в B числа (a+b). Тогда мы нашли меньшее множество A', которое тоже удовлетворяет условиям теоремы.

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

Если прибавить к каждому элементу $A$ одно и то же число, остатки сумм из $k$ элементов при делении на $k$ не поменяются, поэтому можно считать, что наибольшую кратность имеет $0.$ Обозначим через $L$ подпоследовательность $A,$ состоящую из всех нулей; пусть $l$ — количество элементов в $L.$ Ясно, что $l≤k− 1.$ Среди всех подпоследовательностей $A ∖L$ длины не более $k − 1$ выберем самую длинную подпоследовательность $S$ с суммой, кратной $k,$ обозначим ее длину через $s$ (возможно, $S =∅$ и $s= 0).$

Тогда $l+ s≤ k− 1,$ так как в противном случае, дополнив $S$ нескольким нулями, мы получили бы подпоследовательность из $k$ элементов с суммой, кратной $k.$ Итак, в последовательности $A∖(L ∪S)$ не меньше $r+1$ элементов. Возьмем любые $r$ из них, пусть они образуют последовательность $T.$ Пусть $h$ — наибольшая кратность элемента в $T.$ Тогда $h ≤l$ по определению числа $l.$ Разобьем $T$ каноническим образом в объединение $h$ непересекающихся множеств (не последовательностей!) $X1,...,Xh$ и положим $X ′i =Xi ∪0(i=1,...,h).$ Заметим теперь, что $0$ не принадлежит $T$ и что при $1 <j ≤h$ никакие $j$ элементов $T$ не дают в сумме $0.$ Действительно, так как $j +s≤ h+ s≤ l+s≤ k− 1,$ то если бы какие-то $j$ элементов из $T$ давали бы в сумме $0,$ мы могли бы объединить эти элементы с $S$ и получили бы более длинную подпоследовательность с суммой, кратной $k,$ что противоречит определению $S.$ Таким образом, мы проверили, что к набору $X1′,...,X′h$ можно последовательно применять теорему Кемпермана-Шерка (докажем её ниже), что даёт нам неравенство

|X1′+...+ X′h|≥ |X1|+ ...+ |Xh|+ 1= r+ 1

Иными словами, если к последовательности $T$ добавить $h$ нулей из $L,$ то полученная последовательность имеет не меньше $r+1$ различных сумм из $h$ элементов, кратных $k.$ Добавив оставшиеся элементы $A$ (а их в точности $k+ r− (r+ h))$ к каждой из этих сумм, мы получим $r+ 1$ различных сумм из $k$ элементов, кратных $k.$

______________________________________________________________________________________________________________________________________________________

Теорема Кемпермана — Шерка. Пусть $n$ — натуральное число, $A$ и $B$ — два подмножества $ℤdn,$ содержащие $0,$ и пусть уравнение $a +b= 0,$ где $a∈ A,b∈B,$ имеет относительно $a$ и $b$ единственное решение $a= b= 0.$ Тогда

|A +B|≥ min{nd, |A|+ |B|− 1}

Доказательство. Можно считать, что $|A|+|B|− 1 ≤nd.$ Среди всех пар $A,B,$ противоречащих утверждению задачи, выберем такую, в которой величина $|A |$ наименьшая. Заметим, что существует элемент $b∗$ из $B,$ такой что $b∗+A$ не является подмножеством $B.$ Действительно, если бы это было не так, то для ненулевого элемента $a1$ из $A$ мы бы имели равенство $a1+B = B$ и, в частности, так как $0$ лежит в $B,$ мы бы нашли нетривиальное представление $a1+ bi = 0,$ что противоречит условию. Воспользуемся элементом $b∗,$ чтобы перестроить имеющуюся пару множеств. А именно, пусть $A∗$ — это множество всех таких $a$ из $A,$ для которых $a+ b∗$ не лежит в $B.$ Положим $A′ = A∖A∗,B′ = B ∪(b∗+A∗).$

Ясно, что $0$ не лежит в $A ∗,$ поэтому по-прежнему $0$ лежит в $A′.$ Очевидно, $0$ лежит в $B′.$

Уравнение $a′+b′ = 0$ для множеств $A′,B ′$ имеет только тривиальное решение. Действительно, если нашлось нетривиальное решение $a1+ (b∗+a2)=0,$ где $a1$ лежит в $A′,a2$ лежит в $A∗,$ то тогда и $(a1+ b∗)+ a2 =0,$ что невозможно, так как $a1+ b∗$ лежит в $B,a2$ лежит в $A,a2 ⁄= 0,$ а нетривиальных разложений нуля для множеств $A$ и $B$ не существует.

Наконец, отметим, что $A′+ B′ ⊂ A+ B.$

Итак, мы построили новую пару множеств $A ′,B′,$ противоречащую утверждению задачи, но при этом $|A′|< |A|.$ Противоречие.

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

Задача 8#82302

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

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

Подсказка 1

Добавление ко всем элементам множества по k не меняет задачи, так что можно считать, что чаще всего встречаются нули и их h. Решая от противного, предположим, что h≤p-k. Тогда оставшихся элементов хотя бы p, а их сумма s. Можно доказать, что можно выбрать не более h элементов так, что их сумма сравнима с s по модулю p.

Подсказка 2

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

Подсказка 3

Давайте выкинем элементы, которые в сумме дают s. Тогда оставшиеся элементы в сумме делятся на p, причём их осталось хотя бы p-h. Тогда их осталось больше, чем p. Мы получили меньшее по размеру множество, аналогичное предыдущему.

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

Если прибавить к каждому элементу некоторое число, то все суммы по $p$ элементов будут давать такой же остаток при делении на $p,$ как раньше. Следовательно, мы можем считать, что наибольшую кратность $h$ имеет $0.$ Пусть $T$ — последовательность из ненулевых элементов, $s$ — его сумма. Допустим, что условие задачи неверно и $h ≤p − k.$ Тогда $|T|≥p.$

Докажем, что $s$ можно представить в виде суммы не более чем $h$ элементов из $T.$ Распределим элементы $T$ по $h$ непересекающимся множествам $A1,A2,...,Ah.$ Для этого определим $Ai$ как множество тех элементов $T,$ которые входят в $T$ с кратностью не меньше $i.$ При этом $A1$ содержит все различные элементы последовательности. Суммы не более чем по $h$ элементов образуют множество $∑h A1 + i=2(Ai∪ 0).$ По теореме Коши-Дэвенпорта имеем:

h |A1 +∑ (Ai∪ 0)|≥ min(p,|A1|+ |A2 ∪0|+...+|Ah∪ 0|− h+ 1)=p i=2

Итак, $s$ можно представить в виде суммы не более чем $h$ элементов из $T.$ Пусть $Q$ — последовательность, состоящая из этих не более чем $h.$ Положим $T1 =T ∖Q.$ Ясно, что сумма элементов $T1$ кратна $p$ и $p− h≤ |T1|≤ |T|− 1.$ Если бы оказалось, что $|T1 ≤ p|,$ то мы бы легко составили подпоследовательность из $p$ элементов, кратных $p,$ добавив к $T1$ несколько элементов, кратных $p.$ Следовательно, $|T1|> p.$ Применим снова утверждение, доказанное выше, и построим подпоследовательность $Q1$ не более чем из $h$ элементов, сумма которой кратна $p.$ Положим $T2 = T1∖Q1.$ Опять имеем, что сумма элементов $T2$ равна нулю и $p− h≤ |T2|≤ |T1|− 1.$ Продолжая дальше в том же духе, мы всё-таки сумеем построить последовательность длины $p$ c суммой, кратной $p.$

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

Задача 9#82304

У Саши есть карточки, на каждой из которых написано натуральное число $1$ или $2,$ причем карточек каждого типа поровну. Эти карточки разложили по $300$ коробкам, в каждую не более $100$ карточек. Докажите, что Игорь и Вадим могут разделить между собой коробки так, чтобы у каждого из них было поровну карточек с единицей и двойкой.

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

Подсказка 1

Мы хотим найти набор не из всех коробок, в котором поровну единиц и двоек. Попробуем запустить процесс разбиения коробок на две группы и будем рассматривать как наборы префиксы нашего разбиения.

Подсказка 2

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

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

Будем следить за разностью карточек с номерами $1$ и $2.$ Сначала выберем произвольную коробку. Если в ней больше карточек с числом $1,$ то добавим коробку в которой больше карточек с числом $2.$ Если суммарно в двух этих коробках было больше карточек с числом $1,$ то добавим коробку, где больше карточек с числом $2$ и наоборот. Так сделаем $202$ раза. Заметим, что после добавления каждой коробки разность карточек в номерами $1$ и $2$ по модулю не превосходит $100.$ Тогда по принципу Дирихле найдутся $2$ момента, когда разности были равны. Возьмем все коробки, добавленные между этими двумя моментами. В них количество карточек с числом $1$ равно количеству карточек с числом $2,$ и таких коробок было не больше $202< 300.$

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

Задача 10#82305

В Тридесятом царстве в ходу были монеты в несколько копеек, не менее $81$ разных достоинств (сейчас уже никто не знает, сколько их точно было и каких достоинств). Какое наименьшее число тридесятских монет должен найти археолог, чтобы быть уверенным, что среди них заведомо есть ровно $100$ монет, в сумме дающих целое число рублей?

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

Подсказка 1

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

Подсказка 2

Можно взять 99 монет номиналом 1 и 99 монет номиналом 0. Тогда, какие бы сто монет мы не взяли, в сумме давать целое число рублей они не будут. Будем доказывать оценку на 199. Теперь давайте обобщим задачу: пусть у нас есть 2n - 1 остаток по модулю n, и мы хотим из них выбрать n, которые в сумме дают 0 по модулю n. Как такое можно доказывать?

Подсказка 3

Правильно! По индукции! Но простая индукция тут может не пройти. Поэтому по чему индукцию тут лучше вести, учитывая, что у нас какие-то остатки по модулю?

Подсказка 4

Ага! Давайте у нас будет индукция по простым делителям числа n. Но для начала надо доказать базу, то есть нашу задачу в случае простого n = p. Для этого давайте посмотрим на наши остатки и отсортируем их a₁ ≤ a₂ ≤ ... ≤ a_{2p-1}. Пойдем от противного. Попробуйте разбить наши остатки на пары(кроме может одного) так, чтобы в каждой паре гарантировано было два различных остатка.

Подсказка 5

Давайте например рассмотрим a_i и a_{i + p - 1} для i от 1 до p - 1. Они не могут быть равны, так как иначе у нас есть p одинаковых остатков. Давайте эти пары обозначим за множества A_i. А множество A_p будет содержать только a_{2p - 1}. Какую теорему осталось применить?

Подсказка 6

Правильно! Теорему Коши-Дэвенпорта, из которой сразу следует, что |A₁ + ... A_p| = p. То есть противоречие. Базу доказали. Давайте докажем переход. Пусть n = pm. Попробуйте набрать каких-то 2m - 1 набора остатков так, чтобы можно превратить их в переменные и применить предположение. Какое еще условие на эти наборы нужно?

Подсказка 7

Точно! Нам нужно, чтобы сумма в каждом наборе делилась еще на p. Какие тогда наборы нужно брать, учитывая базу индукции?

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

Переформулируем задачу. Будем считать, что у нас номиналы копеек это соответственные остатки по модулю $100$ и нам нужно выбрать $100$ остатков сумма которых делится на $100.$ Заметим, что $198$ монет не хватит так, как нам могут выпасть $99$ монет с остатком $1$ и $99$ монет с остатком $0.$ Докажем, что для любого натурального $n$ нам достаточно вытащить $2n− 1$ монету, чтоб можно было выбрать $n$ монет с суммой, которая делится на $n.$ Индукцией по количеству простых множителей числа $n.$

База индукции. Пусть $n= p$ — простое число. Пронумеруем элементы последовательности в порядке возрастания: $0 ≤a1 ≤ a2...≤ a2p−1.$ Если $ai = ai+p−1$ при каком-нибудь $i,$ то $ai+ ai+1+ ...+ai+p−1 =pai = 0$ (в $ℤp)$ и мы нашли то, что требуется. В противном случае пусть $Ai = {ai,ai+p−1}$ при $1 ≤i≤ p− 1,Ap ={a2p− 1}.$ Последовательно применяя теорему Коши — Дэвенпорта, заключаем, что $|A1 +A2 +...+Ap−1+ Ap|= p.$ Следовательно, каждый элемент $ℤp,$ в том числе $0,$ представим в виде суммы из $p$ слагаемых.

Докажем индукционный переход. Пусть $n =pm,$ где $p$ — простое, и пусть $a1,a2,...,$ $a2n−1$ — данная последовательность. По утверждению задачи для простых $p$ (база индукции), мы можем последовательно выбирать наборы из $p$ чисел, сумма которых делится на $p.$ Так мы сумеем выбрать $2m − 1$ различных наборов $I1,I2,...,I2m−1.$ Действительно, если $2m − 2$ набора уже выбрано, то количество оставшихся элементов не меньше $2pm − 1− (2m − 2)p= 2p− 1.$ Для каждого $i,$ $1≤ i≤ 2m− 1,$ положим $∑ a′i = 1∕p j∈Iiaj.$ По предположению индукции эта последовательность содержит подпоследовательность с суммой $0$ из $m$ элементов. Это дает нам требуемое подмножество из $pm$ элементов с суммой, делящейся на $n.$

Ответ:

$199$

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

Задача 11#82306

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

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

Подсказка 1

Рассмотрим какую-то перестановку элементов множества. Рассмотрим префиксные суммы этой перестановки. Среди них или их разностей найдётся подходящее множество. Значит, нам нужно доказать, что мы сможем разными перестановками получить хотя бы n-1 различных подмножеств.

Подсказка 2

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

Подсказка 3

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

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

Пусть $A = (a ,...,a ) 1 n$ — последовательность из элементов данного множества $S.$ Покажем, что в этой последовательности есть подпоследовательность вида $ai,ai+1,...,aj,$ где $1≤ i<j ≤ n,$ с суммой, кратной $n.$ Действительно, рассмотрим суммы $a1,a1 +a2,...,a1 +a2+ ...+ an.$ Если ни одна не делится на $n,$ то какие-то две дают одинаковый остаток при делении на $n,$ а значит их разность делится на $n$ и имеет требуемый вид. Последовательности такого вида будем называть интервалами. Построив несколько таких подпоследовательностей, мы можем попытаться “перемешать” числа, изменив их нумерацию так, чтобы в новой нумерации ни одна из построенных подпоследовательностей не была бы интервалом. Если это удастся, мы сумеем построить еще один интервал, не совпадающий ни с одним из уже построенных. Продолжая в таком духе, мы построим нужные $n − 1$ непустых подпоследовательностей.

Чтобы воплотить этот план в жизнь, нам осталось доказать следующее утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть даны $k≤ n− 2$ подпоследовательности исходной последовательности $A$ длины $n,$ каждая из которых содержит не меньше $2$ и не больше $n− 1$ элементов. Тогда мы можем так перенумеровать элементы последовательности $A,$ что ни одно из множеств в новой нумерации не будет интервалом.

Доказательство. Когда нам не важен порядок элементов, мы будем в этом доказательстве наряду со словом “последовательность” использовать слово “множество”.

Индукция по $n.$ Базу при $n ≤4$ нетрудно получить хотя бы перебором.

Пусть утверждение доказано для какого-то значения $n> 4$ Докажем его для $n+ 1,$ т. е. проверим, что верно следующее утверждение.

Дана последовательность $B =(b1,b2,...,bn+1).$ И пусть $D1,...,Dk$ — несколько её подпоследовательностей, причём $k ≤n− 1,$ и подпоследовательности содержат от $2$ до $n$ элементов. Тогда существует перенумерация, в которой ни одна из подпоследовательностей $Di$ не является интервалом.

Так как множеств $Di$ не больше $n − 1,$ то существует элемент $bk,$ содержащийся не более чем в одном двухэлементном множестве из $Di;$ без ограничения общности, это $bn+1.$ Выкинем элемент $bn+1$ из исходной последовательности и всех содержащих его подмножеств. Если существует пара $Di,$ содержащая $bn+1,$ то выкинем ее. Если существует множество $Dj = {b1,...,bn}$ , то его также выкинем. Если нет ни того, ни другого, то выкинем произвольное множество $Dm.$

К оставшимся элементам и множествам можно применить предположение индукции, так как все полученные множества содержат от $2$ до $n − 1$ элементов. Посмотрим, в какое место полученной последовательности можно вставить $bn+1$ так, чтобы все требуемые условия выполнились. Если было выброшено произвольное множество $Dm,$ то достаточно вставить $bn+1$ так, чтобы элементы $Dm$ не стояли подряд — очевидно, это можно сделать. Иначе, если есть пара $Di,$ то $bn+1$ нельзя вставить в два места (соседних со вторым элементом пары), а если есть множество $Dj,$ то также появляются два “запрещенных” места — края последовательности. Поскольку $bn+1$ можно было вставить в $n+ 1≥ 5$ различных мест, то хотя бы одно осталось незапрещенным. Вставив туда $bn+1,$ получаем требуемую последовательность.

Предыдущая подтема