Тема Применение классических комбинаторных методов к разным задачам

Упорядочивание

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

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

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

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

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

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

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

Задача 1#119520

На трёх полках стоит в беспорядке многотомное собрание сочинений классика. Самым левым на верхней полке стоит том “Письма, часть $13$ ”. Каждое утро библиотекарь меняет местами два тома с соседними номерами, стоящие на разных полках. В один прекрасный день все тома вернулись на те же полки, на которых они стояли вначале. Докажите, что “Письма, часть $13$ ” по-прежнему стоят слева на верхней полке.

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

Рассмотрим какую-нибудь полку. Пусть на ней в некотором порядке стоят тома с номерами $a ≤ a ≤ ...≤ a . 1 2 n$ Пусть их порядковые номера на полке равны соответственно $b1,b2,...,bn.$ Инвариантом в этой задаче будет то, что том, стоящий в ряду $a1 ≤ a2 ≤ ...≤ an$ на $k$ -м месте, будет всегда иметь тот же самый порядковый номер на полке. Это связано с тем, что при замене тома номер нового в ряду $a1 ≤ a2 ≤ ...≤an$ окажете в том же месте, в котором был номер старого, потому что они соседние. Значит, если том “Письма, часть $13$ ” окажется на верхней полке, то он будет там самым левым, что и требовалось.

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

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

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

Задача 2#122412

Кусок сыра массой $1$ кг разрезали на $n≥ 4$ кусков массами меньше $600$ г. Оказалось, что их нельзя разбить на две кучки так, чтобы масса каждой кучки была не меньше $400$ г, но не больше $600$ г (кучка может состоять из одного или нескольких кусков). Докажите, что найдутся три таких куска, что суммарная масса любых двух из них больше $600$ г.

Источники: ММО - 2025, второй день, 11.2(см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Первое решение.

Пусть $x1,x2,...,xn$ — массы кусков в граммах. Упорядочим их по величине: $600 >x1 > x2 > x3 > ...> xn.$ Тогда $x1 < 400$ , иначе кучка из одного куска массой $x1$ и кучка из всех остальных кусков противоречат условию.

Теперь достаточно показать, что $x2+x3 >600.$ Предположим противное: пусть $x2+ x3 ≤600,$ тогда $x2+ x3 < 400$ (иначе снова есть две кучки, противоречащие условию: кучка из кусков массами $x2,x3$ и кучка из всех остальных кусков). Поэтому $200> x3 > ...> xn.$

Будем теперь класть на весы по одному куски массами $x2,x3,...,xn$ именно в этом порядке. Начальная масса кучки на весах будет равна $x2 < 400,$ а конечная — $x2+ x3+...+xn = 1000− x1 >600,$ так как $x1 < 400.$

Поскольку масса каждого очередного куска меньше $200$ г, в некоторый момент на весах окажется кучка, масса которой будет не меньше $400$ г, но не больше $600$ г, что противоречит условию.

Второе решение.

Из условия следует, что масса каждого куска меньше $400$ г. При любом разбиении кусков на две кучки масса одной из них будет меньше $400$ г, а масса другой — больше $600$ г. В первом случае назовём кучку лёгкой, а во втором — тяжёлой. Лёгкой кучке соответствует тяжёлая (из остальных кусков), и наоборот. Также назовём произвольный кусок большим, если при добавлении его к некоторой лёгкой кучке она становится тяжёлой, а в противном случае назовём кусок маленьким (при добавлении его к любой лёгкой кучке она остаётся лёгкой). Масса любого большого куска больше $200$ г.

Рассмотрим кучку, состоящую из всех маленьких кусков. Она лёгкая, поэтому ей соответствует тяжёлая кучка из остальных кусков. В этой тяжёлой кучке не менее двух кусков, причём они все большие. Выберем один из этих кусков и переложим к кучке из маленьких кусков. Полученная кучка также лёгкая, так как её можно получить, добавляя последовательно к этому большому куску все маленькие куски. Ей снова соответствует тяжёлая кучка, также состоящая из не менее двух кусков. Таким образом, найдены три больших куска, любые два из которых образуют тяжёлую кучку, т.е. имеют суммарную массу больше $600$ г.

Замечание. Такая тройка больших кусков единственна. Действительно, если бы было хотя бы $4$ больших куска, то составленная из них тяжёлая кучка имела бы массу более $2⋅600= 1200$ г. Кроме того, при сужении промежутка $[400;600]$ г, в который не должны попадать массы кучек при произвольном разбиении, утверждение задачи перестаёт быть верным, что показывает пример разрезания на $4$ куска массами $200,200,200,400$ г.

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

Задача 3#78075

Существует ли $2014$ различных натуральных чисел таких, что их сумма делится на сумму любых двух (различных)?

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

Пусть такие числа существуют. Так как все числа различные, то давайте упорядочим их по убыванию $a ≥ a ≥ ...≥ a . 1 2 2014$ Теперь давайте посмотрим на суммы с самым наибольшим числом и аналогично упорядочим по убыванию $a1 +a2 ≥ a1+ a3 ≥...≥a1+ a2014.$ Частные, которые будут получаться при делении суммы всех чисел на эти, как минимум, могут быть от $2$ до $2014.$ Но $2014$ слишком большое число, и равенства не будет. Противоречие.

Ответ:

Не существует

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

Задача 4#80745

Найти все множества $X$ , состоящие из различных натуральных чисел от 1 до 50 такие, что: 1) X содержит не все числа от 1 до 50, но не меньше трёх из них, 2) X содержит числа 1 и 50, 3) для любых трёх чисел $x< y < z$ из X число $x− y+ z$ также принадлежит X.

Источники: Всесиб-2024, 11.2 (см. sesc.nsu.ru)

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

Подсказка 1

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

Подсказка 2

Если у нас есть три подряд идущих числа x, y, z: x < y < z, то число x + z - y, которое больше x, но меньше z, то оно равно y. Что же это значит?

Подсказка 3

Это значит, что y = (x + z)/2, а это критерий арифметической прогрессии. Значит, наш набор - это арифметическая прогрессия. Что мы можем тогда сказать, если она начинается с 1, а заканчивается 50?

Подсказка 4

Это значит, что 49 делится на разность между соседними членами. И либо это 1, либо 7, либо 49. Все варианты нам подходят или нет?

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

Отсортируем числа из множества $X$ по возрастанию:

x1 < x2 <x3 <...<xk

Для любых трех последовательных чисел $xi < xi+1 <xi+2$ число $xi+xi+2− xi+1$ по условию лежит в $X$ . Но

x < x+ x − x < x i i i+2 i+1 i+2

Тогда это число должно равняться $xi+1$ , откуда $xi+1 = xi+xi+2 2$ . В силу произвольности выбора номера $i$ получаем, что каждое число является средним арифметическим двух его соседей, но тогда это арифметическая прогрессия.

По условию числа $1,50∈ X$ , то есть $50= xk = x1+(k− 1)⋅d= 1+(k− 1)⋅d$ , где $d$ - разность прогрессии.

$(k− 1)⋅d= 49$ и в силу того, что $50> k> 2$ , а $d$ натуральное. Имеем единственное решение $k= 8,d =7$ .

Ответ:

$X = {1,8,15,22,29,36,43,50}$

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

Задача 5#83856

Выписаны 100 положительных чисел, сумма которых равна $S,$ а сумма квадратов больше, чем $P.$ Доказать, что среди этих чисел есть число, большее, чем $P∕S.$

Источники: КФУ - 2024, 11.3 (см. malun.kpfu.ru)

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

Подсказка 1

Пусть х₁ - наибольшее из чисел. Тогда очевидно х₁>P/S. С таким выражением работать куда проще, чем с абстрактным условием на неизвестное число. Перезапишем его в виде Sx₁>P. Как бы нам доказать это неравенство?...

Подсказка 2

Давайте домножим выражение для суммы всех чисел на х₁. Попарного сравним каждое слагаемое со слагаемыми из суммы квадратов. Что получается?

Подсказка 3

Верно, Sx₁ оказывается не меньше суммы квадратов! А теперь можно заменить всё на введённые в условии обозначения и доказать неравенство.

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

Расположим наши числа по убыванию, $x ≥ x ≥ x ≥...≥x . 1 2 3 100$ Имеем

S = x1+ x2+x3 +...+ x100

x2+x2 +x2+ ...+ x2 > P 1 2 3 100

Умножим первое равенство на $x1,$ получим, что

Sx1 = x2+x1x2+ x1x3+ ...+ x1x100 ≥ x2+ x2 +x2+ ...+ x2 > P 1 1 2 3 100

Следовательно, $x1 > P. S$

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

Задача 6#90368

В ряд лежат $30$ апельсинов, веса соседних отличаются не более чем на $10$ г. Докажите, что их можно разложить по три штуки в пакет и положить пакеты в ряд так, чтобы веса каждых двух соседних пакетов отличались не более чем на $10$ г.

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Сперва докажем следующую лемму.

Лемма. В ряд лежат $30$ апельсинов, массы любых двух соседних отличаются не более, чем на $10$ г. Тогда если упорядочить апельсины по убыванию массы, то массы любых двух соседних снова будут отличаться не более, чем на $10$ г.

Доказательство. Действительно, предположим обратное, пусть нашлись два соседних апельсина весами $x> y,$ разница весов которых больше $10$ г. Это значит, что для любого апельсина весом хотя бы $x$ в изначальном ряду возле него апельсины весами хотя бы $x$ и для любого апельсина весом не более $y$ в изначальном ряду возле него апельсины весами не более $y.$ Но ряд непрерывен, потому где-то должны лежать рядом апельсины двух видов, противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Тогда разложим апельсины по возрастанию весов. Выложим $10$ пакетов в ряд и положим в них сначала по $2$ апельсина: в первый пакет — первый и последний апельсин, во второй — второй и предпоследний апельсин и т. д. На каждом шаге добавляются два изменения весов разных знаков, что в сумме делает разность весов соседних пакетов по модулю не больше максимума разностей весов соседних апельсинов, т. е. не более $10$ г. Разложим пакеты по возрастанию веса — по-прежнему веса соседних отличаются не более чем на $10$ г. Осталось ещё $10$ апельсинов в ряду по возрастанию (с $21$ -го по $30$ -й). Положим самый лёгкий апельсин в самый тяжёлый пакет, следующий — во второй по тяжести и т. д. Как и ранее, веса соседних пакетов будут отличаться не более чем на $10$ г.

Курсы

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

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

Задача 7#96342

Докажите, что среди любых $25$ различных положительных вещественных чисел можно выбрать два, сумма и разность которых не совпадают ни с одним из оставшихся $23$ чисел.

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

Данное утверждение верно для $n$ чисел при любом $n≥ 4$ и доказывается «от противного».

Предположим, что сумма или разность любых двух из $n$ разлчных чисел $a1 < a2 <...< an−1 <an$ cодержится среди остальных $n − 2$ чисел. Тогда

an+ ai > an =⇒ an− ai = an−1,

где $1 ≤i≤ n− 1.$

При четном $n= 2k$ получаем

an− ak =ak

значит, разность $an$ и $ak$ не содержится среди остальных чисел.

При нечетном $n= 2k +1$ надо рассмотреть пары $(an−1;ai).$ Для них

an−1+a1 =an

an−1+ a> an i

при $2≤ i≤n − 2$ и потому должны выполняться равенства

an−1− ai =an−i−1

в частности

an−1− ak =ak

что также приводит к противоречию.

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

Задача 8#58011

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

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

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

Обозначим количества карандашей разных цветов за $a1 ≤ a2 ≤...≤a100.$

Если $a95 ≥17,$ то получаем $a95+ a96 +a97+ a98+ a99 +a100 ≥6a95 ≥ 6⋅17 >100$ противоречие с выводом выше. Значит, $a95 ≤ 16.$

Тогда суммарно в коробке карандашей

(a1+ a2 +...+ a94)+ (a95+ a96+a97+ a98+ a99+a100)≤

≤(161 +162+ ...+1694)+99= 94⋅16+99= 1603

Может ли быть ровно 1603 карандаша? Да, например, если было 19 карандашей одного цвета ( $a =19) 100$ и по 16 карандашей всех остальных цветов ( $a =...=a = 16). 1 99$

Ответ:

$1603$

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

Задача 9#71649

На дискотеке $n$ юношей танцевали с $n$ девушками. В каждой паре юноша был выше девушки, но не более, чем на $10$ см. Докажите, что если поставить танцевать самого высокого юношу с самой высокой девушкой, второго по росту — со второй, и т. д., то по прежнему в каждой паре юноша будет выше девушки и опять же не более, чем на $10$ см.

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

Подсказка 1

Давайте скажем, что юноша может танцевать с девушкой, если он выше неё, но не более, чем на 10 см. И чтобы доказать, что после перестановки в каждой новой паре юноша может танцевать с девушкой, попробуйте доказать это для произвольной пары, предположив обратное

Подсказка 2

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

Подсказка 3

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

Подсказка 4

А если юноша с номером i не может танцевать с девушкой с номером i, то со сколькими девушками могут танцевать юноши не ниже него/не выше него?

Подсказка 5

Но в самом начале они же как-то танцевали, значит мы получили противоречие! Тогда юноша с номером i может танцевать с девушкой с номером i ⇒ во всех парах юноша может танцевать с девушкой! Задачка решена :)

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

Пусть юноша может танцевать с девушкой, если он выше неё, но не более, чем на $10$ см, и не может в обратном случае. Упорядочим всех девушек и юношей по возрастанию. Пусть рост всех юношей равен $m1 ≤ m2 ≤ ...≤ mn,$ рост всех девушек равен $d1 ≤ d2 ≤...≤dn.$ Докажем, что юноша с ростом $mi$ может танцевать с девушкой с ростом $di.$ Для этого предположим, что это не так, и рассмотрим $2$ случая:

1) $di+ 10< mi$
Тогда ни один юноша с ростом $≥ mi$ не сможет танцевать ни с одной девушкой с ростом $≤ di.$ Но тогда последние $n − i+ 1$ юношей могут танцевать не более с чем $n− i$ девушками, противоречие.

2) $di ≥ mi$
Тогда ни один юноша с ростом $≤ mi$ не сможет танцевать ни с одной девушкой с ростом $≥ di.$ Но тогда первые $i$ юношей могут танцевать не более с чем $i− 1$ девушками, противоречие.

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

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

Задача 10#73182

Сережа коллекционирует фигурки марвел. У него есть несколько коробок разных размеров, чем больше коробка, тем больше фигурок в ней лежит. Во всех коробках 112 фигурок. В трёх самых маленьких коробках в сумме лежит 25 фигурок, а в трех самых больших — 50 фигурок. Сколько фигурок может быть в самом большой коробке? Найдите все варианты.

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

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

Разложим коробки от меньшей к большей. Предположим, что в третьей с начала коробке меньше 10 фигурок. Тогда всего в первых трех коробках не больше $7+8 +9= 24< 25$ фигурок — противоречие. Значит, в третьей коробке хотя бы 10 фигурок. Аналогично показывается, что третья коробка с конца содержит не больше 15 фигурок( $16 +17+ 18= 51 >50$ ). Предположим, что эта коробка содержит 14 фигурок или меньше. Тогда суммарное количество фигурок в коробках, отличных от первых трёх и последних трёх, не превосходит $11+ 12 +13= 36$ , а должно быть $112− 25− 50 =37$ . Противоречие. Значит, в третьей с конца коробке ровно 15 фигурок. Тогда в самой большой коробке может быть либо 18 ( $50= 15+ 17 +18$ ), либо 19 ( $50= 15+16+ 19$ ) фигурок. Больше 19 фигурок быть не может, потому что тогда во второй по величине коробке фигурок не больше, чем $50− 20 − 15= 15,$ а в ней хотя бы 16 коробок. Меньше 18 быть не может, так как тогда фигурок в трех самых больших коробках не больше, чем $15 +17+ 17= 49 <50.$ Оба ответа подходят: (7,8,10,11,12,14,15,17,18) и (7,8,10,11,12,14,15,16,19).

Ответ: 18 или 19

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

Задача 11#34683

Солдаты построены в две шеренги по $n$ человек, так что каждый солдат из первой шеренги не выше стоящего за ним солдата из второй шеренги. В шеренгах солдат выстроили по росту. Докажите, что после этого каждый солдат из первой шеренги также будет не выше стоящего за ним солдата из второй шеренги.

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

Решение

Обозначим через $a1,a2,...,an$ рост солдат первой шеренги в порядке убывания, а через $b1,b2,...,bn$ рост солдат второй шеренги в порядке убывания (те же обозначения используем и для самих солдат).

Пусть утверждение задачи неверно: $ak > bk$ для некоторого $k$ . Это означает, что до перестраивания по росту солдат $ak$ мог стоять только перед одним из $k− 1$ солдат $b1,b2,...,bk−1$ . То же справедливо и для солдат $a1,a2,...,ak−1$ , поскольку они не ниже солдата $ak$ . Итак, до перестраивания шеренг $k$ солдат $a1,a2,...,ak$ могли стоять только перед $k− 1$ солдатами $b1,b2,...,bk−1$ . Противоречие.

Ответ:

Интенсивы

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

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

Задача 12#34686

На доске написано $2021$ число. Оказалось, что сумма любых двух написанных на доске чисел также написана на доске. Какое наибольшее количество ненулевых чисел может быть написано?

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

Подсказка 1

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

Подсказка 2

Да, если у нас есть хотя бы два положительных числа, то их сумма тоже написана на доске! Тогда, если мы сложим максимальное число и еще какое-то положительное, то мы получим, что их сумма тоже будет на доске! Поэтому на доске не больше одного положительного числа. А что же с отрицательными числами?

Подсказка 3

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

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

Упорядочим числа по возрастанию. Если два самых больших числа $a$ и $b$ ( $a ≥b$ ) оба положительные, то их сумма $a+ b,$ которая больше максимального числа ( $a +b> a),$ должна быть тоже на доске. Значит, на доске не больше одного положительного числа.

Аналогично поймем про отрицательные числа. Если два самых маленьких $c$ и $d$ ( $c≤ d)$ числа оба отрицательные, то их сумма $c+ d,$ которая меньше минимального числа ( $c+ d< c),$ должна быть тоже на доске. Значит, на доске не больше одного отрицательного числа.

Получили оценку: на доске не более двух ненулевых чисел.

Пример на ровно два ненулевых числа простой: $1,− 1$ и $2019$ нулей. Все условия задачи в нем выполняются.

Ответ:

$2$

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

Задача 13#35491

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

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

Условие выполняется для произвольных девяти чисел, и нам ничего не мешает считать их упорядоченными по возрастанию: $a1 ≤ a2 ≤ ...≤ a9$ . Тогда нам достаточно доказать положительность $a1$ . Применим условие для тех четырёх чисел, для которых оно “наименее вероятно”, то есть для самых больших четырёх чисел — условие-то всё равно будет выполняться, но мы получим из этого самую классную информацию!

a6+a7+ a8+ a9 ≤a1+ a2+ a3+a4+ a5.

При этом $a6 ≥ a2$ , $a7 ≥a3$ , $a8 ≥ a4$ , $a9 ≥a5$ . Тогда при $a1 < 0$ мы ещё уменьшим правую часть, и она будет меньше левой — противоречие. Значит, всё-таки $a ≥ 0 1$ .

Ответ:

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

Задача 14#35493

В 10 коробках лежат карандаши (пустых коробок нет). Известно, что в разных коробках разное число карандашей, причем в каждой коробке все карандаши разных цветов. Докажите, что из каждой коробки можно выбрать по карандашу так, что все они будут разных цветов.

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

Упорядочим коробки по количеству карандашей $b < b <⋅⋅⋅<b 1 2 10$ . Хочется начинать с коробки, где карандашей меньше всего. Почему? Если мы начнем с коробки, где карандашей много, то можем случайно взять тот цвет, который лежит в коробке, где карандашей мало. В коробке $b1$ есть хотя бы один карандаш, берем любой. В коробке $b2$ карандашей хотя бы два и все разного цвета, поэтому найдется карандаш, отличный от того, который мы взяли. Те же самые рассуждения работают и дальше: на $k$ -ом шаге в коробке $bk$ хотя бы $k$ карандашей разного цвета, мы взяли только $k− 1$ карандаш из предыдущих коробок, поэтому можем взять карандаш из коробки $bk$ , отличный по цвету от ранее взятых. Значит, из каждой коробки можно выбрать по карандашу так, что все они будут разных цветов.

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

Ответ:

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

Задача 15#35497

Есть $20$ различных натуральных чисел, не превосходящих $100.$ Докажите, что среди их попарных разностей есть три одинаковые.

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

Упорядочим числа по возрастанию. Рассмотрим все $19$ разностей соседних чисел (из большего вычитаем меньшее). Предположим, что среди них нет двух одинаковых. Заметим, что разность самого большого числа и самого маленького не превосходит $100− 1= 99,$ но она равна сумме наших $19$ разностей. При этом по нашему предположению у нас не более $2$ разностей равны $1,$ не более двух разностей равны $2,$ и так далее. Тогда сумма наших $19$ разностей не меньше, чем

9⋅10 2(1+ 2+...+9)+ 10= 2⋅-2--+ 10 =100> 99

откуда получаем противоречие.

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

Задача 16#35498

(a) Числа от $1$ до $100$ выписаны по одному разу в клетки таблицы $10× 10.$ В каждой строке отмечено второе по величине число. Докажите, что сумма отмеченных чисел не меньше суммы в одной из строк.

(b) Числа от $1$ до $100$ выписаны по одному разу в клетки таблицы $10× 10.$ В каждой строке отмечено третье по величине число. Докажите, что сумма отмеченных чисел не меньше суммы в одной из строк.

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

Пункт а), подсказка 1

Нам надо доказать, что сумма отмеченных не меньше суммы чисел в какой-то строке. Можно оценить эти две суммы, найдя минимум одной и максимум другой.

Пункт а), подсказка 2

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

Пункт а), подсказка 3

Получается, оно не меньше 9 чисел в своей строке, а ещё и не меньше 9 чисел в каждой из других строк, тогда это число ≥90! Давайте обозначим его за а₁₀. Остальные отмеченные можно не оценивать, а попробовать найти строку, где сумма чисел будет поменьше. Если наши отмеченные - вторые по величине в своих строках, то в строке с каким из отмеченных числа в среднем будут меньше?

Пункт а), подсказка 4

Конечно, это строка с наименьшим из отмеченных! Какая максимальная сумма чисел может быть в этой строке? Выразите её через а₁ - наименьшее отмеченное! Будет ли сумма отмеченных больше неё?

Пункт а), подсказка 5

Конечно будет, достаточно лишь вспомнить, что а₁₀ ≥ 90, а все остальные отмеченные ≥ a₁ и вы сразу увидите справедливость неравенства.

Пункт б), подсказка 1

Помните решение пункта а? Там мы возились с наибольшим и наименьшим из отмеченных чисел, здесь будем делать что-то похожее, но надо будет покруче оценивать суммы. Раз уж все числа различные, давайте отмеченные сразу упорядочим: а₁ < a₂ < … < a₁₀. И так же оценим наибольшие из отмеченных и сумму чисел в строке.

Пункт б), подсказка 2

а₁₀ и а₉ оцениваем просто из того, скольких чисел они точно больше. И строку берём такую же, как в пункте а)

Пункт б), подсказка 3

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

Пункт б), подсказка 4

То есть а₂ > a₁ ⇒ a₂ ≥ a₁ + 1; a₃ ≥ a₂ + 1 ≥ a₁ + 2 и т.д. Теперь всё должно получиться!

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

(a) Упорядочим отмеченные числа по возрастанию и обозначим их через $a1,a2,...,a10$ (в порядке возрастания). Заметим, что $a10$ не меньше как минимум $9$ чисел в каждой строке (поскольку $a10$ не меньше любого другого отмеченного числа, которое является вторым по величине в своей строке). Поэтому $a10 ≥90.$ Рассмотрим строку, в которой стоит $a1.$ Сумма чисел в этой строке не превосходит

8⋅9 a1 − 8+ a1− 7+...a1 − 1+ a1+ 100= 9a1+ 100−-2 =9a1+ 66

поскольку первое по величине число в этой строке не больше $100,$ остальные строго меньше $a1$ и все различны. С другой стороны, сумма отмеченных чисел больше, чем

9a1+a10 ≥ 9a1 +90> 9a1+66

поскольку $a2 >a1,...,a9 > a1,a10 ≥90.$ То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит $a1.$

(b) Упорядочим отмеченные числа по возрастанию и обозначим их через $a1,a2,...,a10$ (в порядке возрастания). Заметим, что $a10$ не меньше как минимум $8$ чисел в каждой строке (поскольку $a10$ не меньше любого другого отмеченного числа, которое является третьим по величине в своей строке). Поэтому $a10 ≥ 80.$ Аналогично, $a9$ не меньше как минимум $8$ чисел в каждой строке, кроме строки с $a10.$ Тогда $a9 ≥ 72.$

Рассмотрим строку, в которой стоит $a1.$ Сумма чисел в этой строке не превосходит

a1− 7+ a1− 6 +...a1− 1+ a1+99+ 100= 8a1+ 199− 7⋅8= 8a1 +171 2

поскольку первое по величине число в этой строке не больше $100,$ второе не больше $99,$ остальные строго меньше $a1$ и все различны. С другой стороны, сумма отмеченных чисел равна

a1+a2 +...+ a8+ a9 +a10 ≥ a1+(a1+ 1)+ (a2 +1)...(a1+7)+ 72+80= 8a1+ 180 >8a1+ 171

поскольку $a1 <a2 <...<a8,a9 ≥72,a10 ≥80.$ То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит $a1.$

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

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

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

Задача 17#81695

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

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

Покажем, что среди данных чисел не может быть больше четырёх попарно различных чисел. Объединим равные числа в группы, выберем в каждой группе по одному числу и расположим выбранные числа в порядке убывания $a> b> c> d> e> ...$ Числа $a,b,c,d$ по условию образуют геометрическую прогрессию, поэтому $ad= bc,$ откуда $bc d= a.$ Те же самые рассуждения показывают, что $bc e= a = d,$ противоречие. Из доказанного следует требуемое.

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

Задача 18#88699

В ряд лежат $30$ яблок. Массы любых двух соседних яблок отличаются не более, чем на $10$ г. Докажите, что если упорядочить яблоки по убыванию массы, то массы любых двух соседних снова будут отличаться не более, чем на $10$ г.

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

Пусть это не так: есть яблоко веса $a,$ а следующий вес больше $a+ 10.$ Покрасим яблоки с весом не больше $a$ в жёлтый цвет, а яблоки с весом больше $a+ 10$ — в оранжевый. В исходной расстановке два яблока разных цветов должны лежать рядом, значит, разность их весов не меньше $10.$ Противоречие.

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

Задача 19#88713

В классе $33$ ученика, а сумма их возрастов $430$ лет. Справедливо ли утверждение, что в классе найдутся $20$ учащихся, сумма возрастов которых больше $260?$

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

Пусть сумма возрастов любых двадцати учащихся меньше $260,$ то есть не больше $259.$ Рассмотрим двадцать самых взрослых учеников. Среди них есть тот, кому меньше $13,$ а, значит, не больше $12.$ Рассмотрим $13$ остальных, их сумма возрастов больше $430 − 260= 170,$ тогда среди них есть тот, кому больше $13.$ Противоречие: самый младший из $20$ -ки оказывается младше, чем кто-то из оставшихся.

Ответ:

Да, справедливо

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

Задача 20#88714

Есть $15$ баллонов воды разного веса. Докажите, что можно разлить один баллон на два новых так, что полученные $16$ баллонов можно распределить по двум грузовикам, чтобы каждый грузовик увёз поровну баллонов и поровну литров воды.

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Чтобы получить разницу, которую легко оценить следует распределить первые 14 баллонов по грузовикам так: в один нечётные, в другой - чётные.

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

Упорядочим баллоны по весу: $a < a < ...< a . 1 2 15$ Баллоны с нечётными индексами поместим в первый грузовик, баллоны с чётными — в другой. Заметим, что

a15− a1 =(a15 − a14)+(a14− a13)+ ...+ (a2 − a1)> (a15− a14)+ (a13− a12)+...+(a3− a2)

Тогда понятно, что $a15 > (a15+ a13+...+a1)− (a14+a12+ ...+ a2).$ Таким образом, мы поняли, что $a15$ больше разности загруженностей грузовиков. Пусть искомая разность равна $x.$ Разделим $a 15$ на баллон весом $x 2$ и $a − x. 15 2$ Баллон весом $x 2$ переложим во второй грузовик. Получили искомое распределение весов.