Тема Региональный этап ВсОШ и олимпиада им. Эйлера

Регион 9 класс → .04 Регион 2017

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

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

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

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

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

Разделы подтемы Регион 9 класс

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

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

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

Изначально на стол положили $100$ карточек, на каждой из которых записано по натуральному числу; при этом было ровно $43$ карточки с нечётными числами. Затем каждую минуту проводилась следующая процедура. Для каждых трёх карточек, лежащих на столе, вычислялось произведение записанных на них чисел, все эти произведения складывались, и полученное число записывалось на новую карточку, которая добавлялась к лежащим на столе. Через год после начала процесса выяснилось, что на столе есть карточка с числом, кратным $10000 2 .$ Докажите, что число, кратное $10000 2 ,$ было на одной из карточек уже через день после начала.

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

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

Если в некоторый момент среди чисел на карточках ровно $k$ нечётных, то среди произведений троек чисел ровно $C3 k$ нечётных; поэтому число на очередной добавляемой карточке будет нечётным ровно тогда, когда $3 C k$ нечётно (и тогда $k$ в эту минуту увеличится на $1$ ).

Заметим, что число $3 C43$ нечётно, а число $3 C44$ — чётно. Значит, в первую минуту добавится нечётное число, а дальше будут добавляться только чётные. Итак, после первой минуты среди чисел на карточках всегда будет ровно $44$ нечётных.

Рассмотрим числа на карточках после $n$ минут. Пусть $Tn$ — сумма всех произведений троек этих чисел, а $Dn$ — сумма всех произведений пар этих чисел. Число $Tn+1$ отличается от $Tn$ прибавлением всех произведений троек чисел, среди которых есть только что добавленное, то есть прибавлением $DnTn;$ итак, $Tn+1 =Tn +TnDn = Tn(1+ Dn).$ Заметим при этом, что $2 Dn ≡ C44 ≡ 0 (mod 2)$ при $n ≥1.$ Значит, при $n≥ 1$ число $1+Dn$ нечётно, и степень двойки, на которую делится $Tn+1,$ равно степени двойки, на которую делится $Tn.$

Итак, после первой минуты степень двойки, на которую делится добавляемое число $Tn,$ всегда равна степени двойки, на которую делится $T1.$ Значит, если бы после второй минуты на карточках не было числа, делящегося на $210000,$ то и впоследствии такого числа бы не появилось. Отсюда и следует требуемое.

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

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

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

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

Петя и Вася играют в следующую игру. Петя выбирает $100$ (не обязательно различных) неотрицательных чисел $x,x ,...,x , 1 2 100$ сумма которых равна $1.$ Вася разбивает их на $50$ пар по своему усмотрению, считает произведение чисел в каждой паре и выписывает на доску наибольшее из $50$ полученных произведений. Петя хочет, чтобы число на доске оказалось как можно больше, а Вася — чтобы оно было как можно меньше. Какое число окажется на доске при правильной игре?

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

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

Если Петя выберет числа $1,-1-, 1-,...,-1-, 2 198 198 198$ то, как бы ни разбивал эти числа Вася, в паре с числом $1 2$ будет число $-1. 198$ Их произведение будет равно $3196,$ а остальные будут не больше него. Тогда на доске окажется число $3196.$

Покажем, как Васе для любых Петиных чисел получить на доске число, не большее $-1-. 396$ Перенумеруем числа в порядке невозрастания: $x ≥ x ≥ ...≥ x . 1 2 100$ Разобьём числа на пары следующим образом: $x k$ в паре с $x . 101−k$ Тогда произведениями чисел в парах будут

x1x100,x2x99,x3x98,...,xkx101−k,...,x50x51

Покажем, что $a =x x ≤ 1-- k 101−k 396$ при $k≤ 49.$ Действительно, из неравенств $x ≤x ≤ ...≤ x1 k k−1$ следует, что $kx ≤x1+ x2+ ...+ x, k k$ поэтому

ka= kxk⋅x101−k ≤ (x1+x2+ ...+ xk)x101−k

Аналогично из неравенств $x101−k ≤ x100−k ≤ x99−k ≤...≤xk+1$ следует, что

(101− 2k)x101−k ≤ x101−k+ x100−k+ ...+ xk+1 ≤ ≤xk+1+ xk+2+...+x100 = 1− x1− x2− ...− xk

Поэтому

k(101− 2k)a ≤(x1+ x2 +...+ xk)(1 − x1− x2− ...− xk)= x(1− x)

где $x =x1 +x2+ ...+ xk.$ Поскольку по неравенству о средних для двух чисел $x(1− x) ≤( x+(12−-x))2 = 14,$ получаем неравенство $x x = a≤ ----1-----. k 101−k 4k(101− 2k)$ Осталось доказать, что $k(101− 2k)≥ 99$ при $k≤49.$ Это неравенство можно переписать в виде $(k− 1)(99− 2k)≥ 0,$ и обе скобки в последней формуле неотрицательны.