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

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

Применение классических комбинаторных методов к разным задачам → .07 Инвариант

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

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

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

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

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

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

Анализ с конца

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

Двойной подсчёт

Жадные алгоритмы

Принцип крайнего

Чётность

Инвариант

Полуинвариант

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

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

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

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

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

Задача 1#119520

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

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

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

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

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

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

Задача 2#121755

Саша и Гоша поставили $2025$ фишек в клетки доски $1000× 1000$ и по очереди ходят. Саша своим ходом может взять две фишки, стоящие в левом верхнем и правом нижнем углу некоторого клетчатого прямоугольника (со сторонами больше $1),$ и поместить их по одной в две другие угловые клетки того же прямоугольника. Гоша своим ходом может передвинуть любую фишку либо вправо вниз, либо влево вверх по диагонали на любое число клеток. Они заканчивают ходить, когда кто-то не может сделать ход. Могут ли они ходить бесконечно?

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

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

Подсказка 1

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

Подсказка 2

Рассмотрите диагонали, параллельные побочной.

Подсказка 3

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

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

Запишем в клетки доски $n ×n$ положительные целые числа $a ,a ,...,a 1 2 2n−1$ так: число $a i$ записано в каждой клетке $i−$ й диагонали, параллельной главной диагонали, идущей слева сверху вправо вниз (ниже приведен пример для доски $5× 5).$

|---|---|--|---|---| |a5-|a4-|a3|a2-|a1-| |a6-|a5-|a4|a3-|a2-| |a7-|a6-|a5|a4-|a3-| |a8-|a7-|a6|a5-|a4-| -a9--a8--a7-a6--a5-|

Сопоставим каждой конфигурации фишек целочисленную величину $S,$ которая равна сумме чисел в клетках, занятых фишками. Тогда $S$ не меняется при действиях Гоши. Пусть последовательность ${ai}$ быстро растет как функция от $i,$ например, $i ai = 2.$ Покажем, что в этом случае $S$ строго увеличивается с каждым действием Саши.

Пусть Саша выбрал прямоугольник, у которого левая верхняя и правая нижняя клетки имели числа $ak$ и $al.$ Заметим, что в нашей расстановке для всякого числа $am$ числа, находящиеся строго ниже и левее него, имеют большие номера. Поэтому после хода Саши числа изменятся с $ak$ и $al$ на $ak+h$ и $al−h$ , где $h+ 1$ — высота выбранного прямоугольника, измеренная в клетках $(h≥ 1).$ Тогда

ak+h+ al−h =2k+h+ 2l−h >2k+ 2l = ak +al

Значит, $S$ станет строго больше. При этом $S$ все время остается целочисленным. Так как $S$ ограничено сверху (как минимум, оно меньше, чем $2025a2n−1),$ игра не может продолжаться бесконечно.

Ответ:

Не могут

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

Задача 3#79799

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

(b) То же самое, но действие такое: убирается по камню с клеток $i$ и $i+ 1$ и кладётся камень в клетку $i+ 2.$ Докажите, что все расстановки, получаемые из заданной начальной, в которых в каждой клетке не более одного камня и нет двух соседних занятых клеток, одинаковые.

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

(a) Докажем, что данный процесс не может продолжаться бесконечно. Пусть в начале на полосе лежат $n$ камней. За каждый ход общее количество камней уменьшается на $1,$ следовательно общее количество ходов не превосходит $n,$ то есть конечно.

Пронумеруем все клетки, начиная с крайней левой, в которой находится камень, натуральными числами от $1$ до $m.$ Пусть в клетки с номером $i$ в начале лежит $ai$ камней. Рассмотрим величину

m∑ S = ai⋅2i i=1

Докажем, что значение $S$ является инвариантом. Действительно, пусть за ход два камня из клетки с номером $k$ переложили в клетку с номером $k+ 1.$ Пусть $S′$ — значение $S$ после хода, тогда

′ k k+1 S = S− 2⋅2 +2 = S

Осталось заметить, что в конце процесса в каждой клетке находится не больше одного камня. Тогда $am-...a1-$ — двоичная запись числа $S,$ в которой все цифры определены единственным образом, а значит и количество камней в каждой клетке в конце процесса определено единственным образом.

(b) Аналогично предыдущему пункту покажем, что процесс не может продолжаться бесконечно. Пусть камень, лежащий в клетке с номером $k,$ имеет вес $Fk$ (число Фибоначчи). Тогда операция не меняет сумму весов, а финале получится запись исходной суммы весов в фибоначчиевой системе счисления.

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

Задача 4#79854

На доске написаны три натуральных числа $x,y,z.$ Петя записывает на бумажку произведение каких-нибудь двух из этих чисел, а на доске уменьшает третье число на $1.$ С новыми тремя числами на доске он снова проделывает ту же операцию, и так далее до тех пор, пока одно из чисел на доске не станет нулем. Чему будет в этот момент равна сумма чисел на Петиной бумажке?

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

На каждом шаге Петя уменьшает произведение чисел на доске на число, которое он пишет на бумажке: $xy(z− 1)= xyz− xy,$ поэтому произведение чисел на доске сложенное с суммой чисел на бумажке не изменяется. Поскольку в конце произведение на доске будет равно $0,$ сумма на бумажке равна исходному произведению $xyz.$

Ответ:

$xyz$

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

Задача 5#70792

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

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

Подсказка 1

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

Подсказка 2

(n, n, n) - (n-1, n-1, n+1) - (n, n-2, n). Что общего сохраняется у кучек после любого хода?

Подсказка 3

Обратим внимание на чётность количество камней в кучах на каждом ходе!

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

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

Ответ:

Ни при каких

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

Задача 6#74329

На столе лежали две колоды, по $36$ карт в каждой. Первую колоду перетасовали и положили на вторую. Затем для каждой карты первой колоды посчитали количество карт между ней и такой же картой второй колоды (т.е. сколько карт между семерками червей, между дамами пик, и т.д.). Чему равна сумма $36$ полученных чисел?

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

Рассмотрим самую нижнюю карту нижней колоды и такую же карту верхней колоды, пусть, например, это короли треф. Предположим, что в верхней колоде король треф лежит на семёрке бубен. Заметим, что если мы в верхней колоде поменяем местами короля треф и семёрку бубен, то количество карт, лежащих между королями треф, на одну уменьшится, а количество карт, лежащих между семёрками бубен, на одну увеличится. Значит, искомая сумма от такой перестановки не изменится. Рассуждая аналогично, можно постепенно менять местами короля треф из верхней колоды с картами, на которых он лежит, до тех пор, пока король треф не станет самой нижней картой в верхней колоде. Далее рассмотрим вторую снизу карту нижней колоды и повторим описанную процедуру с такой же картой из верхней колоды, и так далее. Так, постепенно меняя местами соседние карты верхней колоды, можно, не изменяя искомой суммы, расположить карты верхней колоды в том же порядке, что и в нижней. Тогда между каждыми двумя одинаковыми картами будет лежать ровно $35$ карт, поэтому искомая сумма равна $35⋅36= 1260.$

Ответ:

$1260$

Курсы

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

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

Задача 7#74885

Во всех клетках на диагонали доски $n× n,n≥ 4,$ стоят знаки « $+$ », в остальных клетках « $−$ ». За ход в случайной строке либо столбце меняются знаки: « $+$ » $↔$ « $−$ ». Докажите, что в любой момент игры плюсов не менее $n.$

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Для каждой клетки ( $k,k$ ) на диагонали квадрата (то самой, на которой стояли знаки « $+$ ») построим домик — четверку клеток ( $k,k$ ), ( $k+ 1,k$ ), ( $k,k+ 2$ ), ( $k+ 1,k +2$ ); все индексы здесь считаются вычетами по модулю $n.$ Заметим, что домики разных клеток не пересекаются: в столбце $k$ находятся клетки ( $k,k$ ) и ( $k +1,k$ ) из домика ( $k,K$ ) и ( $k− 2,K$ ), ( $k− 1,k$ ) из домика ( $k − 2,k− 2$ ); другие домики на этот столбец не залезают.

$PIC$

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

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

Задача 8#75915

В вершинах правильного $2023$ -угольника расставлены попарно различные положительные числа. За одну операцию разрешается поменять два числа $a$ и $b$ местами, если сумма двух наиболее удаленных от $a$ чисел равна сумме двух наиболее удаленных от $b$ чисел, и при этом $a$ и $b$ не являются наиболее удаленными друг от друга. Докажите, что при помощи таких операций нельзя переставить два числа в соседних вершинах так, чтобы все остальные числа оказались на своих исходных местах.

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

Подсказка 1

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

Подсказка 2

Обозначим вершины многоугольника a₁,a₂ ... a₂₀₂₃ в порядке обхода. Давайте переставим числа так, чтобы соседними с a_i стали самые удалённые от a_i. Теперь стоит понять, как в новой расстановке будут расставлены соседи в исходной.

Подсказка 3

Задачу можно переформулировать так:

Подсказка 4

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

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

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

$PIC$ $PIC$

Переобозначим числа на круге на $b1, b2, ..., b2023$ в порядке обхода окружности после перестановки. Тогда мы можем поменять $bi$ и $bj$ местами, если сумма соседей равна, сами они не соседи.

Теперь наше условие выглядит так: "По кругу расставлены попарно различные числа $b1, b2, ..., b2023.$ Можно поменять местами любые два не соседних числа, если суммы их соседей равны. Можно ли такими действиями получить расстановку, отличающуюся от исходной поменянными местами двумя числами, стоящих через одно". Если на эту задачу ответ отрицательный, то и на исходную он тоже отрицателен.

Рассмотрим сумму произведений соседних чисел. Пусть мы поменяли местами числа $x$ и $y$ с соседями $s$ и $t,u$ и $w$ соответственно. Тогда наша сумма изменится на величину

−xs− xt− yu− yw+ xu+ xw+ ys+ yt= (−x+ y)(s+ t− u − w) =0

т.к. $s+t= u+ w.$ Значит, при наших операциях эта сумма не меняется.

Но посмотрим, как эта сумма выглядит в расстановке, которую хотелось бы получить. Пусть поменялись местами числа $x$ и $y$ с соседями $a$ и $b,b$ и $c$ соответственно. Тогда получившаяся сумма отличается от исходной на

−xa+ xc− yc+ya= (x− y)(c− a)⁄= 0

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

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

Задача 9#112340

Игорь написал на доске числа $a ,a,a ,...,a , 1 2 3 100$ именно в таком порядке. Раз в минуту Паша отсчитывает $2k$ чисел с начала ряда при некотором целом $k$ и следующие за ними четыре числа $a,$ $b,$ $c,$ $d$ меняет на два числа $ac+ bd$ и $ad+ bc$ в любом порядке. Через $49$ минут на доске остались $2$ числа.

(a) Докажите, что сумма этих чисел не зависит от порядка действий;

(b) Докажите, что сами числа не зависят от порядка действий;

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

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

Объединим числа в пары: число с нечетным номером и следующее за ним. На самом деле Петя каждую минуту меняет две стоящие рядом пары на новую. Можно ли найти теперь какой-нибудь инвариант?

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

Пусть пары (a,b), (c,d) были заменены на (ac+bd,ad+bc). Тогда, как легко видеть, (ac+bd)+(ad+bc)=(a+b)(c+d). Какой тогда выходит инвариант?

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

Верно! Произведение сумм чисел в парах — инвариант. А что получится, если применить этот инвариант к числам, получившимся через 49 минут?

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

В предыдущем пункте мы показали, что сумма последних чисел X и Y не зависит от операций. А можно ли найти похожий инвариант, выражающий какую-нибудь другую операцию для X, Y?

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

Верно! Для суммы не хватает разности! А действительно ли произведение разностей компонент — инвариант?

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

Сумма и разность для X и Y определены однозначно! А как тогда показать, что и сами X, Y определены однозначно?

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

Будем рассматривать числа в парах $(a ,a ). 2i+1 2i+2$ Тогда каждую минуту Петя заменяет две пары $(a,b), (c,d)→ (ac+bd,ad+bc),$ будем $i$ -ое число после $j$ минут обозначать как $j ai.$

Заметим, что:

(ac+ bd)+ (ad +bc)=a(c+ d)+ b(c+ d)= (a +b)(c+ d)

Введём инвариант:

5∏0−j Sj = (aj2i−1+ aj2i)-произведение сумм чисел в парах i=1

Каждая операция сохраняет значение $Sj.$ После всех операций останется одна пара чисел $X$ и $Y,$ причём:

X + Y = S0

Отсюда получается, что пункт $a$ доказан. Также заметим, что:

(ac+ bd)− (ad +bc)=a(c− d)− b(c− d)= (a − b)(c− d)

Тогда введем аналогичный инвариант:

D =50∏−j(aj − aj)-произведение разностей чисел в парах j i=1 2i−1 2i

Он также не изменяется при любых операциях, тогда для оставшихся в конце чисел верно:

X − Y = D0

Тогда

( 50 50 ) X = S0+D0-= 1 ∏ (a2i−1+ a2i)+∏ (a2i−1 − a2i) 2 2 i=1 i=1

( 5∏0 ∏50 ) Y = S0-− D0-= 1 (a2i−1+a2i)− (a2i−1− a2i) 2 2 i=1 i=1

Тем самым пункты $b$ и $c$ доказаны.

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

Задача 10#33444

Можно ли монетами в $10$ и $15$ сиклей набрать ровно $2019$ сиклей?

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

Подсказка 1:

У всех сумм, набранных монетами из 10 и 15 сиклей, имеется какое-то общее свойство. Что это может быть и зачем это для задачи?

Подсказка 2:

Скажем, если 2019 не будет обладать этим свойством, то задача будет решена.

Подсказка 3:

Обратите внимание на делимость всех таких сумм на некоторые числа.

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

Заметим, что и $10$ , и $15$ делятся на $5$ . Поэтому любая сумма, которую мы можем ими набрать, также будет делиться на $5$ . Но число $2019$ на $5$ не делится, значит, набрать его этими монетами нельзя.

Ответ: Нет, нельзя

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

Задача 11#33445

Профессор Снейп написал на доске три числа: $100$ , $200$ и $2019$ . За одну операцию он разрешает Гарри Поттеру выбрать два различных числа $x$ и $y$ (причем $x> y$ ) и записать вместо них числа $x− y$ и $2y$ , а старые числа стереть. Гарри сдаст зачет по зельеварению, если получит на доске числа $1000$ , $2000$ и $3000$ . Есть ли у Гарри Поттера шансы сдать зачет?

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

Способ 1. Посмотрим на сумму чисел на доске. При замене чисел $x$ и $y$ на числа $x− y$ и $2y$ , их сумма не меняется: $x − y +2y = x+ y$ . Поэтому сумма всех чисел на доске так и останется равной $100+ 200+ 2019 =2319$ . Значит, получить числа $1000$ , $2000$ и $3000$ , имеющие сумму $1000+ 2000 +3000= 6000$ , нельзя.

Ответ: Шансов нет

Интенсивы

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

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

Задача 12#33446

Шахматный слон ходит по диагонали на любое число клеток. Может ли за $100$ ходов слон с нижней левой угловой клетки шахматной доски $8× 8$ дойти до верхней левой угловой клетки?

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

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

Ответ: Нет, не может

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

Задача 13#34058

В языке Древнего Московского Племени алфавит состоит всего из двух букв: “М” и “О”. Два слова являются синонимами, если одно из другого можно получить при помощи исключения или добавления буквосочетаний “МО” и “ООММ”, повторяемых в любом порядке и любом количестве. Являются ли синонимами в языке Древнего Московского Племени слова “ММО” и “ОММО”?

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

Решение 1: Заметим, что при исключении или добавлении буквосочетаний «МО» или «OOMM» четность букв в слове не меняется (это и есть инвариант). Так как в словах «ММО» и «ОММО» четность букв разная, то эти слова не могут быть синонимами.

Решение 2: Посмотрим на четность разности количества букв «О» и «М» в слове. Так как в буквосочетаниях «МО» и «OOMM» количество букв «О» и «М» равное, то при их добавлении или исключении из слова, разность количества букв «О» и «М» в слове не меняется. Осталось заметить, что в словах «ММО» и «ОММО» эта разность равна 1 и 0 соответственно, значит, данные слова не синонимы.

Ответ: Нет

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

Задача 14#34060

Артур играется с шариками. На полу у него разбросано больше ста шариков, а в двух коробках лежат по 9 шариков. За один ход Артур может убрать из любой коробки 1 шарик или убрать 1 шарик из левой коробки и одновременно с этим положить 9 шариков с пола в правую. Докажите, что ходы рано или поздно Артур все шарики разбросает по полу.

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

В этой задаче суммарное количество шариком полуинвариантом не является: оно может как уменьшаться, так и увеличиваться. Зато в качестве полуинварианта подойдет следующая величина. Обозначим на очередном шаге количество шариков в первой коробке через $a$ , а во второй — через $b$ . Проследим за величиной $10a +b$ . Если за один ход убирается один шарик, то эта величина, очевидно, уменьшается. Если убирается шарик из левой коробки и добавляется $9$ в правую, то величина уменьшается на $1$ . Таким образом, рано или поздно величина станет равна $0$ . Так как количества шариков в коробках неотрицательные, то в этот момент в обеих коробках по 0 шариков. Значит, Артур разбросал все шарики по полу.

Ответ:

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

Задача 15#34067

На квадратном поле $10× 10$ девять клеток $1×1$ поросли бурьяном. После этого бурьян может распространиться на клетку, у которой не менее двух соседних клеток уже поросли бурьяном. Докажите, что тем не менее бурьян не сможет распространиться на все клетки.

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

Посмотрим, что происходит с периметром всей клетчатой фигуры, заросшей бурьяном. Когда новая клетка заполняется бурьяном, она имеет хотя бы две заросшие соседние клетки, а значит, хотя бы две ее стороны уже до ее заполнения посчитаны в общем периметре всей фигуры. Тогда после ее заполнения она сможет добавить в периметр не более двух новых сторон (то есть увеличить не более, чем на 2), но все ее стороны, которыми она примыкает к соседним заросшим клеткам, ”удалятся“ из периметра, то есть больше не будут на границе фигуры. Значит, периметр уменьшится хотя бы на 2. Итого, периметр не может увеличиться после одной операции.

Тогда периметр на протяжении всего процесса будет $≤ 4⋅9$ (изначальный периметр девяти клеток), а значит, не сможет стать равным $4⋅10$ (периметр всего поля).

Ответ: Задача на доказательство

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

Задача 16#38624

У Ани есть шестерка и 7 девяток. Раз в минуту она может перевернуть какие-нибудь две цифры. Может ли у нее оказаться поровну шестерок и девяток? В ответ укажите “да” или “нет”.

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

Подсказка 1

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

Подсказка 2

Какие здесь вообще есть параметры? Сумма? Может быть. Произведение? Точно не не подходит. Сумма кол - ва 6

Подсказка 3

Верно, на число 4, так как если мы увеличиваем или уменьшаем на 4, то остаток не меняется, ровно как и если мы прибавляем 0. Тогда, выходит, что разность кол - ва 6 и 9 имеет константный остаток при делении на 4. Осталось посмотреть на остаток начального набора и того, который просят получить в задаче!

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

Посмотрим на разность между количеством шестёрок и девяток. После любой из операций она может либо измениться на $4$ в любую сторону, либо же не измениться совсем. Но это означает, что она не меняет свой остаток от деления на $4$ . Изначально он был равен $(7− 1) ≡2 (mod 4)$ , а должен стать равным $0$ — противоречие.

Ответ: нет

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

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

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

Задача 17#39362

Есть три кучки камней: в первой $51$ камень во второй — $49$ , а в третьей — $5$ . Разрешается объединять любые кучки в одну, а также разделять кучку, состоящую из чётного числа камней, на две равные. Можно ли получить $105$ кучек по одному камню в каждой?

В ответ внесите “да” или “нет”.

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Заметим, что если в некоторый момент количество камней в каждой кучке делится на нечётное число $a$ , то и во всех получаемых разрешёнными действиями кучках количество камней будет делиться на $a$ . После первого хода можно получить три варианта размещения камней: кучки из $100$ камней и $5$ камней (общий делитель $5$ ), из $56$ камней и $49$ камней (общий делитель $7$ ), из $51$ камня и $54$ камней (общий делитель $3$ ). Поэтому не удастся получить ни одной кучки из одного камня.

Ответ: нет

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

Задача 18#42222

На доске написано число $12$ . Каждую минуту число умножают или делят либо на $2$ , либо на $3$ и результат записывают на доске вместо исходного числа. Докажите, что число, которое будет написано на доске ровно через час, не будет равно $54.$

Источники: Муницип - 2021, 9 класс

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

Подсказка 1

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

Подсказка 2

Верно, каждую минуту мы меняем какую-то из степеней на 1, чтобы найти по какому параметру искать инвариант можно попробовать сравнить свойства чисел 12 и 54.

Подсказка 3

Можно посмотреть на степень двойки в 12 и в 54 или на сумму степеней в них и найти в каждом из случаев противоречие. Подумайте, как меняются эти свойства каждые 2 минуты и какой инвариант можно найти?

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

Заметим, что $12 =22⋅3$ , а $54= 2⋅33$ . Каждую минуту один из показателей степени меняется на единицу, т.е. сумма степеней меняет четность. Отсюда следует, что через час четность суммы степеней будет той же, что и у исходного числа. Однако сначала сумма степеней была равна $3$ , т.е. числу нечетному, а в конце оказалась равной $4$ , т.е. числу четному.

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

Задача 19#122864

В языке три буквы — Ш, У и Я. Словом называется последовательность из $100$ букв, ровно $40$ из которых — гласные (то есть У или Я), а остальные $60$ — буква Ш. Какое наибольшее количество слов можно выбрать так, чтобы у любых двух выбранных слов хотя бы в одной из $100$ позиций стояли гласные, причем различные?

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

Пример. Рассмотрим все $240$ слов, у которых начиная с $41$ -ой все буквы Ш, а первые $40$ — У или Я. Этот набор слов удовлетворяет условию.

Оценка. Каждому из наших $m$ слов сопоставим $60 2$ слов, заменяя каждую букву Ш, на У или Я (всеми возможными способами). Заметим, что полученные $60 m ⋅2$ слов состоят из букв У и Я и попарно различны (для слов, полученных из одного и того же, это ясно из построения, а для слов, полученных из двух разных, следует из условия). Таким образом, $60 100 m ⋅2 ≤ 2$ и $40 m ≤ 2 .$

______________________________________________________________________________________________________________________________________________________

Замечание. Оценку можно получить по-другому.

Способ 1. Подкинем монетку $100$ раз. Для каждого слова рассмотрим такое событие: при всяком $i$ если на некоторой позиции $i$ стоит буква У, то при $i$ -м подбрасывании выпала решка, а если буква Я, то орёл. Вероятность такого события равна $1∕240,$ и они не совместные, поэтому количество слов не больше чем $240.$

Способ 2. Пусть выбрано более $240$ слов. Присвоим каждому слову вес $1.$ Пусть первая буква у $x$ слов У, у $y$ слов — Я и $x ≥y.$ Удвоим веса всех слов с первой буквой У, и обнулим — с первой буквой Я. Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения $m$ -ой буквы. Пусть $p$ — сумма весов слов, у которых $m$ -ая буква У, $q$ — сумма весов слов, у которых $m$ -ая буква Я. Если $p≤ q,$ удваиваем веса у слов с $m$ -й буквой Я и обнуляем — с $m$ -й буквой У. Иначе — наоборот. В результате таких операций сумма весов не уменьшается. После $100$ операций сумма весов всех слов будет больше $240.$ В каждом слове только $40$ букв У или Я, поэтому вес каждого слова не больше $240.$ Значит, найдутся два слова с одинаковыми весами. Тогда для них не найдется позиции, в которой у одного У, а у другого Я или наоборот, противоречие.

Ответ:

$240$

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

Задача 20#42215

Можно ли так расставить по кругу $100$ чисел $1$ и $101$ число $− 1$ так, чтобы произведение любых трех подряд идущих чисел было положительным?

Источники: Муницип - 2020, Московская область, 7.3

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

Подсказка 1

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

Подсказка 2

Всего у нас 100 единиц и 101 минус единиц, итого 201 число. Число 201 можно разложить на множители как 3 * 67, значит, весь круг разобьется на 67 троек, каждая из которых имеет положительное произведение. Что тогда мы можем сказать про произведение всех чисел вместе из круга?

Подсказка 3

У нас 100 единиц и 101 минус единица, какое знак будет иметь произведение всех чисел вместе? Как оно соотносится с результатом произведения всех чисел на прошлом шаге, когда мы поделили все числа на тройки?

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

Предположим, что такое возможно. Так как всего чисел $100+101= 201= 3⋅67$ , то разобьем их все на $67$ троек подряд идущих чисел. В каждой тройке произведение чисел положительно, поэтому произведение всех чисел также положительно. Но произведение $100$ чисел $1$ и $101$ числа $− 1$ равно $− 1$ , то есть отрицательно.

Ответ: нет

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

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