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

Регион 10 класс → .05 Регион 2018

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

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

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

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

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

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

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

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

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

Петя и Вася по очереди выписывают на доску натуральные числа, не превосходящие $2018$ (выписывать уже имеющееся число запрещено); начинает Петя. Если после хода игрока на доске оказываются три числа, образующих арифметическую прогрессию, этот игрок выигрывает. У кого из игроков есть стратегия, позволяющая ему гарантированно выиграть?

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

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

Подсказка 1:

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

Подсказка 2:

Скорее всего, вы поняли, что если выписано 3 числа и игра ещё не завершилась, то четвёртым ходом Вася её завершит своей победой. Если нет, то покажите, почему это так.

Подсказка 3:

Осталось понять, как сделать так, чтобы Петя не победил третьим ходом. Пусть первым было выписано число a, а вторым — b. Нужно подобрать такое b, чтобы a и b не могли быть соседними членами целочисленной прогрессии, а также не могли быть первым и третьим членами.

Подсказка 4:

Чтобы они не были соседними, можно взять достаточно большое b. Чтобы они не оказались первым и третьим, подумайте о чётности.

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

Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Вася выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).

Кроме того, заметим, что если три целых числа из множества $1,2,3,...,2018$ образуют арифметическую прогрессию, то её разность не больше $1008$ (иначе разность между наибольшим и наименьшим числами будет не менее $2⋅1009= 2018,$ что невозможно).

Теперь опишем выигрышную стратегию Васи.

Пусть первым ходом Петя выписал число $a$ . Предположим, что $a≤ 1009.$ Тогда Вася выписывает то из чисел $2017$ или $2018$ , чётность которого отлична от чётности числа $a$ (обозначим это число через $b$ ). После этого хода выписано два числа разной чётности; значит, они не могут быть первым и третьим членом прогрессии из целых чисел. А поскольку $b− a> 1009,$ они также не могут быть соседними членами прогрессии. Тем самым, Петя не сможет выиграть третьим ходом. Но в этом случае, как мы видели ранее, следующим ходом Вася выиграет.

Если же $a >1010,$ то Вася отвечает, выписывая то из чисел $1$ и $2,$ которое по чётности отличается от $a.$ Дальнейшие рассуждения аналогичны первому случаю.

Ответ:

У Васи

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

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

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

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

Дана клетчатая доска $1000×1000.$ Фигура гепард из произвольной клетки $x$ бьёт все клетки квадрата $19 ×19$ с центральной клеткой $x,$ за исключением клеток, находящихся с $x$ в одном столбце или одной строке. Какое наибольшее количество гепардов, не бьющих друг друга, можно расставить на доске?

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Да, такого не может произойти, так как в таком случае они будут бить друг друга, даже если будут стоять на одной вертикали и горизонтали с исходным. Значит, всех гепардов в квадрате 10 на 10 мы ставим в один ряд, откуда их не более 10. Остался пример. Так как мы всю задачу как-то работали с числом 10, то как лучше всего их расположить в таком случае?

Подсказка 4

Верно, мы можем расположить их в один столбец с интервалом в 10 клеток. Тогда несложно увидеть, что всё сработает. Победа!

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

Разобьём доску на $1002$ квадратов $10× 10.$ Покажем, что в каждом квадрате может стоять не более $10$ гепардов, не бьющих друг друга — отсюда будет следовать, что общее число гепардов не может превосходить $2 100 ⋅10= 100000.$

Рассмотрим произвольный квадрат $Q$ размера $10×10$ и произвольного гепарда $g$ в нём. Гепард $g$ бьёт все клетки квадрата, кроме клеток, лежащих с ним в одной строке или в одном столбце. Если один из остальных гепардов $′ g$ в квадрате $Q$ стоит в одной строке с $g,$ а ещё один, $′′ g ,$ — в одном столбце с $g,$ то $′ g$ и $′′ g$ стоят в разных строках и столбцах и, следовательно, бьют друг друга; это невозможно. В противном случае, без ограничения общности, все гепарды в квадрате $Q$ стоят в одной строке с $g,$ то есть их не больше $10.$

Таким образом, мы доказали, что общее число гепардов не может превосходить $100000;$ осталось привести пример, когда эта оценка достигается. Пронумеруем столбцы доски подряд числами $1,2,...,1000.$ Расставим гепардов на все клетки столбцов, номера которых делятся на $10.$ Этих гепардов будет $1000⋅100= 100000,$ и они не будут бить друг друга.