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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У Пети в двух карманах было по одинаковому количеству монет. Он высыпал все эти монеты на стол и подсчитал, что орлов выпало на $7$ больше, чем решек. Докажите, что он ошибся.

Источники: Муницип - 2023, Ростов, 7.2 (см. tasks.olimpiada.ru)

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

Пусть в каждом кармане было по $k$ монет, а орлов выпало $x$ , тогда решек выпало $2k− x$ . Их разность: $x− (2k− x)= 2(x− k)$ — чётное число и не может равняться 7.

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

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

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

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

Игорь написал на доске числа $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$ доказаны.

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

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

На доску записывают пары чисел. Сначала на доску записали пару чисел $(1,2).$ Если на доске написана пара чисел $(a,b),$ то на доску можно дописать пару $(−a,− b),$ а также пару $(−b,a+ b).$ Кроме того, если на доске написаны пары чисел $(a,b)$ и $(c,d),$ то на доску можно дописать пару $(a+c,b+d).$ Могла ли через некоторое время на доске оказаться пара $(2022,2023)?$ Порядок чисел в паре существенен, например, пары чисел (1, 2) и (2, 1) считаются различными.

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

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

Подсказка 1:

Попробуйте найти какой-нибудь инвариант при таких операциях.

Подсказка 2:

Рассмотрите выражение 2a – b. Как оно меняется при применении операций к паре (a, b)?

Подсказка 3:

Обратите внимание на остаток от деления 2a – b на 7. Как он меняется?

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

Первое решение. Докажем, что для любой пары $(x,y),$ записанной на доске, число $2x− y$ делится на $7.$

Действительно, для пары $(1,2)$ число $2⋅1− 2= 0$ делится на 7.

Пусть для пары $(a,b)$ число $2a − b$ делится на $7.$ Тогда для пары $(−a,− b)$ число

2⋅(− a)− (−b)=− (2a− b)

делится на $7,$ и для пары $(−b,a +b)$ число

2⋅(−b)− (a +b)= −a− 3b=3(2a− b)− 7a

делится на $7.$

Пусть для пар $(a,b),(c,d)$ числа $2a − b,2c − d$ делятся на 7. Тогда для пары $(a+c,b+ d)$ число

2(a+ c)− (b+ d)= (2a− b)+ (2c− d)

делится на $7.$

Так как для пары $(2022,2023)$ число

2⋅2022− 2023= 2021

не делится на $7,$ эта пара на доске появиться не может.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Будем к каждой паре $(a,b)$ на доске добавлять третье число $c= −a − b.$ Тогда сумма чисел в каждой тройке будет равна нулю, а правила дописывания новых пар будут такими: если на доске записана тройка $(a,b,c),$ то можно дописать тройки $(−a,−b,− c)$ и $(−b,−c,−a),$ а если записаны тройки $(a,b,c)$ и $(d,e,f),$ то можно дописать тройку $(a +d,b+ e,c+ f)$ — назовём эту тройку суммой троек $(a,b,c)$ и $(d,e,f).$ Также для тройки $(a,b,c)$ и целого числа $k$ обозначим через $k ⋅(a,b,c)$ тройку $(ka,kb,kc).$

______________________________________________________________________________________________________________________________________________________

Утверждение. Докажем, что все тройки, появляющиеся на доске, имеют вид

(a,b,c)=k ⋅(1,2,−3)+ ℓ⋅(2,−3,1)+ m ⋅(−3,1,2) (∗)

с целыми $k,$ $ℓ$ и $m.$ В начальный момент времени это верно:

(1,2,−3)= 1⋅(1,2,−3)+0 ⋅(2,− 3,1)+ 0⋅(− 3,1,2).

Теперь достаточно показать, что из троек, имеющих вид $(∗),$ также получаются лишь такие тройки. Для операции взятия суммы троек это очевидно. Для остальных операций это тоже несложно проверить: если $(a,b,c)$ имеет вид $(∗),$ то

(−a,−b,− c)= (−k)⋅(1,2,− 3)+ (−ℓ)⋅(2,−3,1)+ (− m)⋅(−3,1,2),

(−b,−c,−a)= (−m)⋅(1,2,−3)+ (−k)⋅(2,− 3,1)+ (−ℓ)⋅(−3,1,2).

Утверждение доказано.

_________________________________________________________________________________________________________________________________________________________________________________

Предположим теперь, что на доске появилась тройка (2022, 2023, -4045), то есть она имеет вид $(∗).$ Тогда имеем

2022= k+2ℓ− 3m и 2023= 2k− 3ℓ+ m.

Выражая из первого равенства $k =2022− 2ℓ+ 3m$ и подставляя во второе, получаем

2023= 2⋅2022− 7ℓ+7m,

то есть

7(m − ℓ)= 2023− 2⋅2022 =− 2021.

Однако это невозможно, поскольку $2021$ не делится на $7.$

Ответ:

не могла

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

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

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

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

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

Подсказка 1:

Для удобства расстояние между соседними столбами примем за единичное. Также пронумеруем их от 1 до n. Пусть nᵢ — количество столбов i-го цвета. Сколько всего будет искомых пар?

Подсказка 2:

Несложно догадаться, что для одного цвета таких пар nᵢ − 1 (количество промежутков). Значит, всего n₁ − 1 + ... + nₖ − 1 = n − k. Задача на оценку + пример, однако по условию нам дана только различность всех расстояний. Для примера, как мы можем оценить сумму 2-ух различных натуральных чисел, зная, что они от 1 до 5?

Подсказка 3:

Очевидно, что она ≥ 1 + 2 и ≤ 4 + 5. Применим аналогичную идею, только сумму чего будем оценивать?

Подсказка 4:

Кажется, хорошей идеей будет оценить сумму всех расстояний S. S ≥ 1 + 2 + ... + (n − k) = (n − k)(n − k − 1)/2. Да, мы получили какое-то неравенство, но оценку на количество из него пока что не вывести. Какое неравенство мы хотим получить для итоговой оценки?

Подсказка 5:

То, где с обеих сторон участвуют только переменные n и k. С правой частью мы справились, что же делать с левой?

Подсказка 6:

Необходимо выразить или оценить сверху S с помощью n и k (идея двойного подсчёта). Зайдём из далека. Как можно посчитать (не оценить) сумму расстояний для конкретного цвета?

Подсказка 7:

Попробуем сначала самым честным и пробивным способом. Пусть d₁, ..., dₚ — номера столбов первого цвета (НУО). Тогда искомая величина равна d₂ − d₁ + d₃ − d₂ + ... + dₚ − dₚ₋₁. А если покороче?

Подсказка 8:

Сумма расстояний для первого цвета = dₚ − d₁ (в целом, это интуитивно). Может обобщим эту идею?

Подсказка 9:

Пусть aᵢ — номер первого столбца i-го цвета, bᵢ — последнего. Тогда чему же равно S?

Подсказка 10:

S = b₁ − a₁ + ... + bₖ − aₖ = b₁ + ... + bₖ − (a₁ + ... + aₖ). Однако переменных k и n мы пока что не наблюдаем. Как бы их привязать к этому выражению?

Подсказка 11:

Разумеется, в явном виде выразить через n и k мы не сможем (ибо сумма может быть разной), значит, нужно вновь оценить сверху (чтоб нам на руку сыграла транзитивность в неравенствах). Посмотрим, что мы имеем: две суммы различных чисел. Кажется, мы где-то это уже видели...

Подсказка 12:

Поскольку мы хотим получить оценку сверху на S, то сумму b₁ + ... + bₖ нужно оценить снизу, а a₁ + ... + aₖ сверху. Метод нам известен, а что же получается в итоге?

Подсказка 13:

S ≤ k(n − k) (получите данный вид самостоятельно). Что же мы имеем? (n − k)(n − k − 1)/2 ≤ S ≤ k(n − k). Какая оценка на n у нас получилась?

Подсказка 14:

n ≤ 3k − 1. Осталось придумать пример. Он строится из оценки, всего лишь необходимо гарантировать равенства во всех выше написанных неравенствах. Успехов!

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

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

Оценка. Пусть $n$ столбов покрашено так, что условие задачи выполнено. Пусть $ni$ — количество столбов $i$ -го цвета (далее считаем, что $ni ≥ 1,$ т.е. все цвета присутствуют, иначе можно увеличить $n,$ добавив столб нового цвета в конец). Пусть $ai$ и $bi$ — номера первого и последнего столбов $i$ -го цвета.

Всего у нас есть

t=(n1− 1)+(n2− 1)+ ...+ (nk − 1)= (n1+n2+ ...+ nk)− k =n − k

хороших пар столбов. Поскольку все расстояния между столбами в хороших парах различны, наименьшее из этих расстояний не меньше 1, следующее — не меньше 2, и т.д. Итак, для суммы $S$ расстояний во всех хороших парах получаем оценку

S ≥ 1+2+ ...+ t= t(t+ 1)∕2

С другой стороны, сумма всех расстояний для $i$ -го цвета равна $b − a. i i$ Поэтому

S = (b1+ ...+ bk)− (a1 +...+ ak)

Сумма $b1+ ...+bk$ не превышает суммы $k$ самых больших среди номеров 1, 2, …, $n,$ а сумма $a1+ ...+ ak$ не меньше, чем сумма $k$ наименьших среди номеров 1, 2, …, $n,$ поэтому

S ≤ (n+ (n− 1)+ ...+(n− k+ 1))− (1+2+ ...+ k)=

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

Итак,

t(t+1)∕2≤S ≤ kt,

откуда $t≤ 2k− 1$ и

n= k+ t≤3k− 1.

Пример. Годится, например, покраска

1,2,...,k− 1,k,k,k− 1,...,2,1,2,3,...,k

Здесь для цвета 1 единственная хорошая пара, и расстояние между столбами в ней равно $2k− 1.$ Для всех остальных цветов есть две хорошие пары, при этом для цвета 2 имеем расстояния $2k− 3$ и 2, для цвета 3 — расстояния $2k− 5$ и 4, и т.д., для цвета $k$ — расстояния 1 и $2k− 2.$

Ответ:

$3k− 1$

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

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

Изначально в строку выписывают 250 букв — 125 букв A и 125 букв B в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв A и B, и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы A на буквы B и буквы B на буквы A. (Например, из строки ABABBAB можно одной операцией получить строку ABBAABAB.) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке?

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

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

Подсказка 1:

Попробуйте найти какой-нибудь инвариант для операции из условия.

Подсказка 2:

Можно посмотреть на количество букв, обладающих каким-либо свойством.

Подсказка 3:

Обратите внимание на количество букв А на нечётных позициях. Как оно меняется при проведении операции?

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

Первое решение. Пронумеруем позиции в строке слева направо числами от 1 до 250. Пусть в исходной строке $x$ букв A стоят на нечётных местах (т. е. местах с нечётными номерами). Покажем, что в полученных строках это количество не изменится.

Действительно, пусть для некоторой операции выбран кусок, в котором по $y$ букв A и B, причём $t$ из этих букв A стоят на нечётных местах. Тогда на чётных местах в куске стоят $y− t$ букв A и, следовательно, $y− (y− t)= t$ букв B. После операции именно из этих $t$ букв B возникнут буквы A, стоящие на нечётных местах куска — значит, количество таких букв A не поменяется.

Итак, в любой полученной строке будет ровно $x$ букв A на нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно $125− x$ букв A. Поскольку $125− x⁄= x,$ требуемое невозможно.

_________________________________________________________________________________________________________________________________________________________________________________

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

Рассмотрим одну операцию с куском длины $2y.$ При этой операции пары из букв, не лежащих в куске, сохраняют свой тип. Далее, для каждой буквы вне куска было ровно $y$ пар, содержащих её и букву из куска; столько же таких пар осталось, и все эти пары были и стали одного и того же типа.

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

Ответ:

нельзя

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

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

Кар-Карыч задумал число, прибавил к нему 1, потом разделил сумму на 3, умножил на 4, отнял 6, разделил на 7 и получил число 2. Какое число он задумал?

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

Будем раскручивать операции с конца. После последнего деления на 7 Кар-Карыч получил число 2, следовательно, до этого действия у него было число $2⋅7= 14$ . До предыдущего (до того, как отнял 6) — $14 +6= 20$ , еще одно действие назад — $20 :4=5$ , после первого — $5⋅3= 15$ , и в самом начале — $15− 1= 14$ .

Ответ: 14

Курсы

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

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

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

Трудолюбивые бурундучки заготавливают дрова на зиму. Заготовку начали еще в начале осени, 1-го сентября, и в первый день положили на склад всего одно бревно, ведь до зимы было еще далеко. Каждый следующий день количество бревен увеличивалось ровно в 2 раза, и склад был заполнен целиком в последний день осени, 30-го ноября. В какой день склад был заполнен ровно наполовину?

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

Пойдем с конца. Так каждый день бревен становилось ровно в 2 раза больше, то, если пойти назад, бревен будет становиться в 2 раза меньше. Значит, 30 ноября склад был заполнен полностью, а 29-го ноября склад был заполнена наполовину.

Ответ: 29 ноября

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

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

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

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

Если произведение 4 натуральных чисел нечетно, то все эти 4 числа обязательно нечетны. Но сумма 4 нечетных чисел четна, значит, Совунья не права.

Ответ: Нет, не могут

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

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

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

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

Покрасим четные числа в красный цвет, а нечетные в синий. Так как по кругу стоят 11 чисел, то красные и синие числа не могут чередоваться, то есть идти в порядке …К-С-К-С…. Это значит, что найдутся два одноцветных рядом стоящих числа, то есть два соседних числа одной четности. Тогда их сумма четна, и Бараш сможет указать именно эти два числа.

Ответ: Да, всегда

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

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

Совунья игралась со своей любимой шахматной доской $8× 8$ . В процессе она случайно пролила на нее зеленую краску. Может ли оказаться так, что количество испачканных краской клеток на 9 больше, чем не испачканных?

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

Если бы так случилось, что количества испачканных краской клеток и неиспачканных отличаются на 9, то эти количества были бы разной четности. Тогда их сумма нечетна. Но их сумма равна общему числу клеток на шахматной доске, то есть равна 64 — четному числу, чего быть не может. (Как будто бы не может быть что 64 - четное число) Значит, такого быть не могло.

Ответ: Нет

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

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

На празднование дня города мышата испекли огромный торт. Сначала к нему подошел Лосяш и взял себе половину торта. Следующей половину оставшегося взяла себе Совунья. После этого за своим куском подходили еще трое: Крош, Нюша и Пин, и каждый брал половину оставшегося куска. При этом Пину достался ровно 1 килограмм торта. А сколько килограммов весил торт вначале?

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

Пойдем с конца. Раз Пин достался 1 килограмм, то весь оставшийся кусок перед тем, как он подошел, весил 2 кг. Эти 2 кг составляют половину того, сколько взяла Нюша, значит, перед ее приходом кусок весил 4 килограмма. Рассуждаем так дальше: раз после Кроша торт весил 4 кг, то и он съел 4 килограмма, значит, перед ним торт весил $4+ 4= 8$ килограммов. Именно столько осталось Совуньи, значит, она съела те же 8 килограммов, а перед ней торт весил 16 килограммов. Наконец, Лосяш тоже оставил после себя столько же, сколько съел сам, значит, съел он 16 килограммов, а весь торт весил изначально $16 ×2= 32$ килограмма.

Ответ: 32

Интенсивы

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

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

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

Лосяш в знак особой признательности подарил Барашу и Нюше по несколько пончиков. Заметив, что Барашу досталось меньше, Нюша отдала половину своих пончиков ему. Теперь Бараш сделал ответный жест дружбы и отдал половину своих пончиков Нюше. В ответ Нюша снова отдала половину своих пончиков Барашу, и принимать обратно даже один пончик не согласилась. В результате такой дележки у Нюши осталось 15 пончиков, а у Бараша — 31. По сколько пончиков у них было вначале?

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

Своим последним ходом Нюша отдала половину пончиков и у нее осталось 15, значит, эти 15 пончиков также составляют половину. Поэтому всего перед последней дележкой у нее было $15× 2= 30$ пончиков, а у Бараша — $31− 15= 16$ пончиков. Значит, перед тем, как Бараш делил свои пончики, у него их оказалось в 2 раза больше, чем 16, то есть $16× 2= 32$ . Тогда у Нюши до того, как часть пончиков ей вернул Бараш, осталось $30 − 16= 14$ . Поэтому перед тем, как она первый раз делила пончики, у нее было в 2 раза больше, чем 14, то есть $14× 2= 28$ пончиков, а у Бараша — $32− 14= 18$ , откуда и ответ.

Ответ: 28 у Нюши и 18 у Бараша.

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

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

Совунья решила сыграть сама с собой в шахматы. Но так как играть она не умеет, то она играет по очень странным правилам. Она выставляет на шахматную доску $8× 8$ все 32 фигуры, а затем по одной их убирает. Очередную фигуру Совунья убирает, только если рядом с ней на соседних по стороне клетках стоит нечетное число других фигур. Сможет ли Совунья так расставить фигуры и убирать их, чтобы в итоге на доске не осталось ни одной фигуры?

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

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

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

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

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

Студенты Хогвартса записывались на дополнительные курсы. На арифмантику записались 60 человек, на уход за магическими существами записались 50 человек, а на прорицания — 40 человек. Перед началом учебного года составили три списка: тех, кто записался ровно на один курс; тех, кто записался ровно на два курса из трех; тех, кто записался на все три курса одновременно. Оказалось, что во всех списках одно и то же число человек. Сколько?

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

Подсказка 1

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

Подсказка 2

Давайте сложим количество людей на всех трех кружках 60 + 50 + 40 = 150. Сколько раз в такой сумме мы посчитали людей, которые ходят только на один курс, на два, на три?

Подсказка 3

В данных 150 учащихся трижды встречаются те, кто записался на 3 курса, дважды встречаются те, кто записался на 2 курса и по одному разу те, кто ходит только на один курс. Учитывая что количество людей в каждой из такой групп равно, как можно найти это количество?

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

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

С одной стороны, так как на предметы записались 60, 50 и 40 человек, то и сданных тетрадок по арифмантике будет 60, по УЗМС — 50, а по прорицаниям — 40. В сумме получается $60 + 50 +40 = 150$ сданных тетрадок.

С другой стороны, студенты, записавшиеся на один курс, сдадут по одной тетрадке, и так как таких студентов $x,$ то и сданных ими тетрадок будет $x.$ Студенты, записавшиеся на два курса, сдадут по две тетрадки, и так как таких студентов тоже $x,$ то они сдадут всего $2x$ тетрадок. Наконец, $x$ студентов, записавшихся на все три предмета, сдадут $3x$ тетрадок. Поэтому всего сданных тетрадок будет $x +2x +3x = 6x.$

Приравняем посчитанные двумя способами тетрадки.

$6x= 150; x= 25.$

Итак, $x =25,$ значит, в одном списке 25 человек. Именно это число нам и нужно было посчитать в задаче.

Ответ: 25

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

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

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

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

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

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

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

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

Профессор Снейп написал на доске три числа: $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$ , нельзя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: Нет

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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