Тема Алгебраические текстовые задачи

Конструктивы в алгебре

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

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

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

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

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

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

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

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

Число $x$ таково, что $sin x+tgx$ и $cosx+ ctgx$ — рациональные числа. Докажите, что $sin2x$ является корнем квадратного уравнения с целыми коэффициентами.

Источники: ВСОШ, ЗЭ, 2023, 11.1 (см. olympiads.mccme.ru)

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

Подсказка 1:

Ясно, что sin(2x) выражается через sin(x)cos(x). Если найти уравнение с таким корнем, то будет несложно получить корень sin(2x).

Подсказка 2:

Давайте заметим, что выражения a + b и ab будут целыми и инвариантными относительно перестановки синуса и косинуса. Почему бы в дополнение к выражению v = sin(x)cos(x) не взять выражение u = sin(x) + cos(x) и попробовать выразить ab и a + b через u и v?

Подсказка 3:

Вы должны были получить такие равенства: a + b = u + 1/v, ab = v + u + 1. Как из них получить нужное уравнение?

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

Положим $a= sinx+ tgx$ и $b= cosx+ ctgx.$ Введём обозначения:

u= sinx+ cosx

v = sinxcosx

По условию рациональными являются числа

c =a+ b= u+ v−1

d =a⋅b= v+ u+ 1

Отсюда

k= d− c= v+1 − v−1

Значит,

t= sin2x= 2v

является решением квадратного уравнения

2 t + 2t− (4+ 2kt)= 0

с рациональными коэффициентами, откуда следует требуемое.

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

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

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

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

В пяти корзинах лежат яблоки двух сортов так, что в каждой корзине есть яблоки только одного сорта. Известно, что в первой корзине находится 20 яблок, во второй — 30 , в третьей — 40 , в четвёртой — 60, в пятой — 90. После того, как содержимое одной из корзин полностью продали, яблок первого сорта стало в два раза больше, чем яблок второго сорта. Сколько яблок могло быть в проданной корзине? Если ответов несколько, укажите их все через пробел в порядке возрастания.

Источники: ВСОШ - 2022, школьный этап, 9 класс

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

Подсказка 1

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

Подсказка 2

Изначально было 240 яблок, что тоже делится на 3. Поэтому в проданной корзине не могло быть яблок, чьё количество не делится на 3, так как разность двух чисел, делящихся на 3, тоже делится на 3!

Подсказка 3

Остались варианты: 30, 60, 90. Однако обязательно надо проверить, что оставшееся количество яблок первого или второго сорта мы сможем набрать, используя оставшиеся корзины, так как в каждой должны лежать яблоки только одного сорта

Подсказка 4

Именно по этой причине в проданной корзине 30 яблок быть не может, так как второго сорта останется (240-30)/3 = 70 штук, и мы не сможем их разложить в коризны на 20, 40, 60, 90. Осталось проверить варианты на 60 и 90 яблок и, если все хорошо, привести примеры

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

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

Если яблок первого сорта стало в два раза больше яблок второго сорта, то общее количество оставшихся яблок должно делиться на $3$ . Первоначальное количество яблок равно $20+ 30+40+ 60+ 90 =240$ штук. Так как $240$ делится на $3$ , то количество убранных яблок тоже должно делиться на $3$ . Поэтому варианты на $20$ и $40$ яблок не подходят. Если убрали $30$ яблок, то яблок второго сорта должно быть $(240− 30):3= 70$ штук. Но $70$ штук нельзя набрать используя корзины на $20, 40$ и $60$ яблок.

Осталось проверить, что ответы $60$ и $90$ достигаются. Для этого надо предъявить примеры, как могли быть распределены яблоки по группам (сортам), чтобы количество яблок в одной группе было в два раза больше, чем в другой. Действительно:

40 +60= 2(20+ 30),если убрали 90 яблок;

30 +90= 2(20+ 40),если убрали 60 яблок.

Ответ: 60 90

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

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

Можно ли множество из $2017$ чисел

{log25,log26,log27,...,log22021}

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

Источники: Росатом-2022, региональный вариант, 11.5 (см. olymp.mephi.ru)

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

Подсказка 1

Во-первых, давайте сначала хоть как-то разобьем на две группы, а потом будем как-то менять элементы в группах, уменьшая модуль разности. Разобьем на группы так, что в первой группе в аргументе логарифма были только нечетные числа, а в другой только четные. В какой группе больше сумма? Модуль разности больше 1? Как модуль разность можно уменьшить, если мы дошли до идеи менять местами какие-то числа в разных группах?

Подсказка 2

Ну конечно, где нечетные, там сумма больше, при том, больше 1, так как у нас разность log_2(2k + 1) - log_2(2k) > 0, для всех k от 3 до 1010, а еще плюсом прибавляется log_2(5) > 1. Значит, на текущий момент модуль разности больше 1. Тогда давайте попробуем из поменять местами числа log_2(2021) и log_2(2020). Тогда у нас разность уменьшится, при том на сколько меньшее 1. Ну мы чуть-чуть улучшили ситуацию. А что нам мешает делать дальше также?

Подсказка 3

Верно, ничего. Главное понимать, что при каждой такой замене у нас будет уменьшаться разность и ни в какой момент, она не может перепрыгнуть с чего-то, что больше 1, на что-то что меньше -1, из-за того, что уменьшаем не более чем на 1. Тогда у нас рано или поздно модуль станет меньше 1, так как в начальный момент разность больше 1, а в конечный меньше -1(когда мы полностью поменяли группы). Значит, победа!

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

На первом шаге в группе $A$ разместим логарифмы нечетных чисел, а в группе $B$ — четных:

A = {log25,log27,log29,...,log22021}

B ={log26,log28,log210,...,log22020}

Обозначим через $σA,σB$ суммы чисел в группах $A$ и $B$ соответственно. Покажем, что $σA − σB > 1.$ Действительно,

(|| log27> log26 |||{ log29> log28 | .. ⇒ σA− log25> σB ⇒ σA− σB > log25 >1 ||||( . log22021> log22020

Перенесем число $log22021$ из группы $A$ в группу $B,$ а число $log2 2020$ наоборот — из $B$ в $A.$ Поскольку $log2 2021> log22020$ разность $σA − σB$ уменьшилась на величину

2021 ( 1 ) log22021− log2 2020= log22020 = log2 1+ 2020 < 1

Если для вновь образованных множеств $A$ и $B$ разность $σA − σB >0,$ меняем местами числа $log22019$ и $log22018.$ По-прежнему, разность $σA − σB$ уменьшается на величину

log22019− log22018= log2 2019< 1 2018

Если разность $σA− σB > 0,$ по процесс перекладывания чисел из одного множества в другое может быть продолжен. Если на каком-то шаге $σA − σB$ поменяет знак, то $|σA− σB|<1$ и искомое разбиение достигнуто. Это обязательно произойдет за конечное число шагов, поскольку замена множеств $A$ и $B$ местами приводит к смене знака величины $σA − σB.$

Ответ: да

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

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

На прямой отмечено $n+ 1$ различных отрезков; одна из точек прямой принадлежит всем этим отрезкам. Докажите, что среди отмеченных отрезков можно выбрать различные отрезки $I$ и $J,$ пересекающиеся по отрезку длины, не меньшей $n−-1 n d,$ где $d$ — длина отрезка $J.$

Источники: Всеросс., 2017, ЗЭ, 9.3(см. olympiads.mccme.ru)

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

Первое решение. Введём координаты на нашей прямой. Пусть данные отрезки — это $I = [a ;b],I = [a;b],I = [a ;b]; 0 0 0 1 1 1 n n n$ нумерацию отрезков выберем так, что $a0 ≤a1 ≤ ...≤ an.$ Если $bk ≥ bk+1$ при некотором $k,$ то отрезок $Ik$ содержит $Ik+1,$ и потому отрезки $I =Ik+1$ и $J = Ik$ — искомые. Поэтому в дальнейшем мы считаем, что $b0 <b1 < ...< bn.$

Рассмотрим $2n$ отрезков $[a0;a1], [a1;a2],...,[an−1;an],[b0;b1],[b1;b2],...,[bn−1;bn]$ (некоторые из них могут иметь нулевую длину). Рассмотрим кратчайший из них — пусть для определённости это $[ak;ak+1],$ а его длина равна $ℓ.$ Тогда

bk− b0 = (bk − bk−1)+(bk− 1− bk−2)+...+(b1 − b0)≥kℓ

и, аналогично,

an− ak = (an− an−1)+(an−1− an−2)+ ...+ (ak+1− ak)≥(n− k)ℓ

Поскольку $In$ и $I0$ имеют общую точку, имеем $b0 ≥an,$ откуда

bk − ak ≥ (bk − b0)+(an− ak) ≥kℓ+ (n − k)ℓ= nℓ

Итак, длина $d$ отрезка $Ik$ не меньше, чем $nℓ.$ Иначе говоря, часть $[ak;ak+1]$ этого отрезка, лежащая вне $Ik+1,$ имеет длину, не превосходящую $d∕n.$ Поэтому отрезки $I =Ik$ и $J = Ik+1$ -искомые.

Второе решение. Пусть данные отрезки — это $I0 = A0B0$ , $I1 = A1B1,...,In =AnBn.$ Как и в предыдущем решении, мы сводим задачу к случаю, когда точки $A0,A1,...,An$ пронумерованы слева направо, и так же пронумерованы точки $B0,B1,...,Bn.$

При всех $k= 0,1,...,n,$ отметим на отрезке $I k$ точку $C k$ так, что

AkCk :CkBk = (n − k):k

Таким образом, точка $C0 = B0$ находится не левее точки $Cn = An.$ Значит, найдётся индекс $k,$ при котором точка $Ck$ находится не левее точки $Ck+1.$ Выберем такой индекс $k$ и положим $d= min(AkBk,Ak+1Bk+1).$ Заметим, что точки $Ak,Ak+1,Ck+1,Ck,Bk,Bk+1$ лежат на прямой именно в таком порядке слева направо. Тогда

A B ≥ A C +C B = n−-k− 1-A B + k A B ≥ k+1 k k+1 k+1 k k n k+1 k+1 n k k ≥ n−-k−-1d+ kd= n-− 1d n n n

Это и значит, что длина общей части отрезков $Ik$ и $Ik+1$ не меньше, чем $n−1d, n$ где $d$ — длина одного из них.

Замечание. Нетрудно привести пример $n +1$ попарно пересекающихся отрезков одинаковой длины $d,$ любые два из которых пересекаются по отрезку длины, не превосходящей $n-− 1d. n$

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

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

Существует ли описанный 2021-угольник, все вершины и центр вписанной окружности которого имеют целочисленные координаты?

Источники: Тургор - 2021, 11.6, устный тур (см. turgor.ru)

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

Подсказка 1

Есть два возможных ответа - да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что ну кажется очень непростой задачей. Тогда будем доказывать, что ответ «да».

Подсказка 2

Если мы хотим, чтобы верхняя целая часть A^n отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t + 1/t в квадрат?

Подсказка 3

Хотелось бы сделать так, чтобы число вида A^n + 1/A^n было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/t^2n = (t^n + 1/t^n)^2 - 2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида A^n + 1/A^n, при A = t^2, было бы целым.

Подсказка 4

Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a + b * sqrt(c))^k, где a, b, k - целые, это выражение вида t + l * sqrt(c). Заметьте, это верно и для отрицательных k.

Подсказка 5

Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t + 1/t = c, где с - целая положительная константа.

Подсказка 6

Тогда, по модулю факта про возведение таких иррациональностей в степень, можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k - целое, а значит, нашли подходящее А.

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

Будем называть точку с рациональными координатами рациональной. Рассмотрим окружность $x2 +y2 = 1$ . Докажем, что на ней существует сколь угодно много рациональных точек.

Рассмотрим прямую вида $y =kx+ 1$ с рациональным $k$ . Она проходит через точку $(0,1)$ окружности, и вторая точка пересечения с окружностью тоже будет рациональной (поскольку квадратное уравнение $2 2 x + (kx +1) = 1$ с рациональными коэффициентами имеет рациональный корень 0 , второй корень также рационален).

Выбирая разные рациональные $k$ , отметим на окружности 2021 рациональную точку, включая точки $(−1,0),(1,0),(0,1),(0,− 1)$ . Через каждую из этих 2021 точек проведём касательную к окружности и отметим точки пересечения соседних касательных, получим описанный 2021-угольник (строго это можно обосновать, например, так: сначала получим описанный квадрат, проведя касательные в четырёх указанных точках, а затем по очереди проведём остальные касательные: каждая будет отсекать от уже имеющегося многоугольника треугольник, примыкающий к вершине).

Заметим, что уравнения касательных имеют рациональные координаты (поскольку касательные перпендикулярны прямым, соединяющим начало координат с рациональными точками касания). Точка пересечения прямых с рациональными координатами рациональна (как единственное решение системы линейных уравнений с рациональными коэффициентами). Значит, вершины нашего 2021-угольника рациональны. Приведём координаты вершин к общему знаменателю $N$ и рассмотрим гомотетию с центром в начале координат и коэффициентом $N$ . Она переведёт наш 2021-угольник в удовлетворяющий условию задачи.

Ответ: да

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

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

Существует ли такое натуральное $n,$ что для любых вещественных чисел $x$ и $y$ найдутся вещественные числа $a ,a ,...,a , 1 2 n$ удовлетворяющие равенствам

1 1 1 x =a1+ a2+ ...+an; y = a1 + a2 + ...+ an?

Источники: Турнир городов - 2021, весенний тур, сложный вариант, 11.2

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

Подсказка 1:

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

Подсказка 2:

Вот вам одна из идей, как построить пример. Придумайте при некотором n такое разложение для пары (x, 0). Тогда разложение для (x, y) вы сможете получить из 2n слагаемых как сумму разложений (x, 0) и (0, y).

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

Докажем, что подходит $n= 6.$ Предварительно заметим, что любую пару $(0,y)$ с ненулевым $y$ можно получить так:

3- 3- 3 2y 2y y 0= 2y + 2y − y,y = 3 + 3 − 3

Аналогично можно получить любую пару $(x,0)$ с ненулевым $x.$ Тогда любую пару $(x,y)$ с отличными от нуля $x$ и $y$ можно получить как «сумму» двух рассмотренных выше пар. Пару $(x,0)$ можно получить как сумму двух пар $(x2,0),$ аналогично можно получить пару $(0,y),$ а пару $(0,0)$ — как $1+ 1+ 1− 1− 1− 1.$

Ответ:

Существует

Курсы

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

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

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

Территория Тридесятого царства состоит из всех целых чисел. Княжеством будем называть множество вида ${ak+ b|k∈ ℤ}$ , где $a ⁄=0$ и $b−$ некие целые числа (то есть бесконечную в обе стороны арифметическую прогрессию). Царь хочет разделить всю территорию царства, кроме чисел 3 и 10 , на бесконечное количество непересекающихся княжеств. Возможно ли это?

Источники: ФЕ - 2021, 10.4 (см. www.formulo.org)

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

Подсказка 1

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

Подсказка 2

Чётное и нечётное, делится на 3 и даёт остаток 1... Давайте попытаемся отдельно разбить чётные и нечётные числа. Одно из ключевых свойств — делимость. Попробуйте разбить все чётные числа кроме 0 (в том числе 10) на непересекающиеся княжества.

Подсказка 3

Для этого можно воспользоваться делимостью — брать число в княжество в том случае, если оно делится на какое-то число, а на другое не делится. Тогда 0 никуда не попадёт!

Подсказка 4

Тут можно поиграться со степенями двойки — брать число в княжество, если оно делится на 2ⁿ, но не делится на 2ⁿ⁺¹. Чему в таком случае будут равны a и b? И останется только придумать, как исключить 3 и 10 при помощи того, что 0 не в княжествах.

Подсказка 5

Выходит, что a = 2ⁿ⁺¹, b = 2ⁿ. А чтобы исключить 3 и 10, нужно сделать "сдвиг" княжеств. Брать число в них не в случае делимости, а в случае каких-то остатков от деления.

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

Будем отдельно разбивать чётные числа и нечётные, тогда надо дважды разбить прогрессию без одной точки. Покажем, как это сделать для нечётных: поместим нечётное число $x$ в княжество $s$ , если $x− 3$ кратно $s 2$ , но не кратно $s+1 2$ . Для чётных аналогично.

Ответ: да

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

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

Дан клетчатый прямоугольник $2m ×2n$ , разбитый произвольным образом на доминошки $2× 1$ .

Если две доминошки образуют квадрат $2× 2$ , разрешается повернуть их обе на $∘ 90$ (сделать флип). Наша цель — последовательностью флипов сделать все доминошки горизонтальными (кирпичная кладка) за как можно меньшее количество операций.

Раскрасим наш прямоугольник в шахматную раскраску, считая левый нижний угол черным. Направим по сторонам квадратиков стрелочки так, чтобы черные квадратики обходились бы против часовой стрелки, а белые — по часовой стрелке.

Пусть нам дано некоторое замощение прямоугольника доминошками, которое мы обозначим через T. Сопоставим замощению его функцию высоты — это будет функция на вершинах клеток нашего прямоугольника, которую мы будем обозначать $HT (v)$ .

Определим её следующим образом. Выберем левую нижнюю вершину $v0$ прямоугольника и положим ее высоту равной нулю; далее, каждую вершину $v$ соединим с $v0$ путем, который проходит по линиям сетки и не пересекает доминошек. Этот путь состоит из стрелок, каждая из которых проходится либо в попутном направлении (т. е. сонаправлена с путем), либо в противоположном. Положим высоту $HT(v)$ равной разности числа попутных и противоположно направленных стрелок.

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

| | hT(v)= |HT(v)− HTmin(v)|. 4

Назовём рангом замощения $T$ число $r(T)=∑v hT(v)$ . Докажите, что любое замощение $T$ можно превратить в кирпичную кладку за $r(T)$ флипов, причём за меньшее количество флипов это сделать невозможно.

Источники: Иннополис - 2021, 11.3 (см. dovuz.innopolis.university)

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

Подсказка 1

Попробуйте доказать, что функция высоты H(T) задаёт разбиение единственным образом.

Подсказка 2

Давайте посмотрим на 2 вершины u и v, соединённые ребром (для определённости ребро от u к v). Попробуем проследить взаимосвязь между H(v) и H(u). Точно! H(v) = H(u) + 1 или H(v) = H(u) - 3. После этого попробуйте все клетки поля разбить на пары по какому-нибудь принципу.

Подсказка 3

Попробуем доказать утверждение задачи с помощью индукции по величине r(T). Заметим, что если r(T) = 0, то доказывать ничего не надо, то есть для нашей индукции уже есть база. Как же делать переход? Рассмотрим для какого-то замощения T функцию |H(t)|, посмотрим на вершины, в которых эта функция достигает максимум. Ага! Если функция достигает максимума в какой-то точке v, то в этой точке всегда можно сделать флип.

Подсказка 4

После флипа в вершине v приведённая высота в вершине v уменьшится на 1, т.е. мы получим новое замощение T2, для которого r(T2) = r(T) - 1. Теперь, связав 3 и 4 пункт вместе, соберём индукцию целиком!

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

Утверждение. Функция высоты $H T$ задаёт разбиение единственным образом.

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Покажем, что для любых соседних вершин $u$ и $v,$ ребро между которыми направлено от $u$ к $v,$ либо $HT (v)= HT(v)+1,$ либо $HT (v)= HT(u)− 3$ . Действительно, первый случай реализуется, когда стрелка от от $u$ к $v$ — это стрелка на границе доминошки, а второй случай сотвествует тому, что это стрелка, которая разделяет доминошку на две половинки.

Рассмотрим те рёбра, разность функций высоты на концах которых равна $1$ . Эти рёбра будут образовывать границы доминошек нашего разбиения; напротив, те ребра, разность функций высоты на концах которых равна $− 3$ , будут «закрыты» доминошками. Далее рассмотрим какую-нибудь клетку. Все стрелки на её границе направлены в одном направлении: либо по часовой стрелке, либо против. Поскольку сумма приращений функции высоты при обходе этой клетки равна нулю, это значит, что существует ровно три ребра из четырех, для которых разность значений функции высоты на их концах равна единице, и одно ребро, для которого эта разность равна минус трём; оно и будет закрыто доминошкой. То же самое можно будет сказать и про клетку, смежную с данной по этому ребру. Тем самым все клетки окажутся разбитыми на пары, то есть в итоге из функции высоты действительно однозначно получится замощение нашего прямоугольника.

_________________________________________________________________________________________________________________________________________________________________________________

Будем вести индукцию по величине $r(T)$ .

Если $r(T)= 0$ , доказывать нечего, т.к. тогда $HT = HTmin$ , и, согласно утверждению выше, $T = Tmin$ . В противном случае рассмотрим в замощении $T$ функцию $|HT |$ , пусть $v1$ — вершина, в которой эта функция достигает глобального максимума (если таких вершин несколько, выберем любую из них). Заметим, что в этой вершине можно сделать флип. Действительно, рассмотрим квадрат $2× 2$ , центром которого является вершина $v1$ . Тогда или горизонтальные, или вертикальные ребра, выходящее из $v1$ , должны быть закрыты доминошками разбиения $T$ (если из вершины $v1$ выходит и горизонтальное, и вертикальное ребра, то, сдвинувшись по одному из них, можно увеличить значение $|HT (v1)|$ , что невозможно, т.к. $v1$ — точка максимума). Значит, квадрат $2× 2$ действительно разбит на две доминошки, и флип возможен.

Сделаем флип с центром в этой точке. Данный флип уменьшит приведеную высоту вершины $v1$ на $1,$ а высоты остальных вершин оставит без изменений. Так мы получим новое замощение $T′$ , для которого $r(T′) =r(T)− 1$ . Применяя предположение индукции, получаем требуемое.

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

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

Заданы квадраты со сторонами $a = 2020 n n$ , для $n= 1,2,...$ Можно ли все квадраты, начиная со второго, уложить в первый квадрат без наложений?

Источники: Газпром - 2021, 11.4 (см. olympiad.gazprom.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Обратите внимание на то, что сумма обратных степеней двоек как раз равна 1!

Подсказка 4

Можно ли разбить наши квадраты на группы так, чтобы одна группа помещалась в прямоугольник с длиной 2020/2ⁿ?

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

Разделим квадраты на группы так, чтобы количество квадратов в группе было ровно 2 в степени номера группы:

(2020 2020) ( 2020 2020 2020 2020) -2--;-3- , -4-;-5-;--6-;-7-- ,...

Сумма длин сторон квадратов в $n$ -ой группе равна

( ) ( ) 2020 -1n + n1---+...+-n+11--- <2020⋅ -1n +-1n +...+ 1n- = 2020⋅1 =2020 2 2 +1 2 − 1 ◟2---2-n◝◜-----2-◞ 2 раз

Квадраты $n$ -ой группы помещаются рядом в прямоугольник с высотой $202n0 2$ и шириной 2020. Помещая эти прямоугольники, содержащие группы квадратов, один на другой, получим прямоугольник шириной 2020 и высотой, равной сумме высот прямоугольников:

2020(1+ -1 +-1 +-1 +...+ -1 +...) = 2020 2 22 23 24 2n

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

Ответ:

Да

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

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

Устройство принимает на вход и выдает на выход наборы из $n$ битов (причем $n ≥4$ ). Поданный на вход набор $x = (x ,...,x ) 1 n$ преобразуется в выходной набор

h(x)= (x1⊕ xn−1,x2 ⊕xn,x2⊕x3,x3⊕ x4,...,xn−2⊕ xn−1,x1⊕ xn),

где $⊕$ — стандартная операция сложения битов: $0⊕ 0= 1⊕1 =0,0⊕1 =1 ⊕0= 1$ .

Подав теперь этот набор $h(x)$ на вход, получим на выходе набор $h(h(x ))= h(2)(x)$ , который вновь подадим на вход и получим $h(3)(x)$ и т.д.

Докажите, что если все наборы

(2) (k) x,h(x),h (x),...,h (x)

оказались различными, то $k≤ 2n− 1− 1$ .

Источники: Верченко - 2021, 11.6 (см. v-olymp.ru)

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

Подсказка 1

Заметим, что для всех x вектор h(x) содержит четное число единиц. Сколько всего существует векторов, в которых единиц чётное число?

Подсказка 2

Конечно, 2ⁿ⁻¹. Значит, нам нужно улучшить нашу оценку всего на 1. Если встретятся все векторы с чётным число единиц, то встретится и нулевой. Какие векторы с чётным числом нулей могут перейти в него?

Подсказка 3

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

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

Заметим, что для всех $x$ вектор $h(x)$ содержит четное число единиц, так как

(x1⊕ xn−1)⊕(x2⊕ xn)⊕(x2⊕ x3)⊕ (x3 ⊕x4)⊕...⊕(xn−2⊕ xn− 1)⊕ (x1 ⊕xn)= 0.

Значит, в рассматриваемой последовательности

(2) (k) x,h(x),h (x),...,h (x)

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

n−1 k≤ 2 .

Для получения оценки $k≤ 2n−1− 1$ рассмотрим отдельно случай когда среди векторов последовательности (*) нет нулевого вектора $(0,0,...,0)$ и когда он есть.

Если в последовательности (*) нет вектора $(0,0,...,0)$ , то она содержит не более $1+ (2n−1− 1)= 2n− 1$ векторов и

k≤ 2n−1− 1.

Пусть теперь последовательность (*) содержит вектор ( $0,0,...,0$ ). Рассмотрим два случая.

1) Если $n$ — нечетное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и других векторов, переходящих в нулевой нет. При этом не существует векторов $z$ таких, что

h(z)= (1,1,...,1)

Таким образом в этом случае последовательность (*) содержит максимум два вектора и

k≤ 2n−1− 1.

2) Если $n$ — четное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и найдутся два вектора

a= (0,0,1,0,1,...,0,1,1) и b= (1,1,0,1,0,1,...,0,1,0,0),

содержащие четное число единиц такие, что

h(a)=h(b)= (1,1,...,1).

Последовательность (*) не может содержать одновременно векторы $a$ и $b$ , поэтому в этом случае она содержит не более $( n− 1 ) n−1 1+ 2 − 1 = 2$ векторов, так что

k≤ 2n−1− 1.

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

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

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

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

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

Подсказка 1

Давайте для начала научимся представлять нечетные числа. Пусть есть число 2k + 1. Где такое выражение встречается в контексте квадратов?

Подсказка 2

Верно! Если прибавить к 2k + 1 число k², то получим (k+1)². Попробуйте что-то похожее придумать для четных.

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

Для нечётных чисел подойдет представление

( 2 2) (2 2) 2k+ 1= (k +1) +0 − k +0

а для чётных

( 2 2) ( 2 2) 2k = (k+ 1) + 0 − k +1 .

Интенсивы

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

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

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

На доске написаны функции: $x+1,x2+ 1,x3+ 1,x4+ 1.$ Разрешается дописывать на доску новые функции, получаемые из написанных на доске с помощью операций вычитания и умножения. Покажите, как получить ненулевую функцию, которая при положительных значениях аргумента принимает неотрицательные значения, а при отрицательных значениях аргумента — неположительные значения.

Источники: Всеросс., 2020, РЭ, 11.6(см. olympiads.mccme.ru)

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

Например, подходит $(x4+1)(x+1)− (x4 +1)= x(x4+ 1).$

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

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

Докажите, что существуют такие последовательности натуральных чисел $a n$ и $b , n$ что одновременно выполнены следующие условия:

- последовательности $an$ и $bn$ являются неубывающими;

- последовательности $-1 -1 -1 An =a1 +a2 +...+ an$ и $1- 1- -1 Bn = b1 + b2 +...+ bn$ неограниченно возрастают;

- последовательность $---1--- ---1--- ---1---- Cn = max(a1,b1) + max(a2,b2) + ...+ max(an,bn)$ ограничена.

Источники: Курчатов - 2020, 11.6 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Попробуем строить последовательности а и b вокруг последовательности С. Пусть каждый k-тый член в ней равен 2 в степени (-k) — такая последовательность, конечно, ограничена. Как теперь собрать такие последовательности а и b, чтобы max(aₙ, bₙ)=cₙ?

Подсказка 2

Вспомним про раскраски! Разобьём натуральный ряд на цветные отрезки, и для каждого цвета одно число (аₙ или bₙ) равно 2^n, а второе число должно быть меньше него. Как бы это реализовать?

Подсказка 3

Для каждого числа "не на своём цвете" будем брать 2 и возводить в самое маленькое число на этом отрезке! То есть, если красный отрезок начинается с числа k, то (не умаляя общности) аₙ равен 2^n, а bₙ равен 2^k (для синих отрезков аналогично с точностью наоборот). Тогда мы действительно можем составить нашу последовательность c, а так же обе последовательности а и b будут неубывающими. Но как сделать так, чтобы и последовательности А и В были неограниченно возрастающими? Хорошо бы было, если бы на каждом красном отрезке сумма обратных значений b не была слишком маленькой...

Подсказка 4

Конечно! Пусть длина каждого отрезка, начинающегося на k, равна 2^k! Тогда сумма обратных на каждом отрезке равна единице, и последовательности будут не ограничены сверху!

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

Рассмотрим последовательность $c = 2k k$ . Ясно, что все суммы

1 1 1 Cn = c1 + c2 + ...+ cn

ограничены. Будем строить исходные последовательности $an$ и $bn$ так, чтобы $max(an,bn)=cn$ . Последовательно разобьём натуральный ряд на отрезки подряд идущих чисел так, что если отрезок начинается с числа $k$ , то его длина равна $ck$ . После этого раскрасим все эти отрезки поочередно в красный и синий цвета.

Теперь зададим последовательность $an$ следующим образом:

- если $n$ - красное число, то положим $an$ равным числу $cn$ ;

- если $n$ - синее число, то положим $an$ равным $ck$ , где $k$ - первое число отрезка, содержащего $n$ .

Последовательность $bn$ зададим аналогично, но инвертируя цвета:

- если $n$ - синее число, то положим $bn$ равным числу $cn$ ;

- если $n$ - красное число, то положим $bn$ равным $ck$ , где $k$ - первое число отрезка, содержащего $n$ .

Заметим, что для каждого синего отрезка сумма обратных значений последовательности $an$ на нём равна $1,$ поэтому последовательность сумм $1a1 + 1a2 + ...+ 1an$ не ограничена сверху. Аналогично, для последовательности $bn$ сумма обратных значений на каждом красном отрезке равна $1,$ поэтому последовательность сумм $b1+ 1b-+ ...+ 1bn- 1 2$ не ограничена сверху.

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

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

Существует ли множество натуральных чисел $A,$ для которого выполнены следующие свойства: всевозможные суммы двух элементов из $A$ уникальны (т.е. не бывает двух различных пар элементов, у которых суммы одинаковы), и при этом среди этих сумм можно найти $2020$ подряд идущих натуральных чисел.

Источники: Турнир Ломоносова - 2020, 11.5 (см. turlom.olimpiada.ru)

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

Подсказка 1

Если вы обратились к подсказкам, то скорее всего вы устали от безрезультатных попыток доказать, что не существует. Дак вот, эта задача — конструктив. Нужно придумать пример)

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Чтобы добиться различности, давайте попробуем некоторые переменные приравнять к степени некоторого числа х от 1 до k-ой. Другие переменные определим как c - x + ..., c - x² + ..., c - x³ + ... и так далее. Что нужно поставить вместо точек, чтобы пример стал рабочим? И не забудьте его работоспособность доказать!

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

Приведём явный пример.

Рассмотрим числа вида

2 2 3 3 a1 = x,b1 =c− x+ 1,a2 =x ,b2 =c− x + 2,a3 = x ,b3 = c− x + 3,...,

k k 2020 2020 ...,ak = x ,bk =c− x + k,...,a2020 = x ,b2020 =c − x + 2020,

где

x= 10,c= 6⋅102020.

Тогда, очевидно, суммы вида

a1 +b1,a2+ b2,...,a2020+ b2020

равны $c+1,c+ 2,...,c+ 2020$ , то есть образуют $2020$ подряд идущих чисел. Осталось доказать, что среди попарных сумм пирведённых чисел нет совпадающих.

Разделим все суммы на три вида: первый вид $an +ak =xn +xk,$ второй вид $an+ bk =c+ xn− xk+ k,$ третий вид $b + b = 2c− xn− xk+ n+ k. n k$

______________________________________________________________________________________________________________________________________________________

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

Предположим, что число второго вида и третьего вида равны между собой. Тогда для некоторых $n,k,l,m$ будет выполнено

an+ bk =c+ xn− xk+ k= bn +bk = 2c− xl− xm +l+ m =bl+ bm.

Перенося в этом равенстве все слагаемые без $c$ влево и оставляя справа только $c(2c− c= c),$ заметим, что $c$ больше, чем сумма модулей всех остальных слагаемых, а значит, равенства быть не может. Аналогично доказывается, что числа первого вида не могут быть равны числам второго и третьего видов.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Пусть есть $n ≥k$ и $m ≥ l$ такие, что пара чисел $(n,k)$ не совпадает с парой $(m,l)$ . Докажем, что не может быть равенства $bn+ bk = bm + bl.$

Действительно, если так, то после подстановки получаем равенство

− xn− xk +n +k =− xm − xl+m + l.

Если $n⁄= m$ , то без ограничения общности можно считать, что $n> m$ , но тогда $xn$ по модулю больше, чем все суммма модулей остальных $7$ слагаемых в равенстве, а значит, равенства быть не может. Если $n= m$ , то после сокращения равных слагаемых остаётся равенство

k l −x + k= −x +l,

причём в этом равенстве $k ⁄=l,$ так как изначальные пары были различны. Но тогда опять же не умаляя общности будет выполнено, что $k >l$ и $− xk$ по модулю будет больше, чем сумма модулей всех остальных членов в уравнении, что невозможно. Следовательно, все суммы третьего вида различны между собой.

Заметим, что при доказательстве того, что попарные суммы различны внутри второго типа нужно отдельно рассмотреть случаи, когда $n =k$ и $m = l,$ они будут образовывать наши подряд идущие числа, а следовательно, все различны. Во всех остальных случаях соображение о том, что какое-то слагаемое по модулю будет больше, чем сумма модулей остальных, по-прежнему работает.

Ответ: Да, существует

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

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

Приведите пример различных натуральных чисел $a< b< c< d$ таких, что $c2 =$ $ab+ ad+ bd.$

Источники: Изумруд - 2020, 11.1 (см. izumrud.urfu.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Смотрим остатки по модулям 3, 4 и 5. Отсюда берем какие-то подходящие b, c и d, получаются несколько наборов, можем выбрать любой.

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

Рассмотрим числа 1, 4, 8, 12. Так как

2 8 = 4+ 12+ 4⋅12,

то этот набор чисел удовлетворяет условию.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

В задаче требуется только пример, попробуем прийти к нему. $a$ — наименьшее из используемых натуральных чисел, пусть $a= 1.$ Добавим к каждой части по единице, тогда уравнение выглядит как

2 c +1= b+ d+ bd+ 1= (b+1)⋅(d+1).

Теперь рассмотрим делимость на $3.$ $c2+1 ≡±1 (mod 3),$ тогда

({b⁄≡ 2 (mod 3) ( , d⁄≡ 2 (mod 3)

иначе правая часть будет делиться на $3.$

Рассмотрим аналогично делимость на $4.$

[ c2+ 1≡ 1 (mod 4) c2+ 1≡ 2 (mod 4)

Тогда

( { b⁄≡ 3 (mod 4) ( d⁄≡ 3 (mod 4)

иначе правая часть будет делиться на $4.$

Получим минимально возможное $b= 4,$ то есть $c2+ 1= 4+ d+ 4d +1= 5⋅(d+ 1)$ и $c2+ 1≡0 (mod 5).$

Тогда $c ≡2 (mod 5)$ или $c ≡3 (mod 5)$ . В первом случае получаем $c= 7$ и $49= 4+d+ 4d,$ $d= 9.$

Во втором случае: $c= 8$ и $64= 4+ d+ 4d,$ $d =12.$

Оба примера подходят, могут быть и другие подходящие под условие наборы.

Ответ:

Например, подходят числа $a= 1b= 4c =8 d= 12. , , ,$

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

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

На доске написаны четыре различных положительных числа. Известно, что это $sinx,cosx,tg x$ и $y ⁄= ctgx,$ но неизвестно, в каком порядке. Всегда ли можно определить, где именно какое число?

Источники: ИТМО - 2020, 11.3 (см. olymp.itmo.ru)

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

Подсказка 1

Как можно было бы доказать, что сделать этого невозможно?

Подсказка 2

Верно! Хотелось бы найти такие x и z, что для них получится одинаковый набор указанных тригонометрических функций и числа y, но в разном порядке. Например, sin(x) = cos(z). Какие различные тригонометрические функции для x и z можно было бы уравнять?

Подсказка 3

Попробуем сделать так, чтобы выполнялись равенства sin(z) = tg(x), cos(x) = tg(z). А каким можно взять y?

Подсказка 4

Верно! Будем строить y = cos(z) = √(1-tg²(x)). Из наших условий получается, что необходимо выполнение равенства cos(x) = tg(x)/√(1-tg²(x)). Что из этого равенства выходит?

Подсказка 5

Точно! Получается, что sin²(x) должен быть 1 - 1/√2 или 1/2. Осталось проверить, что найденные числа подходят!

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

Докажем существование таких чисел $x$ и $z,$ что

∘ ----2-- sinz =tgx,cosz = y = 1− tg x

и, кроме того,

--tgx--- cosx= tgz = ∘1− tg2x

Тогда на доске находятся, во-первых, числа $sin x,cosx$ и $tg x,$ а во-вторых, $sinz,cosz,tgz$ и невозможно определить, где какое число.

Решаем уравнение:

cosx= ∘--tgx2-- 1− tg x

∘ ----2-- 2 1− tg x cos x= sinx.

Возведя уравнение в квадрат и раскрыв тангенс, получаем

(cos2x− sin2x)cos2x =sin2x.

Обозначив $sin2x =t$ получаем

(1− 2t)(1− t)=t

1− 4t+ 2t2 = 0.

Это уравнение имеет подходящий корень $1√- 1 1− 2 ⁄= 2.$ Осталось убедиться, что при таком значении $2 sin x$ все четыре числа различны. Это правда, так как числа из одной пары $sin x,$ $cosx,$ или $sinz,cosz$ совпадают при квадрате синуса равном $1 2;$ совпадение чисел из разных пар означает равенство и вторых числел тоже, откуда тангенс угла равен его синусу или косинусу, что также не выполняется при найденном значении. Кроме того, все эти числа меньше единицы, поэтому котангенса среди них нет.

Можно также просто вычислить эти числа, это $∘√---- ∘---√--∘ ∘----∘---∘---- 2− 1, 2 − 2, 1∕2, 1− 1∕2.$

Замечание. Более простые варианты, при которых мы не можем однозначно распределить числа, не подходят из-за запрета равенства чисел или запрета наличия котангенса. В силу симметрии у задачи есть второе решение, в котором $x$ и $z$ меняются местами.

Ответ: Нет

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

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

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

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

На доске написана система из $12$ различных уравнений с $6$ неизвестными $x ,x ,x,x ,x,x . 1 2 3 4 5 6$ Каждое уравнение имеет вид $xi+ xj +xk =0,$ где $i⁄= j ⁄= k$ (сумма трех различных неизвестных равна нулю). Могло ли оказаться так, что у системы бесконечно много решений?

Источники: Высшая проба - 2020, 11.1(см. olymp.hse.ru)

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

Подсказка 1

Эх, вот бы сразу знать ответ, чтобы не пришлось идти не в ту сторону.. Если такого быть не могло, то должно быть красивое доказательство (хотя бы какое-то!), если может, то нужен один пример. С чего легче начать?

Подсказка 2

Давайте попробуем с примера. Если решений бесконечно много, то у них есть какой-то общий вид, причем чем меньше будет различных значений у переменных, тем больше равенств нулю мы сможем составить (если все 6 неизвестных разные, то составить 12 уравнений будет сложнее, чем если у нас будут всего 1-3 различных значений на 6 переменных).

Подсказка 3

Очевидно, что все переменные не могут быть равны между собой (ведь тогда единственным решением будет (0,0,0,0,0,0), а не бесконечное количество, противоречие). Сможем ли составить пример с двумя различными значениями? Получится ли записать такое решение в общем виде?

Подсказка 4

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

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

Да, могло. Приведем пример. Пусть $t$ — произвольное действительное число, положим, чтобы выполнялись равенства:

x1 = x2 = 2t

x = x = x =x =− t 3 4 5 6

Тогда при сложении одного слагаемого, равного $2t,$ и двух слагаемых, равных $− t,$ сумма будет равна нулю. Количество таких сумм составляет:

C1 ⋅C2= 2⋅6= 12 2 4

Выпишем данную систему явно:

(||x + x + x =0 ||||| 1 3 4 |||||x2+ x3+ x4 =0 |||||x1+ x3+ x5 =0 |||||x2+ x3+ x5 =0 |||||x1+ x3+ x6 =0 ||||{ x2+ x3+ x6 =0 |||||x1+ x4+ x5 =0 |||||x2+ x4+ x5 =0 |||||x1+ x4+ x6 =0 ||||| |||||x2+ x4+ x6 =0 |||||x1+ x5+ x6 =0 |(x2+ x5+ x6 =0

Ответ:

Могло

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

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

Дано несколько вещественных чисел, по модулю не превосходящих $1.$ Сумма всех чисел равна $S.$ Докажите, что из них можно выбрать несколько чисел так, чтобы при некотором натуральном $n <100$ сумма выбранных чисел отличалась от $nS- 100$ не более чем на $-1- 100.$

Источники: Высшая проба - 2020, 11.5(см. olymp.hse.ru)

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

Подсказка 1

Обозначим данные k чисел за x₁, x₂, ... , x_k. Давайте, например, поймем, что нам дает условие на модуль.

Подсказка 2

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

Подсказка 3

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

Подсказка 5

У нас n - натуральное, давайте рассмотрим наименьшие индексы m_1, m_2, ... , m_99, такие, что x₁ + x₂ + ... + xₘ_₁ ≥ S/100, x₁ + x₂ + ... + xₘ_₂ ≥ 2*S/100 и так далее. Как они могут нам помочь в оценке? Может, нам чего-то еще не хватает? Вспомните, что мы хотим доказать.

Подсказка 6

Доопределим разность суммы каждой последовательности и соответствующей ей оценки: aᵢ = x₁ + x₂ + ... + xᵢ - i*S/100. Кстати, все ли они определены? А можем ли мы как-то оценить величину каждой aᵢ?

Подсказка 7

mᵢ и aᵢ определены, так как по крайней мере для k при любом i выполняется x₁ + x₂ + ... + x_k = S ≥ i*S/100. Давайте формально доопределим m₀ = 0 и a₀ = 0. Выбранные нами индексы были первыми для своего условия, а также все xᵢ по модулю не превосходят 1, следовательно, значения aᵢ лежат в отрезке [0;1]. А можем ли мы сжать этот отрезок для удобства и попробовать оценить разницу между какими-нибудь aᵢ и aⱼ, где i ≠ j? Какое неравенство мы хотим получить по условию задачи?

Подсказка 8

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

Подсказка 9

Несколько ранее мы предположили, что отрезок величин aᵢ можно сжать для получения искомой оценки, а если для некоторого i a_i попадает в отрезанный кусок? Какое множество чисел может быть искомым?

Подсказка 10

Подумайте, как доказать, что в таком случае набор чисел x₁, x₂, ... , x_(m_i-1) нам подойдет.

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

Обозначим данные $k$ чисел через $x,x ,...,x . 1 2 k$ Без ограничения общности будем считать, что $S ≥ 0.$ Если это не так, то будем доказывать утверждение задачи для чисел $yi = −xi$ с положительной суммой. Из него будет следовать утверждение исходной задачи.

Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные $s$ и $t$ $(1≤ s≤ t≤k),$ что подмножество $xs,xs+1,...,xt$ — искомое.

Обозначим через $m1$ первый индекс, для которого

S x1+x2+ ...+ xm1 ≥ 100,

через $m2$ — первый индекс, для которого

x1+x2+ ...+ xm2 ≥-2S-, 100

и так далее:

x1+ x2+...+xmi ≥-iS- 100

по всем $i$ от $1$ до $99.$ Рассмотрим также разности

a = x +x +...+ x − -iS- i 1 2 mi 100

Заметим, что $m i$ и $a i$ определены, поскольку по крайней мере для $k$ выполняется неравенство

x1+ x2 +...+ xk = S ≥-iS- 100

для любого $i.$ Формально доопределим: $m0 = 0$ и $a0 = 0.$ Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа $xi$ по модулю не превосходят $1,$ то все $ai$ лежат на отрезке $[0;1].$

Предположим, все $ai$ лежат на отрезке $[0;1− 1100].$ Тогда, так как чисел $ai$ всего $100$ (для $i$ от $0$ до $99),$ найдутся два индекса $i$ и $j,$ для которых $|ai− aj|≤ -1. 100$ Без ограничения общности $j >i.$ Тогда $mj ≥ mi$ по определению чисел $mi.$ Получаем:

| | ||(x + x + ...+ x )− (x +x + ...+ x )+ jS-− iS||≤ -1- | 1 2 mi 1 2 mj 100 100| 100

или, что то же самое,

|| (j− i)S|| 1 ||xmi +xmi+1+ ...+ xmj −--100--||≤ 100.

Заметим, что можно взять $n =j− i,$ поскольку $j− i> 0$ и $j− i≤ j <100.$ Тем самым, числа $xmi,xmi+1,...,xmj$ — искомые.

Пусть теперь для некоторого $i$ разность $ai$ попала на полуинтервал $(1 −1100,1].$ Докажем, что в этом случае подмножество $x1,...,xmi−1$ — искомое. Для этого достаточно показать, что

iS-− -1-< x1 +...+xmi−1 ≤-iS-. 100 100 100

Второе неравенство следует из определения $mi;$ ведь $mi$ — это первый индекс, для которого сумма стала не меньше $-iS-. 100$ Первое неравенство равносильно следующему: $x1+...+xmi−1− iS-> −-1. 100 100$ Но

x1+...+xmi−1− -iS-= ai− xmi 100

и это больше $− 1100,$ так как $ai > 1− 1100$ и $xmi ≤ 1.$

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

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

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

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

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

Обозначим первые пять чисел через $a,b,c,d$ и $e.$ Рассмотрим их частичные суммы $a,a+ b,a+ b+ c,a+ b+ c+d$ и $a+ b+ c+d +e.$ Среди них либо есть $0,$ либо есть две одинаковые по модулю $5.$ Тогда разница между двумя суммами с одинаковыми остатками по модулю $5$ — тоже сумма нескольких подряд идущих из этих $5$ чисел, и она кратна $5.$ Итак, среди этих $5$ чисел можно выделить несколько подряд идущих, сумма которых делится на $5.$ Поставим между этими числами знаки “ $+$ ” и скобочки вокруг этой суммы, на остальные числа из пятерки просто умножим.

Проведя те же действия для еще двух пятерок, получим произведение $15$ чисел, делящееся на $3 5 .$ Остальные $8$ чисел разобьем на пары подряд идущих, если оба числа в паре нечетны, то сложим их, поставим вокруг них скобки и знак умножения перед скобками. Если же хотя бы одно число четно, то перед обоими числами поставим знак умножения. В итоге каждая пара добавит в произведение хотя бы одну двойку, и за четыре пары мы получим четыре двойки. Таким образом, мы получим делимость на $53⋅24 = 2000.$

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

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

На доске выписаны в ряд $n$ положительных чисел $a ,a,...,a . 1 2 n$ Вася хочет выписать под каждым числом $a i$ число $b > a i i$ так, чтобы для любых двух из чисел $b1,b2,...,bn$ отношение одного из них к другому было целым. Докажите, что Вася может выписать требуемые числа так, чтобы выполнялось неравенство $(n−1)∕2 b1b2...bn ≤2 a1a2...an.$

Источники: Всеросс., 2017, ЗЭ, 10.4(см. olympiads.mccme.ru)

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

Мы докажем, что существуют даже числа $b ,b,...,b, 1 2 n$ удовлетворяющие следующим (более сильным) условиям:

(1) $bi ≥ ai$ при всех $i≤ n;$

(2) $(n−1)∕2 b1b2...bn ≤2 a1a2...an;$

(3) отношение любых двух из чисел $bi$ является степенью двойки (с целым показателем).

Заметим, что доказываемое утверждение не изменится, если какое-то из чисел $ak$ (а с ним и соответствующее $bk$ ) умножить на некоторую степень двойки. Умножим каждое из чисел $ak$ на степень двойки так, чтобы все полученные числа лежали в промежутке $[1,2).$

Не умаляя общности можно считать, что $1≤ a1 ≤ a2 ≤$ $≤ ...≤ an < 2.$ Покажем теперь, что одна из следующих $n$ последовательностей удовлетворяет всем трём условиям:

a1, 2a1,2a1,2a1,...,2a1,2a1; a2, a2, 2a2, 2a2, ...,2a2, 2a2; a3, a3, a3, 2a3,...,2a3, 2a3; an−1,an−1,an−1,an−1,...,an− 1,2an−1; an, an, an, an,...,an, an.

Поскольку для любых $k$ и $ℓ$ выполнено неравенство $2aℓ ≥ 2> ak,$ каждая из последовательностей удовлетворяет $(1).$ Кроме того, каждая из последовательностей, очевидно, удовлетворяет $(3).$ Осталось показать, что хотя бы одна из них удовлетворяет $(2).$ Для этого заметим, что произведение всех $n2$ чисел во всех $n$ последовательностях равно