Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Применение классических комбинаторных методов к разным задачам

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

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

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

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

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

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

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

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

Вероятностный метод (усреднение)

Индукция в комбинаторике

Дискретная непрерывность

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

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

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

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

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

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

Ответ:

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

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

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

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

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

Есть $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$ переложим во второй грузовик. Получили искомое распределение весов.

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

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

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

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

Выложим яблоки по неубыванию масс. Из восьмой задачи понятно, что массы соседних яблок по-прежнему отличаются не больше, чем на $10$ грамм. Занумеруем яблоки по неубыванию масс $a1 ≤ a2 ≤ ...≤ a30.$ Рассмотрим следующий ряд пар: $(a1,a30),(a2,a29),(a3,a28),...,(a15,a16).$ В нём массы двух соседних пакетов $(ak,a31−k)$ и $(ak+1,a31−(k+1))$ отличаются на

(ak− ak+1)+(a31−k − a31−(k+1)) ≤10− (ak+1− ak)≤10

а с другой стороны

(ak− ak+1)+(a31−k− a31−(k+1))≥ −10+ (a31−k− a31−(k+1))≥− 10

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

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

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

Каждая из $100$ коробок состоит из яблок и груш. В каждой коробке не более $s$ яблок и не более $m$ груш. Докажите, что можно так разбить коробки на $2$ группы по $50,$ чтобы по суммарному количеству яблок группы различались не более чем на $s$ штук, а по суммарному количеству груш они различались не более чем на $m$ штук.

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

Подсказка 1

Давайте разбираться с двумя видами фруктов по очереди. Начнём с яблок, чтобы делать какие-то оценки на разность количеств, давайте упорядочим коробки по возрастанию количеств яблок в них. Теперь в ряду разобьём коробки на пары соседних с номерами 2i-1 и 2i. Как тогда можно оценить разность количеств яблок в группах, если в каждую группу попало по одной коробке из каждой пары?

Подсказка 2

Ага, она не превосходит максимального количества яблок в коробке, а, значит, не превосходит s. Теперь давайте перейдём к грушам. Вот пусть вообще произвольное распределение (что из каждой пары коробок ровно одна в первой группе) не обеспечило нам маленькую разность количества груш в группах. Что с этим можно сделать?

Подсказка 3

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

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

Произвольно занумеруем коробки. Обозначим за $a i$ — количество яблок в коробке с номером $i,$ за $b i$ — количество груш в коробке с номером $i.$

Упорядочим коробки по убыванию яблок $ai$ (т. е. $a1 ≥ a2 ≥ ...≥ a100$ ). Назовем коробки с номерами $2i− 1$ и $2i$ двойкой. Заметим, что если разбить коробки на две группы так, что пары любой двойки попадут в разные группы, то разность $ai$ в группах не будет превосходить $(a1− a2)+(a3− a4)+ ...+ (a99− a100)≤a1 ≤ s.$ Распределим коробки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма $bi$ больше, чем во второй. Тогда в какой-то из двоек $bi,$ попавшее в первую группу, больше $bj,$ попавшего во вторую. Поменяв коробки, принадлежащие этой двойке, местами, мы получим, что разность сумм $bi$ уменьшилась по модулю, поскольку изменилась не более, чем на $2b1.$ Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.

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

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

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

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

Подсказка 1

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

Подсказка 2

Давайте тогда наши 98 коробок упорядочим по возрастанию количества яблок в них, пары соседних разобьём на пары с номерами 2i-1 и 2i. Теперь любое разбиение, где коробки из каждой из пар попали в различные группы таково, что разность числа яблок в группах не превосходит максимального числа яблок в коробках.

Подсказка 3

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

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

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

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

Произвольно занумеруем коробки. Обозначим за $ai$ количество яблок в коробке с номером $i$ за $bi$ — количество груш в коробке с номером $i.$

Упорядочим коробки по убыванию яблок $ai$ (т. е. $a1 ≥ a2 ...≥ a98).$ Назовем коробки с номерами $2i− 1$ и $2i$ двойкой. Заметим, что если разбить коробки на две группы так, что пары любой двойки попадут в разные группы, то разность $ai$ в группах не будет превосходить

(a1− a2)+ (a3− a4)+...+ (a97− a98)≤ a1

Распределим коробки по группам произвольным образом. Пусть еще не получилось требуемого разбиения, причем в первой группе сумма $bi$ больше, чем во второй. Тогда в какой-то из двоек $bi$ попавшее в первую группу, больше $bj$ попавшего во вторую. Поменяв коробки, принадлежащие этой двойке, местами, мы получим, что разность сумм $bi$ уменьшилась по модулю, поскольку изменилась не более, чем на $2bi.$ Тогда такой процесс не может продолжаться бесконечно, поэтому когда-нибудь распределение станет требуемым.

Добавим теперь первые две выбранные коробки в ту группу, где не меньше груш. Очевидно, полученный набор из $51$ коробки удовлетворяет условиям задачи, что и требовалось.

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

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

Семь грибников собрали вместе $59$ грибов, причем каждый собрал разное количество. Докажите, что какие-то три грибника собрали вместе не менее $33$ грибов.

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

Упорядочим количества собранных грибов по возрастанию: $a < a < ...< a . 1 2 7$ Покажем, что $a +a + a ≥ 33. 5 6 7$ Предположим противное, пусть $a5+a6+ a7 ≤ 32.$ Нетрудно понять, что $7a7− 21=(a7− 6)+(a7− 5)+ ...+ a7 ≥a1+ a2+ ...+ a7 =59,$ откуда $a7 ≥12.$ Тогда из неравенства $a5+a6+ a7 ≤ 32$ следует, что $a5+ a6 ≤ 20.$ Также из неравенства $a5+ a6+ a7 ≤32$ следует, что $a1+ a2+a3+ a4 ≥ 27.$ Теперь мы можем оценить $a6$ и $a5$ снизу:

4a6 − 14= (a6− 5)+ (a6− 4)+(a6− 3)+ (a6− 2)≥ a1+ a2 +a3+ a4 ≥ 27

4a5− 10≥ (a5 − 4)+ (a5− 3)+(a5− 2)+ (a5− 1)≥ a1+a2+ a3+ a4 ≥27

Таким образом, $a6 ≥ 11$ и $a5 ≥ 10,$ откуда $a6+ a5 ≥ 21.$ Получили противоречие с неравенством $a5+a6 ≤ 20.$

Курсы

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

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

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

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

(a) Какое наименьшее количество различных сумм можно получить?

(b) Какое наибольшее количество различных сумм можно получить?

Источники: Муницип - 2021, Татарстан, 11.5

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

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

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

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

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

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

Верно, эти числа тоже будут идти по возрастанию! То есть, знаки в таком наборе будут полностью совпадать со знаками в первом наборе, поэтому он тоже будет возрастающим(но в нём не будет последнего числа). Аналогично, дальше мы можем прибавлять максимум из оставшихся чисел к каждому числу из набора и тем самым получать новый набор! Сколько всего чисел тогда будет, если в первом наборе n, во втором n-1, в третьем n-2..,?

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

Да, всего чисел будет n*(n-1)/2. Остаётся привести пример, когда все другие суммы, которые мы не рассматривали будут совпадать с хотя бы одним из рассмотренных нами чисел(для этого стоит располагать все n чисел компактно по отношению друг к другу)

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

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

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

Верно, тогда удобно считать, что каждое из чисел либо есть в сумме, либо его нет! То есть, на каждое число существует 2 варианта! Сколько всего вариантов, в таком случае?

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

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

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

Можно считать, что исходные положительные числа расположены в порядке возрастания: $a < a < ...< a. 1 2 n$ Рассмотрим

$PIC$

Очевидно, что здесь каждое число больше предыдущего, поэтому все выписанные числа различны. Их количество $n +(n− 1)+...+ 1= 12n(n+ 1)$ соответствует требованиям задачи.

Осталось привести пример, в котором больше, чем $12n(n+ 1)$ различных сумм получить не удастся. Для этого подойдет набор из первых $n$ натуральных чисел, из которых нельзя составить больше, чем $12n(n +1)$ различных сумм: эти суммы - все натуральные числа от $1$ до $1+ 2+ ...+ +n= 12n(n+ 1).$

б) Каждое число $ai$ входит или не входит в рассматриваемую сумму. Кроме того, нужно ещё исключить сумму, не содержащую ни одного слагаемого, поэтому различных сумм из $n$ слагаемых можно составить не более, чем $2n− 1.$

Числа $1,10,102,...,10n−1$ дают пример $n$ различных чисел, из которых можно образовать наибольшее число различных сумм. Сумма любых $k$ чисел этого набора - это число, в десятичной записи которого используются только $1$ и $0.$ Каждая такая сумма может быть представлена в виде $n$ -элементного упорядоченного набора из $0$ и $1.$ Поскольку на каждом месте набора могут быть только две цифры, их общее количество равно $2⋅2⋅...⋅2= 2n.$ Единственный невозможный набор, составленный из $n$ нулей, необходимо исключить, поэтому общее количество допустимых наборов равно $2n− 1.$

Ответ:

$a) n(n+1) 2$

$n b) 2 − 1$

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

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

Даны три отрезка длины $1,2$ и $3.$ Отрезок длины $3$ разбили на $100$ отрезков. Докажите, что из получившихся $102$ отрезков можно выбрать какие-то три таким образом, что сумма длин любых двух выбранных отрезков больше длины третьего.

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

Расположим длины $100$ частей, на которые разбили отрезок длины $3,$ в порядке невозрастания $a ≤ a ≤...≤a , 1 2 100$ где $a ,...,a 1 100$ — длины.

Для проверки условия, что среди трех отрезков длинами $0< x≤ y ≤z$ сумма любых двух больше длины третьего достаточно проверить, что $x +y >z$ (остальные неравенства выполняются по очевидным причинам).

Рассмотрим тройки отрезков $(a1,a2,a3),(a2,a3,a4),...(a98,a99,a100).$ Либо найдется тройка, для которой выполнено неравенство треугольника, и задача решена, либо ни для одной из них не выполнено это условие. Тогда имеем

a1+ a2 ≤ a3;a2+ a3 ≤a4,...,a98+ a99 ≤ a100

Сложим все неравенства и получим, что $a + 2(a + a + ...+ a )+ a ≤ a + a +...+ a . 1 2 3 98 99 3 4 100$ Преобразуем и получим

a1 +a2+ a3+...+a98 ≤ a100− a2

Откуда $a1 +a2+ ...+ a100 ≤ 2a100+ a99− a2 < 3a100.$ Но сумма всех $100$ отрезков это $3.$ Значит, $a100 > 1.$ При этом $a100 < 3,$ потому что это длина кусочка от отрезка длины $3.$ И тогда можно взять тройку отрезков $1,2,a100,$ для которой выполнены неравенства $a100+1 >2;2+ a100 > 1;2+ 1> a100.$

Значит, всегда можно выбрать какие-то $3$ из $102$ отрезков, чтобы сумма длин любых двух выбранных отрезков была больше длины третьего.

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

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

Первоклассник составил из шести палочек два треугольника. Затем он разобрал треугольники обратно и разбил шесть палочек на две группы по три палочки: в первой группе оказались три самых длинных палочки, а во второй — три самых коротких. Обязательно ли можно составить треугольник из трех палочек первой группы? А из трех палочек второй группы?

Источники: ВСОШ, РЭ, 2021, 10.1 (см. olympiads.mccme.ru)

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

1) Упорядочим длины палочек

a1 ≥ a2 ≥ a3 ≥a4 ≥ a5 ≥ a6.

Так как $a1$ входила в треугольник с некоторыми двумя другими палочками, то $a1$ меньше их суммы, а следовательно, меньше чем сумма двух самых длинных из оставшихся палочек: $a1 <a2+ a3.$ Так как $a1 ≥ a2$ и $a1 ≥a3,$ выполнение неравенства $a1 < a2+ a3$ достаточно для того, чтобы из палочек $a1,a2,a3$ можно было составить треугольник.

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

Ответ:

1) да, обязательно; 2) нет, не обязательно

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

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

Петя задумал пять чисел (не обязательно целых). На доске он написал их попарные суммы: $7,9,12,16,17,19,20,21,22,29.$ Какие числа задумал Петя?

Источники: ШВБ - 2020, отборочный тур (см. olymp.bmstu.ru)

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

Подсказка 1

Попробуем набрать уравнения, которых будет достаточно для однозначного восстановления ответа! Для начала, мы можем расположить исходные числа по возрастанию, тогда мы точно знаем, из каких чисел было получено 7, 9, 22, 29.

Подсказка 2

Верно, 7 - это сумма двух минимальных чисел, 9 - это сумма первого и третьего, 22 - это сумма третьего и пятого, а 29 - это сумма четвертого и пятого! Также, поскольку нам даны все попарные суммы, то есть каждое число встречается ровно в двух суммах, то мы знаем и общую сумму чисел, она равна 43. Тогда, какое число мы уже точно-точно знаем?

Подсказка 3

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

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

Поскольку все суммы разные, все числа тоже разные. Упорядочим эти числа в порядке возрастания и обозначим следующим образом: $x1 < x2 < x3 < x4 < x5$ Тогда

x1 +x2 = 7, x1+x3 =9, x3+ x5 = 22, x4+ x5 = 29

Кроме того,

4(x1+ x2+ x3 +x4+ x5)=7 +9+ 12+ 16 +17+ 19+20+ 21+ 22 +29,

(x +x )+ x +(x + x) =43 1 2 3 4 5

Решая систему, последовательно находим

x3 = 7, x1 = 2, x2 = 5, x5 = 15, x4 =14

Ответ:

$2,5,7,14,15$

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

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

Какое наименьшее количество натуральных чисел от $1$ до $320$ нужно покрасить в красный цвет, чтобы $1$ и $320$ были красными, а также для любого красного числа $a,$ большего $1,$ нашлись такие красные числа $b$ и $c$ (возможно, одинаковые), что $a =b+ c?$

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

Подсказка 1

Скажем, что мы закрасили числа a₁, a₂, ... , aₙ. Упорядочим их по возрастанию.

Подсказка 2

Запишите отношение между aᵢ и aᵢ₋₁.

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

Пусть окрашено $n$ чисел. Упорядочим их по возрастанию:

1= a1 < a2 < ...< an = 320

Заметим, что для любого $k∈ {2,...,n}$ справедливо неравенство

a ≤2a k k−1

Действительно, в противном случае при $i,j <k$ , имеем

a > 2a ≥ a + a k k−1 i j

и мы не сможем представить $ak$ в виде суммы двух красных чисел. Тогда

320= an ≤ 2an−1 ≤4an−2 ≤ ...≤ 2n− 1a1 = 2n−1

Значит, $n− 1≥ 9$ и $n ≥10$ . Осталось привести пример покраски 10 чисел: $1,2,4,5,10,20,40,80,160,320$ .

Ответ: 10

Интенсивы

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

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

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

Как-то на стройку привезли несколько блоков общим весом $100$ пудов. Оказалось, что суммарный вес трех самых легких блоков равняется $25$ пудам, а трех самых тяжелых — $35$ пудам. Каждый блок может весить нецелое число пудов. Сколько блоков могли привезти на стройку?

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

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

Упорядочим блоки по возрастанию. Левые три блока весят $25$ пудов, последние три — $35$ пудов. Значит, блоки посередине весят в сумме $40$ пудов. Если их не больше трех, то они перевешивают три самых тяжелых блока, чего не может быть. Если их пять или больше, то три самых легких из них весят не больше $40 ⋅3∕5= 24$ пудов, чего опять же не может быть. Значит, посередине ровно $4$ блока, а всего блоков $10.$

______________________________________________________________________________________________________________________________________________________

Замечание. Так как по условию сказано, что блоки привезли, то подразумевается, что данная ситуация возможна. Мы доказали, что ответ не более чем единственен, значит, этот единственный ответ подходит, и приводить пример не обязательно. Но можно и привести, достаточно задать вес всех блоков 10 пудов, кроме двух: самый легкий сделать 5 -пудовым, а самый тяжелый - 15 -пудовым.

Ответ:

$10$ блоков

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

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

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

Источники: Турнир городов - 2017, весенний тур, базовый вариант, 9.4

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

Подсказка 1

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

Подсказка 2

Если хотим всех расставить по убыванию, то как будто бы нужно сразу по убыванию и ставить всех. А как бы нам выбрать группы, чтобы 25 самых низких стояли в самом конце - там, где им и нужно стоять? Научитесь переставлять их за 3 хода!

Подсказка 3

Давайте обозначим первые слева 25 мест в ряду буквой A, вторые 25 − B, третьи и четвёртые — C и D. Можем постепенно по убыванию расставлять детей, перемещая 25 низких всё правее и правее

Подсказка 4

То есть можем сначала поставить всех по убыванию в АВ - тогда 25 низких точно не в А, значит они где-то среди ВСD. Потом так же расставляем ВС… Уловили идею? Попробуйте так допереставлять 25 самых низких, а потом аналогично расставить 25 следующих по росту детей!

Подсказка 5

Заметьте, что для правильной расстановки 25 следующих по росту детей нам понадобится всего 2 хода, потому что D мы уже не трогаем, там все правильно стоят. Остаётся последний ход - какой и для чего?

Подсказка 6

Да, расставляем всех из АВ по убыванию! Потому что в С и D все уже верно стоят, осталось расставить по убыванию детей из АВ.

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

Обозначим первые слева $25$ мест в ряду буквой $A,$ вторые $25− B,$ третьи и четвёртые — $C$ и $D.$ Каждый раз, выбирая $50$ детей, будем выстраивать их по убыванию роста. Сделаем это сначала с $AB,$ затем с $BC$ и, наконец, с $CD.$ После первой перестановки $25$ самых низких детей окажутся в куске $BCD,$ после второй — в $CD,$ после третьей — в $D.$ Таким образом, $25$ самых низких детей уже расставлены правильно. Снова выполним перестановки $AB$ и $BC.$ Они расставят в нужном порядке следующих по росту $25$ детей в куске $C.$ Последняя перестановка $AB$ расставит правильно $50$ самых высоких.

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

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

Можно ли число $2016$ представить в виде суммы нескольких попарно различных натуральных чисел таких, что среди всех возможных попарных сумм этих чисел ровно $7$ различных?

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

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

Подсказка 1

Попробуем пойти от противного. Тогда 2016 можно представить в виде суммы n попарно различных чисел. Всего пар чисел можно составить n(n-1)/2. Какая нижняя оценка получается на n?

Подсказка 2

Верно! Должно получиться не менее 7 пар, и поэтому n ≥ 5. С другой стороны, наши числа можно упорядочить по возрастанию. Складывая наименьшее число последовательно со всеми остальными, получим n-1 различное число. А можно ли аналогично получить еще суммы, которые отличаются от уже построенных?

Подсказка 3

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

Подсказка 4

Верно! Всего получится 2n-3 различных числа, а их должно быть не больше 7, поэтому n ≥ 5. Выходит, что n = 5! Теперь легко выписать все возможные суммы наших чисел. Всего получится 10 сумм, а среди них только 7 различных. Причем ранее мы уже указали 7 попарно различных сумм! Попробуем теперь рассмотреть три оставшихся. С какими другими суммами они должны совпадать?

Подсказка 5

Ясно, что мы не рассматривали суммы между вторым и третьим, вторым и четвертым, третьим и четвертым числами. Кроме того, понятно, что они попарно различны. Благодаря тому, что остальные 7 сумм нам удалось упорядочить, можно найти среди них суммы, которые должны совпадать с нашими тремя. Как это сделать?

Подсказка 6

Верно! Они должны совпадать с суммами первого и четвертого, первого и пятого, второго и пятого чисел! Тогда можно вычесть равенства и заметить, что все наши числа образуют арифметическую прогрессию. Могло ли так получиться?

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

Предположим, что $2016$ можно представить в виде суммы попарно различных натуральных чисел $a < a < ...< a 1 2 n$ таких, что среди всех возможных попарных сумм этих чисел ровно $7$ различных. Общее количество пар из $n$ чисел равно $n(n−1) 2$ и должно быть не меньше $7,$ поэтому $n≥ 5.$ С другой стороны, ввиду очевидных неравенств:

a1 +a2 < a1+ a3 < ...< a1 +an < a2+ an < ...< an−1+an

имеем $n− 1+n − 2 =2n− 3≤ 7$ и $n ≤5.$ Следовательно, $n =5$ и каждая невыписанная попарная сумма чисел $a <a < ...< a 1 2 n$ равна одной из семи сумм, рассмотренных в длинном неравенстве. Всего нерассмотренных сумм три:

a2+ a3 < a2+a4 <a3+ a4

и все они больше $a1+a3$ и меньше $a3+ a5.$ По условию, они должны совпадать с суммами

a + a < a +a <a + a 1 4 1 5 2 5

в указанном порядке. Отсюда: $a2− a1 =a4− a3 = a5− a4 =a3− a2,$ следовательно, числа $a1 < a2 < ...< a5$ образуют арифметическую прогрессию. Тогда их сумма равна $5⋅ a1+2a5= 2016$ , откуда следует, что число $4032$ должно делиться на $5$ — противоречие.

Ответ:

Нельзя

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

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

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

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

Подсказка 1

Хм, среднее арифметическое любых трёх чисел тоже записано на доске, довольно сильное заявление. А можем ли мы выбрать 3 числа так, чтобы точно определить, какое из чисел будет их средним арифметическим?

Подсказка 2

Можно упорядочить все числа - допустим это a₁ ≤ a₂ ≤ ... ≤ a₁₀, и выбрать 3 числа, идущие подряд - где тогда должно быть их среднее арифметическое?

Подсказка 3

Конечно, это число, стоящее посередине! А значит, можно записать много уравнений и поработать с ними, или присмотреться ещё к написанному равенству: если привести подобные слагаемые, что можно сказать об этих трёх числах, что они образуют?

Подсказка 4

Арифметическую прогрессию! А что будет с числом справа или слева от тройки, будет ли оно в той же прогрессии? Тогда какой вид имеют все числа на доске? Точно ли все средние арифметические записаны?

Подсказка 5

Получили, что все числа имеют вид a₁ + n ⋅ d, где d - разность прогрессии. Попробуйте теперь рассмотреть тройку не подряд идущих чисел - записано ли её среднее арифметическое на доске?

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

Предположим противное. Упорядочим данные числа и обозначим их за $a ,a,a ,...,a , 1 2 3 10$ что $a ≤a ≤ a ≤ ...≤ a . 1 2 3 10$ Заметим, что если мы рассматриваем тройку вида $ai,ai+1,ai+2,$ то в силу соображения, что среднее арифметическое чисел лежит между их минимумом и максимумом, среднее арифметическое данной тройки будет равно $ai+1.$

Рассмотрим сначала тройку $a1,a2,a3 :$

a1+ a2+a3 ----3---- =a2

a1 +a3 = 2a2

a1+ a3 --2---= a2

Следовательно, $a1,a2$ и $a3$ образуют арифметическую прогрессию. При этом если её разность нулевая, т.е. эти числа равны, то, рассматривая тройки вида $ai,ai+1,ai+2,$ мы получим, что все числа равны, поэтому данная прогрессия имеет ненулевую разность.

Аналогично рассмотрев тройку $a2,a3,a4,$ показываем, что эти числа тоже образуют арифметическую прогрессию. Пусть $a1,a2,a3$ и $a4$ — это арифметическая прогрессия с ненулевой положительной разностью $d,$ тогда $a2 = a1+ d$ и $a4 =a1+ 3d.$ Рассмотрим тройку $a1,a2,a4 :$

a1+a2+-a4 a1+-a1+-d+a1+-3d 3a1+-4d- 4 3 = 3 = 3 = a1+ 3d

Но такого числа нет на доске, противоречие.

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

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

Бумажный квадрат со стороной $100$ разрезали $99$ вертикальными и $99$ горизонтальными прямыми, получив таким образом $10000$ прямоугольников (необязательно с целыми сторонами). У какого наименьшего количества прямоугольников площадь может оказаться меньшей или равной $1?$

Источники: СпбОШ - 2015, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

Такс... сперва давайте обозначим как-то длины отрезков, на которые разбиты стороны. Например, пусть одна сторона разбита на отрезки a₁ ≤ a₂ ≤ ... ≤ a₁₀₀, а другая на отрезки b₁ ≤ b₂ ≤ ... ≤ b₁₀₀. На какую оценку намекает формула площади прямоугольника и сумма длин отрезков?)

Подсказка 2

Конечно! Т.к. площадь прямоугольника это ab, то можно воспользоваться неравенством о средних. Как это сделать?

Подсказка 3

Давайте рассмотрим числа √a₁*√b₁₀₀, √a₂* √b₉₉, ..., √a₁₀₀*√b₁. По неравенству о средних √a*√b ≤ (a+b)/2. Как тогда можно оценить сумму этих чисел?

Подсказка 4

Да! Их сумма не превосходит половины суммы всех aᵢ и bᵢ, т.е. не превосходит 100. О чем это говорит?

Подсказка 5

Верно! Тогда можно сказать, что найдётся такой номер j, что aⱼb₁₀₀ -ⱼ≤ 1. Теперь осталось рассмотреть индексы, меньше j для a и 100 - j для b и показать, что таких пар ≥100. Не забудем построить пример!!!

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

Пример.

Одну из сторон разобьём на $100$ отрезков длины $1,$ а другую — на $99$ отрезков длины $1,01$ и оставшийся отрезок длины $0,01$ . Тогда только $100$ прямоугольников с узкой стороной длины $0,01$ имеют площадь меньше $1.$
Оценка.

Первый способ
Пусть одна из сторон разбита на отрезки длины $a1 ≤ a2 ≤...≤a100,$ а другая — на отрезки $b1 ≤b2 ≤ ...≤ b100.$ Рассмотрим числа $√ -----√---- a1b100, a2b99$ , $√ ----- ..., a100b1.$ В силу неравенства $√ -- a+b ab ≤ 2 ,$ сумма всех этих чисел не превосходит половины суммы всех $ai$ и $bi,$ т.е. не превосходит $100.$ Поэтому найдётся такой номер $j,$ что $ajb101−j ≤ 1.$ Но тогда и для всех пар $k,n$ при $k ≤j,n≤ 101− j$ тоже выполнено неравенство $akbn ≤ 1,$ причём количество таких пар равно $j(101− j)≥ 100.$ Это значит, что все прямоугольники со сторонами $ak$ и $bn$ имеют площадь не больше $1,$ и число этих прямоугольников не меньше $100.$
Второй способ
Пусть одна из сторон разбита на отрезки длины $a0,a1,...,a99,$ а другая — на отрезки $b0,b1,...,b99.$ Для удобства будем считать, что отрезки занумерованы остатками от деления на $100.$ Возьмём произвольное $k$ от $0$ до $99$ и рассмотрим выражение

∘ ---- ----- ----- ------- ( a0bk+ ∘a1bk+1 +∘ a2bk+2+ ...+ ∘a99bk+99)2.

По неравенству Коши-Буняковского-Шварца оно не превосходит

(a0+a1+ ...+ a99)(bk+ bk+1+...+bk+99)= 1002.

Следовательно, $√---- ∘ ----- ∘----- ∘ ------- a0bk+ a1bk+1+ a2bk+2 +...+ a99bk+99 ≤100,$ и значит, одно из его слагаемых не превосходит $1.$ Стало быть, мы доказали существование прямоугольника малой площади, у которого номера сторон различаются ровно на $k.$ А поскольку $k$ может быть любым числом от $0$ до $99,$ существует не менее $100$ таких прямоугольников.

Ответ:

$100$

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

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

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

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

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

Источники: ММО - 2012, 9.1(см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Упорядочим провинции по возрастанию населения. Какие провинции могут быть крупными?

Подсказка 3

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

Подсказка 4

В первых двух провинциях, поскольку они крупными не являются, проживает не более 7% населения, а вместе не более 14%. Тогда в третьей провинции проживает менее 14% населения. Можно ли оценить наименьшее число провинций, продолжая рассуждать аналогично?

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

Сначала упорядочим все провинции по возрастанию населения. Первая и вторая провинция крупными являться не могут, поскольку две провинции с меньшим населением для них просто не найдутся. Чем больше крупных провинций, тем меньше число провинций, поэтому для нижней оценки можно полагать, что каждая новая провинция крупная. В третьей провинции живет не более $14%$ населения, поскольку в первой и второй провинции в сумме проживает не более $14%$ жителей. Аналогично получаем, что в четвертой провинции не более $21%$ жителей, а в пятой не более $35%.$ Теперь заметим, что суммарно в первых пяти провинциях проживает не более $7+ 7+14+ 21+ 35 =84$ процентов жителей страны. Таким образом, провинций не менее $6.$ В качестве примера берем $6$ провинций со следующим распределением доли жителей: $7%,$ $7%,$ $11%,$ $16%,$ $25%,$ $34%.$

Ответ:

$6$

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

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

Некоторые из чисел $a,a ,...,a 1 2 200$ написаны синим карандашом, а остальные — красным. Если стереть все красные числа, то останутся все натуральные числа от $1$ до $100,$ записанные в порядке возрастания. Если же стереть все синие числа, то останутся все натуральные числа от $100$ до $1,$ записанные в порядке убывания. Докажите, что среди чисел $a1,a2,...,a100$ содержатся все натуральные числа от $1$ до $100$ включительно.

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

Подсказка 1

Нужно доказать, что среди первых 100 чисел есть все числа от 1 до 100. Очень много чисел… Может можно доказать в общем случае, что какое-то число n есть среди первых 100?

Подсказка 2

А что будет, если этого числа n нет среди первых 100?

Подсказка 3

Ага, n будет где-то среди последних 100! Но при этом есть синие числа от 1 до 100, и красные числа от 1 до 100, то есть оба n находятся среди последних 100 чисел. Теперь надо бы найти противоречие, а его можно искать в количестве чисел до наших n: не зря же мы все n поместили во вторую половину чисел!

Подсказка 4

Сколько синих чисел до синего n? А до красного?

Подсказка 5

Оцените количество чисел до первого n с двух сторон: с одной стороны оно не превышает количества синих + количества красных до n, а с другой стороны первое n стоит хотя бы на 101 месте, тогда их больше чем…

Подсказка 6

Увидели противоречие? Тогда любое n от 1 до 100 находится среди первых 100, а значит мы доказали утверждение!

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

Заметим, что каждое из чисел от $1$ до $100$ встречается ровно $2$ раза: один раз оно записано синим карандашом и один — красным. Предположим, что среди чисел $a1,a2,...,a100$ нет какого-то числа $1≤ n≤ 100.$ Тогда синее $n$ и красное $n$ находятся среди $a101,a102,...,a200.$

$1)$ Сотрём все красные числа — остались синие от $1$ до $100,$ записанные в порядке возрастания, и среди них есть синее $n.$ До него записаны числа от $1$ до $n − 1,$ то есть ровно $n− 1$ число.

$2)$ Сотрём все синие числа — остались красные от $100$ до $1,$ записанные в порядке убывания, и среди них есть красное $n.$ До него записаны числа от $100$ до $n+ 1,$ то есть ровно $100− n$ чисел.

Тогда до первого $n$ записано не более $n− 1+ (100− n)= 99$ чисел. Но так как первое n записано среди чисел $a101,a102,...,a200,$ то до $n$ записано как минимум $100$ чисел. Противоречие.

Значит, предположение было неверным, и среди чисел $a1,a2,...,a100$ есть все числа от $1$ до $100.$

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

Следующая подтема