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

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

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

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

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

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

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

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

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

Задача 1#85495

У математика есть 19 различных гирь, массы которых в килограммах равны $ln2,ln3,ln 4,...,ln 20$ , и абсолютно точные двухчашечные весы. Он положил несколько гирь на весы так, что установилось равновесие. Какое наибольшее число гирь могло оказаться на весах?

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

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

Подсказка 1

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

Подсказка 2

Мы знаем, что сумма логарифмов равна логарифму произведения: ln(a) + ln(b) = ln(ab). То есть можно сравнивать не суммы логарифмов, а произведения их аргументов.

Подсказка 3

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

Подсказка 4

Большие простые числа (а именно те, которые больше 10) не могут быть в произведении.

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

Сумма логарифмов положительных чисел равна логарифму их произведения, поэтому будем уравнивать произведения двух непересекающихся наборов чисел из множества ${2,3,...,20}$ . Разложим натуральные числа от $2$ до $20$ на простые множители:

| | 3 | | | 2= 2 | 8 =22 | 14= 2⋅7 | | 3= 32 | 9 =3 | 15= 3⋅54 | | 4= 2 |10= 2⋅5 | 16= 2 | | 5= 5 | 11= 121 | 17= 172 | |6= 2⋅3 |12= 2 ⋅3 | 18= 2⋅3 2 | | 7= 7 | 13= 13 |19= 19,20= 2 ⋅5 |

Числа $11,13,17,19$ встречаются ровно по одному разу среди делителей, поэтому их следует исключить. Таким образом, на весах будет не более $15$ гирь.

Покажем, что можно уравновесить $15$ гирь. Приведем один из возможных примеров равенства произведений:

2⋅4⋅6⋅7⋅8⋅10⋅15⋅18 =

= 29⋅34⋅52⋅7= 3⋅5⋅9⋅12⋅14⋅16 ⋅20

Ответ: 15

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

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

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

Задача 2#85513

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

Источники: Турнир городов - 2024, весенний тур, 11.4 (см. turgor.ru)

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

Подсказка 1

Не совсем понятно, как работать с огромным количеством начАл лучей…а что если найти особенную точку и отталкиваться от нее? Как Вы думаете, на что будет похож наш рисунок, когда мы проведем все лучи?

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Можно указать точку $O$ явно - например, подойдёт точка $√ -√- ( 2, 3)$ . Пусть на прямой, проходящей через эту точку, есть две рациональные точки $(a,b)$ и ( $c,d$ ) (где $a,b,c,d$ рациональные). Тогда вектора ( $√- √- a− 2,b− 3)$ и $(a− c,b− d)$ пропорциональны, откуда

√- √- (a− 2)(b− d)=(b− 3)(a− c),

откуда $√ - √- a(b− d)− b(a− c)=(b− d) 2− (a− c) 3$ . Возводя в квадрат и перенося заведомо рациональные слагаемые в левую часть, получим, что будет рациональным число $√- 2(b− d)(a− c) 6$ , что возможно только при $b= d$ или $a= c$ . Но из равенства (*) видим, что если выполнено хоть одно из равенств $b= d,a =c$ , то выполнено и второе, откуда точки $(a,b)$ и $(c,d)$ совпадают.

_________________________________________________________________________________________________________________________________________________________________________________

Можно поступить иначе - доказать существование такой точки $O$ . Проведём всевозможные прямые через пары рациональных точек. Таких прямых будет счётное количество. Так как всего направлений на плоскости несчётное количество, на ней найдётся прямая $l$ , не параллельная ни одной из проведённых прямых. Проведённые прямые высекают на $l$ счётное число точек, а всего на $l$ точек несчётное количество, поэтому там ещё останутся точки, любая из них подойдёт в качестве $O$ .

Ответ: да

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

Задача 3#94421

Действительные числа $x,y$ и $z$ таковы, что

x(y-− z) y(z− x) z(x−-y) y+ z + z+ x + x +y = 0

Верно ли, что тогда какие-то два из них равны?

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

Вы спрашиваете, как это сделать? Замените y и z на какие-нибудь выражения от х и получите уравнение. Если найдëте х, подходящий по одз и при котором x, y, z различны, то победа.

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

Попробуем подобрать пример, когда все попарно различны. Для упрощения давайте предположим, что $y$ и $z$ равны каким-то функциям от $x.$ Например, $y =2x,z = x+ 1$ . Переменные не должны быть равны, а значит $x⁄= 0,1.$ Подставим в равенство:

x(x− 1) 2x (x+ 1)x 3x+-1-+ 2x+-1 =--3x--.

Это уравнение имеет корень $x =− 14$ (мы сразу исключили $x = 1).$ Он не противоречит ОДЗ и не равен $1,0.$ Значит, мы нашли пример.

Ответ:

Нет

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

Задача 4#94422

Докажите, что существует бесконечно много натуральных $N$ таких, что каждое из чисел $N − 2,N$ и $N +6$ представимо в виде суммы квадратов двух целых чисел.

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

Подсказка 1

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

Подсказка 2:

Попробуйте придумать пример, опираясь на квадратные трëхчлены. Например, рассмотрите трехчлен (x+2)²+(x+4)². Какие есть трëхчлены, несильно отличающиеся от него и представимые в виде суммы квадратов?

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

Например, можно взять $N =2x2+ 12x +20,x∈ ℕ.$ Тогда

2 2 N = (x+ 2) +(x+ 4)

2 2 N − 2= (x+3) + (x +3)

N + 6= (x+1)2+ (x +5)2

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

Задача 5#94425

Верно ли, что любой многочлен с действительными коэффициентами можно представить в виде суммы кубов трёх многочленов с действительными коэффициентами?

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

Подсказка 1:

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

Подсказка 2:

Но как это сделать для произвольного? Попробуйте сделать для какого-то конкретного, например, для x. А там станет понятно, как обобщить до произвольного.

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

Заметим, что $(x +1)3+2(−x)3+(x− 1)3 =6x.$ Если вместо $x$ подставить многочлен $P(x),$ поделить на $6,$ и внести константы в кубы, то получим равенство:

(P(x)+ 1)3 ( P(x))3 (P(x)− 1)3 --√36--- + −-3√3- + --√36--- = P(x)

Ответ:

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

Задача 6#97185

Докажите, что для любого многочлена $P$ с целыми коэффициентами и любого натурального $k$ существует такое натуральное $n,$ что $P (1)+ P(2)+ ...+ P(n)$ делится на $k.$

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

Подсказка

Всë, что вам нужно, это вспомнить известный факт: P(x) ≡ P(x + tk) (mod k). С его помощью нужно придумать пример.

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

Заметим, что $P(r)$ и $P(kt+r)$ имеют одинаковые остатки при делении на $k.$ Следовательно, в сумме $P (1)+ P(2)+ ...+ P(k2)$ для каждого $r= 0,1,...,k− 1$ будет $k$ слагаемых вида $P(kt+r),$ дающих одинаковые остатки при делении на $k.$ Сумма этих $k$ слагаемых делится на $k;$ сумма всех $2 k$ слагаемых разбивается на $k$ таких сумм, а потому тоже делится на $k.$

Курсы

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

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

Задача 7#67559

Назовём рассадку $N$ кузнечиков на прямой в различные её точки $k$ -удачной, если кузнечики, сделав необходимое число ходов по правилам чехарды, могут добиться того, что сумма попарных расстояний между ними уменьшится хотя бы в $k$ раз. При каких $N ≥ 2$ существует рассадка, являющаяся $k$ -удачной сразу для всех натуральных $k$ ? (В чехарде за ход один из кузнечиков прыгает в точку, симметричную ему относительно другого кузнечика.)

Источники: Тургор-2023, 11.5 (см. www.turgor.ru)

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

Подсказка 1

Случай N=2 рассмотрите отдельно, он очевиден. Для всех N>2 попробуйте придумать пример такой рассадки.

Подсказка 2

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

Подсказка 3

На геометрическую прогрессию! Она и поможет нам придумать такую рассадку. Только вот рассадка 1, q, q^2, ... не очень то работает. Как можно подкорректировать координаты кузнечиков?

Подсказка 4

Давайте посадим кузнечиков в точки с координатами 0, 1, 1+q, 1+q+q^2, ... Какой тогда можно сделать первый ход, чтобы картинка стала подобна предыдущей (возможно, со сдвигом и с подбором нужного q)?

Подсказка 5

Нужно чтобы первый кузнечик перепрыгнул через второго и оказался на последнем месте! Отсюда мы получаем условие на q. И остаётся только одно: доказать, что найдётся q, удовлетворяющее этому условию, и притом оно будет из (0; 1).

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

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

Для любого $N > 2$ предъявим явно начальную рассадку, которая является $k$ -удачной для любого натурального числа $k.$

Сначала для данного $N > 2$ построим конечную геометрическую прогрессию $N−1 1,q,...,q ,$ со знаменателем $q ∈ (0,1),$ для которой выполнено условие

1= q+ q2 +⋅⋅⋅+ qN−1

Требуемый набор существует при любом целом $N > 2,$ поскольку уравнение

2 N−1 q+q + ⋅⋅⋅+ q − 1= 0

имеет решение на интервале $(0,1),$ так как левая часть меняет знак на его концах.

Расположим теперь $N$ кузнечиков в следующих начальных точках:

0,1,(1+ q),(1 +q+ q2),...,(1 +q+ ⋅⋅⋅+ qN−3),(1+ q+⋅⋅⋅+qN−2)

Рассмотрим прыжок первого кузнечика через второго; тогда его новая координата будет равна $2 =1 +1 =1+ q+ q2+⋅⋅⋅+qN−1.$ Получилось, что прыгнувший кузнечик стал самым правым, а все кузнечики теперь расположены в точках

1,(1+ q),(1+ q+q2),...,(1+q +⋅⋅⋅+ qN−2),(1+ q+ ⋅⋅⋅+qN− 1)

Сдвинув начало координат на 1 вправо, получим координаты кузнечиков

0,q,(q+ q2),...,(q+ ⋅⋅⋅+ qN −2),(q+⋅⋅⋅+qN−1)

Таким образом, кузнечики уменьшили свои координаты ровно в $1 q$ раз. Если указанный шаг (прыжок самого левого кузнечика через ближайшего соседа) повторять $r$ раз, то попарные расстояния уменьшатся в $-1 qr$ раз, что позволит достичь любого нужного уменьшения $-1. K$

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

При $N = 2$ как бы кузнечики ни прыгали, расстояние между ними не меняется.

Пусть $N ≥ 3.$ Рассадим 1-го, 2-го и 3-го кузнечиков на прямой в точках с координатами 0, 1, $√2,$ назовём этих кузнечиков $V,$ $Q,$ $R.$ Остальные произвольно рассаживаются в другие попарно различные точки. Покажем, что для всякого $k$ кузнечики далее смогут прыгать так, чтобы сумма попарных расстояний уменьшилась хотя бы в $k$ раз (исходную сумму обозначим через $P ).$

Лемма.

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

Доказательство леммы.

Покажем, что эти условия сохраняются при прыжке. Предположим, для некоторого кузнечика отношение расстояний до двух других рационально, тогда эти расстояния имеют вид $a$ и $aq,$ где $q$ рационально. Тогда расстояние между другими двумя кузнечиками ненулевое и имеет вид $|a± aq|,$ тогда отношение любых двух расстояний между кузнечиками рационально, противоречие. Пусть какой-то кузнечик перепрыгнул через кузнечика $A,$ тогда расстояния от $A$ до обоих кузнечиков не изменились, а значит, отношение этих расстояний осталось иррациональным, в частности расстояния различны, и потому кузнечики по-прежнему находятся в попарно различных точках.

Вернёмся к задаче.

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

Пусть, не умаляя общности, в текущий момент минимально расстояние между кузнечиками $V,$ $Q$ с координатами $a$ и $b,$ а $R$ имеет координату $c$ . Отметим на прямой все точки с координатами, отличающимися от $a$ на число, кратное $(a − b).$ Понятно, что прыгая друг через друга кузнечики $V,$ $Q$ смогут занять любые две соседние отмеченные точки, тогда $R$ не находится в отмеченной точке (по лемме прыгая только через друг друга $V,$ $Q,$ $R$ остаются в попарно различных точках), тогда $V$ , $Q$ могут занять две соседние отмеченные точки между которыми лежит $c,$ и расстояние от $R$ до одного из кузнечиков будет не более $12|a− b|,$ то есть наименьшее расстояние уменьшилось хотя бы в 2 раза.

Тогда за несколько ходов кузнечики $V,$ $Q,$ $R$ могут уменьшить наименьшее расстояние между ними хотя бы в 2 раза, потом за несколько ходов ещё хотя бы в 2 раза, потом ещё, и т.д, могут за несколько ходов добиться того, чтобы расстояние между какими-то двумя из них было равно некоторому числу $t$ , меньшему $----P----- 2N (N − 1)⋅k$ — пусть они так и сделают. Назовём каких-нибудь двух кузнечиков, между которыми расстояние $t,$ хорошими, и одного из них назовём $D,$ далее эти кузнечики уже не прыгают.

Далее, любой кузнечик не из пары хороших может прыгая через пару хороших (в подходящем порядке) смещаться на $2t$ в любую сторону на прямой, и тогда может за несколько прыжков через них оказаться на расстоянии меньшем $2t$ от $D,$ пусть все кузнечики кроме хороших сделают прыжки таким образом. Тогда расстояние от любого кузнечика до $D$ будет меньше $2t,$ а значит, все попарные расстояния меньше $4t,$ а значит, их сумма меньше $4t⋅N-(N-−-1)- P- 2 < k.$

Ответ:

при $N ≥ 3$

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

Задача 8#67560

В ряд слева направо стоят $N$ коробок, занумерованных подряд числами $1,2,...,N$ . В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № $i$ и № $j$ », где $i$ и $j$ — числа. Для каждого ли $N$ существует инструкция, в которой не больше $100N$ команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?

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

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

Подсказка 1

Сразу вот такое наблюдение: у нас всего N коробок, а длина инструкции может быть 100N...Да и еще шарики в коробках лежат не наугад, а подряд, т.е. еще меньше вариаций для расположения шаров в коробках... На какой ответ в задаче это намекает?

Подсказка 2

Как будто всегда можно придумать такую инструкцию) А если мы доказываем что-то, что должно работать для любого натурального числа, то давайте доказывать это по индукции! А именно, будем доказывать, что для любого N существует нужная инструкция длины меньше чем 100N. Как можно это сделать?

Подсказка 3

База понятное дело проверяется, а вот что делать с переходом...Нам в нем, очевидно, нужно пользоваться меньшим числом K, для которого условие верно. Значит, нам нужно свести ситуацию для N к меньшей ситуации. То есть, по факту нужно перенести все шарики в меньший промежуток, где они также стоят подряд. Как это можно сделать и какой промежуток брать для этого?

Подсказка 4

Давайте мы будем переносить все в левую половину (если N = 2k, то в первые k коробок, если N = 2k+1, то в первые k+1 коробок). И самая важная идея: представьте, что в коробках, в которых есть шарики - синие шарики, а в которых нет мы положили красные шарики. То есть, нам нужно синие шары положить левее красных, но при таком условии мы можем сделать наоборот, и с помощью дополнительных инструкций поменять нам на нужную ситуацию)

Подсказка 5

Если сейчас в лоб не получается придумать как перетащить все шарики синие шарики в левую половинку, то вот что поймите: мы же можем перетащить любые шарики влево а оставшиеся будут справа, а после сделать ситуацию наоборот. Поэтому перетаскивайте те шары, которых меньше (и кстати, их будет <не больше k как раз).

Подсказка 6

Раз наших шаров не больше k, то значит в i-ой и k+i-ой коробкой не больше одного нужного шарика....Попробуйте применить это и раскрутить дальше, возможно добавив какие-то инструкции)

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

Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику. Теперь пустых коробок нет. Покажем даже более сильное утверждение: что для любого $N$ есть инструкция не длиннее чем $3N$ со следующим свойством.

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

Воспользуемся методом математической индукции. Понятно, что для $N = 1$ такая инструкция есть. Это база индукции. Теперь покажем, как из инструкции для $k ≥1$ сделать инструкцию для $2k$ и для $2k− 1,$ этого будет достаточно. Обозначим $N = 2k$ или $2k− 1.$ Инструкция для $N$ будет выглядеть так:

I группа: сначала все пары вида $(i,k+ i)$ в любом порядке

Если $N$ нечетно, сюда приходится добавить все пары вида $(i+1,i+k)$ при $i≥1$ (назовём эти команды дополнительными).

II группа: инструкция для $k$ первых коробочек из индукционного предположения

III группа: все пары различных чисел вида $(i,N + 1− i)$ в любом порядке

При $N = 2k$ длина этой инструкции не превышает $k+ 3k +k =5k ≤3N.$

При $N = 2k− 1$ длина этой инструкции не превышает $2(k− 1)+3k+ (k − 1)=$ $= 6k− 3= 3N.$ Теперь почему она работает. Есть тот цвет, которого не больше $k$ , назовём его основным. Покажем, что можно выполнить часть инструкций I группы так, чтобы все шарики основного цвета лежали среди первых $k$ коробочек, и при этом конфигурация среди первых $k$ коробочек будет тоже непрерывной.

Есть четыре варианта того, как могут располагаться шарики основного цвета.

1) Они идут подряд, и все они среди левых $k$ коробок — ничего делать не надо;

2) Они идут подряд, и все они среди правых коробок — используем все пары вида $(i,k+ i)$ ;

3) Они есть и среди левых $k$ коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида $(i,i+ k)$ нет двух шариков основного цвета. Все основные шарики тогда перенесем справа налево (тогда шарики не основного цвета будут среди первых $k$ шариков лежать подряд.

4) Шарики основного цвета — самые первые и самые последние. Перенеся последние влево (при нечётном $N$ используя дополнительные операции), получаем требуемое.

(Про это всё проще думать, если мыслить расположение коробочек не в ряд, а по окружности.)

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

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

Ответ: да

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

Задача 9#67679

Имеются абсолютно точные двухчашечные весы и набор из $50$ гирь, веса которых равны $arctg1,arctg 1,arctg 1,...,arctg-1. 2 3 50$ Докажите, что можно выбрать 10 из них и разложить по 5 гирь на разные чаши весов так, чтобы установилось равновесие.

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

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

Подсказка 1

Не совсем ясно, как удобнее подобраться к равновесию. Быть может, найти какие-то мини-группы среди гирек, которые уже удобно делить на равные по весу части? Группы на сколько гирек попробуем найти? Раз уж у нас арктангенсы то было бы неплохо как-то от них избавиться, иначе совсем неясно, как с ними работать... С помощью чего это сделаем?

Подсказка 2

Попробуем искать группы по 3, в которых одна гирька уравновешивает две остальные, а от арктангенса избавимся, взяв тангенс от обеих частей равенства, записанного на тройку из гирек arctg(1/n), arctg(1/m) , arctg(1/k) (первые две уравновешивают третью). Что получится после преобразований и как решать получившееся равенство на n, m и k?

Подсказка 3

С помощью преобразований придём к mn - k(n+m) = 1. Выходит, если мы найдем такие k, n, m в промежутке целых чисел от 1 до 50, то задача решена! Как будем это делать?

Подсказка 4

Попробуйте разложить на множители, а далее перебирать k и для него искать m и n (возможно, перебором)

Подсказка 5

Добавьте к обеим частям равенства k², а далее проделайте действия из подсказки 4

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

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

( 1 1 ) ( 1) 1 1 1 tg arctg n + arctgm = tg arctgk и arctgn + arctgm-= arctgk

равносильны. Воспользовавшись формулой

tg(x +y)= -tgx+-tg-y- 1− tgx⋅tg y

получаем, что

n+-m--= 1⇐⇒ nm − k(n +m )= 1⇐⇒ k2− k(n +m )+nm = k2+ 1 nm− 1 k

Тогда $(n− k)(m − k) =k2+ 1.$ Выбирая теперь различные натуральные $k$ и раскладывая $k2+1$ на множители, находим подходящие тройки, в которых каждое число не превосходит $50.$ Результат для $k≤ 5$ и $n < m$ представлен в следующей таблице:

$k$	$1$	$2$	$3$	$4$	$5$

$(n,m )$	$(2,3)$	$(3,7)$	$(4,13)$	$(5,21)$	$(6,31)$
			$(5,8)$		$(7,18)$

Теперь покажем, как разложить гири по чашам:

1-я чаша		2-я чаша

$1$	=	$2,3$
$5,21$	=	$4$
$6,31$	=	$7,18$

(в таблице указано значение $n$ для гири весом $arctg 1n).$ Таким образом нам удалось выбрать 10 гирь и разложить по 5 гирь на разные чаши весов так, чтобы установились равновесие.

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

Задача 10#68534

В выпуклом $100$ -угольнике $41$ вершина покрашена в чёрный цвет, и $59$ вершин покрашены в красный цвет. Докажите, что существуют $24$ четырехугольника $P1,P2,...P24$ с вершинами в вершинах $100$ -угольника такие, что

Четырехугольники $Pi$ и $Pj$ не имеют общих точек при любых $i⁄= j$ ;
Каждый выбранный четырехугольник имел $3$ вершины одного цвета (чёрного или красного) и одну другого.

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

Сразу забудем про одну произвольную чёрную вершину $100$ -угольника. Заметим, что среди оставшихся вершин найдутся $4$ подряд идущие, среди которых красных точек больше, чем чёрных. Будем сдвигать эту четвёрку на один по часовой стрелке пока не придём в четвёрку, в которой ровно $3$ вершины красного цвета и одна — чёрного (такое случится, так как мы рано или поздно первый раз встретим чёрную вершину). Возьмём соответствующий четырёхугольник и выкинем его. На оставшихся вершинах повторим операцию. Так будем продолжать, пока не останется $29$ красных вершин и $30$ чёрных. Затем будем по очереди проводить рассуждения для чёрного цвета, затем снова для красного и так далее. В конце останется $1$ красная вершина и две чёрные. Значит, мы нашли $96∕4= 24$ не пересекающихся четырёхугольника.

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

Задача 11#77201

Ромашки распускаются по утрам. У распустившейся ромашки 12 лепестков. Каждый вечер от неё отлетает один лепесток, пока не отлетят все. Днём 1-го мая на лужайке росло 20 ромашек с лепестками (хотя бы одним), у них на всех было 219 лепестков. Днём 4-го мая лепестков в сумме на всех ромашках стало 198. Сколько новых ромашек за это время распустились?

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

Заметим, что ко дню $4$ мая ромашки, которые распустились с $1$ по $4$ мая, могут добавить к имеющимся лепесткам либо $10,$ либо $11,$ либо $12$ лепестков.

Посчитаем максимальное количество лепестков у $20$ ромашек: $20⋅12 =240$ лепестков. Посчитаем максимальное и минимальное количество лепестков, которое может остаться на изначальных ромашках $4$ мая.

Чтобы найти минимальное количество лепестков, нужно чтобы у каждой ромашки отлетало по $1$ лепестку, что означает, что у изначальных ромашек хотя бы $3$ лепестка изначально.Следовательно, каждый день отлетает по $20$ лепестков. Тогда минимальное количество лепестков будет равно: $219 − 20− 20− 20= 159.$ Тогда можно оценить, сколько максимум ромашек распустилось: $159+ 4⋅10 >198.$ ( $10$ потому, что нужно как можно больше новых ромашек). Следовательно, что новых ромашек меньше $4.$

Чтобы найти максимальное количество лепестков, нужно найти максимальное количество ромашек, у которых не более $2$ лепестков. Т.к. максимальное количество лепестков равно $240,$ а каждая такая ромашка уменьшает количество лепестков как минимум на $10,$ то таких ромашек не более $2,$ т.к. изначальное количество лепестков равно $219.$ Следовательно, максимальное количество лепестков равно: $219− 20 − 18− 18= 163.$ Тогда можно оценить, сколько минимум ромашек распустилось: $163+ 2⋅12 <198.$ ( $12$ потому, что нужно как можно меньше новых ромашек). Следовательно, что новых ромашек больше $2.$

Тогда единственное число, которое больше $2$ и меньше $4$ , это $3.$

Пример: первая ромашка с $1$ лепестком, вторая - с $2$ лепестками, остальные - с $12$ лепестками.

Ответ: 3

Интенсивы

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

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

Задача 12#70162

В пяти корзинах лежат яблоки двух сортов так, что в каждой корзине есть яблоки только одного сорта. Известно, что в первой корзине находится 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

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

Задача 13#76637

Можно ли множество из $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.$

Ответ: да

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

Задача 14#82262

На прямой отмечено $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$

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

Задача 15#92428

Существует ли описанный 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-угольник в удовлетворяющий условию задачи.

Ответ: да

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

Задача 16#94424

Существует ли такое натуральное $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.$

Ответ:

Существует

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

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

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

Задача 17#94761

Территория Тридесятого царства состоит из всех целых чисел. Княжеством будем называть множество вида ${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$ . Для чётных аналогично.

Ответ: да

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

Задача 18#94952

Дан клетчатый прямоугольник $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)

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

Утверждение. Функция высоты $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$ . Применяя предположение индукции, получаем требуемое.

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

Задача 19#99165

Заданы квадраты со сторонами $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

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

Ответ:

Да

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

Задача 20#99591

Устройство принимает на вход и выдает на выход наборы из $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.2 (см. v-olymp.ru)

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

Заметим, что для всех $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.

Предыдущий раздел

Следующий раздел