РЕШУ ОЛИМП: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 8 9
Атрибут

Тип 0 № 1815 Добавить в вариант

На круглом ожерелье висят n > 3 бусинок, каждая покрашена в красный или синий цвет. Если у какой-то бусинки соседние с ней бусинки покрашены одинаково, ее можно перекрасить (из красного в синий или из синего в красный). При каких n из любой исходной раскраски бусинок можно сделать ожерелье, в котором все бусинки покрашены одинаково?

(С. Берлов)

Решение.

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

I способ. (инвариант). Легко убедиться, что при любом перекрашивании количество пар соседних бусинок вида к-к либо не меняется, либо меняется ровно на 2, т. е. в любом случае не меняется четность этого числа. То же самое верно и про число пар вида с−с. В одноцветном ожерелье (четной длины) оба эти количества четны. Поэтому из ожерелья, в котором оба эти количества нечетны, нельзя получить ни одно из двух одноцветных ожерелий. При четном n таково, например, ожерелье

II способ. (критические ожерелья). Для n, кратного четырём, рассмотрим ожерелье вида ...−к−к−с−ск−к−с−с−..., в котором чередуются пары красных и пары синих бусинок. С этим ожерельем нельзя сделать ни одного перекрашивания. В частности, из него нельзя получить и одноцветное.

Если n четно, но имеет вид $n=4 k плюс 2,$ немного изменим вид критического ожерелья: ...−к−к−к−к−с−с−кк−с−с−... (один из красных блоков теперь имеет длину 4). С ним можно сделать лишь одно перекрашивание, точнее, два аналогичных  — перекрасить вторую или третью красную бусинку в длинном блоке. С полученным ожерельем можно сделать лишь две операции: обратную к только что проделанной или операцию, перекрашивающую бусинку, соседнюю с только что перекрашенной.

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

Ответ: при всех нечетных n.

Решение · Помощь

Тип 0 № 3722 Добавить в вариант

Илья берёт тройку чисел и преобразует её по правилу: на каждом шаге каждое число заменяется на сумму двух остальных. Чему равна разность между самым большим и самым маленьким числами в тройке на 1989-ем шаге применения этого правила, если изначальная тройка чисел была {70; 61; 20}? Если вопрос задачи допускает несколько вариантов ответа, то выпишите их без пробела в порядке возрастания.

Решение · Помощь

Тип 0 № 5746 Добавить в вариант

Про монотонно возрастающую функцию f(x), определённую для всех ненулевых x, известно, что $f левая круглая скобка x плюс f левая круглая скобка дробь: числитель: 1, знаменатель: x конец дроби правая круглая скобка правая круглая скобка =0.$ Найдите все такие функции f(x).

Решение · Помощь

Тип 0 № 5773 Добавить в вариант

Докажите, что для любых действительных x и y справедливо равенство

$||x| минус |y|| плюс |x| плюс |y|=|x минус y| плюс |x плюс y|.$

Решение · Критерии · Помощь

Тип 0 № 7965 Добавить в вариант

Найдите все различные натуральные числа x и y, для которых справедливо равенство $x ! плюс y=y ! плюс x.$

Решение · Помощь

Тип 21 № 8183 Добавить в вариант

Дана клетчатая доска 2020 × 2021. Петя и Вася играют в следующую игру. Они по очереди ставят фишки в свободные клетки доски. Выигрывает тот игрок, после хода которого в каждом квадрате 4 × 4 будет стоять фишка. Начинает Петя. Кто из игроков может обеспечить себе победу вне зависимости от действий соперника?

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

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

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

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

Факторы, влияющие на оценку.

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

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

3.  Если участник не довел задачу до ответа, то итоговая оценка за данную задачу не может превышать 1 балл.

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

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

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Решение · Критерии · Помощь

Тип 0 № 8189 Добавить в вариант

На центральной клетке доски 11 × 11 стоит фишка. Петя и Вася играют в следующую игру. Каждым своим ходом Петя передвигает фишку на одну клетку по вертикали или горизонтали. Каждый своим ходом Вася возводит стенку с одной из сторон любой из клеток. Двигать фишку через стенку Петя не может. Игроки ходят по очереди, начинает Петя. Петя выигрывает, если сможет фишкой уйти с доски. Может ли он обеспечить себе победу вне зависимости от действий соперника?

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 21 № 8933 Добавить в вариант

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

Решение.

Перед нами схема авиалиний страны, в которой, чтобы добраться из города 1 в город 100 не хватит 71 перелёта. Основная часть схемы состоит из повторяющихся блоков по 4 города, см. города 5, 6, 7 и 8.

Для того, чтобы попасть из города 1 в город 5, нужно 2 перелёта, затем из города 5 в город 93 по 3 перелёта за каждые 4 города, то есть 66 перелётов, и ещё 4 перелёта, чтобы добраться из города 93 в город 100, итого, минимум 72.

С другой стороны, 72 перелёта всегда достаточно, чтобы добраться от любого города до любого.

Чтобы доказать это, поместим какой-нибудь начальный город на уровень 0, соединённые с ним (будем называть их соседними) города  — на уровень 1, их оставшихся соседей  — на уровень 2, и так далее. Каждый раз на уровень k + 1 мы помещаем города, соседние с городами на уровне k, если им ранее не сопоставлен другой уровень. (Приведённый выше пример нарисован как раз по этому принципу).

Каждый город на уровне k может быть соединён только с городами на уровнях k − 1, k и k + 1.

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

Это означает, что у нас не может быть более

$2 плюс 2 плюс 92 умножить на дробь: числитель: 3, знаменатель: 4 конец дроби = 73$

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

Ответ: 72.

Решение · Помощь

Всего: 8 1–8