Тема Заключительный этап ВсОШ

Закл (финал) 10 класс → .04 Закл 2017

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

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

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

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

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 10 класс

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

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

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

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

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

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

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

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

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

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

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

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

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

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

( ) 2(n−1)+(n−2)+...+0⋅an1an2 ...ann = 2(n−1)∕2a1a2...an n

Следовательно, произведение чисел хотя бы в одной из последовательностей не превосходит $2(n−1)∕2a1a2...an,$ что и требовалось.

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

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

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

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

Изначально на столе лежат три кучки из 100,101 и 102 камней соответственно. Илья и Костя играют в следующую игру. За один ход каждый из них может взять себе один камень из любой кучи, кроме той, из которой он брал камень на своем предыдущем ходе (на своём первом ходе каждый игрок может брать камень из любой кучки). Ходы игроки делают по очереди, начинает Илья. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?

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

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

Пусть Илья возьмет камень из кучки 101. Тогда если Костя возьмет камень из другой кучи, то Илья сможет просто брать камень с той же кучи, что и Костя. Почему? Если у Кости был ход (рассматриваем уже хотя бы второй Костин ход, так как с первыми ходами все работает), значит, на своем предыдущем ходе Костя брал камень из другой кучи, но Илья брал камень из той же кучи, поэтому сейчас он тоже может взять камень, откуда его взял Костя. Таким образом, в этом случае после хода Ильи во всех трех кучках камней четно, а значит, Костя проиграет.

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

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

Таким образом, выигрывает Илья.

Ответ: Илья

Курсы

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

Интенсивы

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

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

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