ВсОШ 2024, 9, 10 классы, задача 4

Средняя
Комбинаторика
Источник:
Всероссийская олимпиада школьников, Региональный (9–11 классы), 2024, 9 класс, Первый турВсероссийская олимпиада школьников, Региональный (9–11 классы), 2024, 10 класс, Первый тур

( баллов) В ряд выписаны по одному разу все натуральные числа от до в каком-то порядке. Докажите, что можно выбрать несколько стоящих подряд выписанных чисел, сумма которых больше , но не превосходит .

(С. Берлов)

Ответ

Решение. Сумма всех чисел ряда, кроме числа , равна , поэтому сумма чисел с какой-то из сторон от числа больше , пусть для определённости справа.

Пусть справа от стоят (слева направо) числа . Обозначим ; выберем наименьшее , для которого , так что . Если , то мы уже нашли желаемую группу чисел.

Пусть теперь . Докажем, что тогда нам подходит сумма . Действительно, поскольку , имеем . С другой стороны, , что и требовалось.

1

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

0
2

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

-1, -2 или -3
Максимум: 7

Похожие задачи

ВсОШ 2022, 10 класс, задача 3

У Васи есть n конфет нескольких сортов, где nge145. Известно, что если из данных n конфет выбрать любую группу, содержащую не менее 145 конфет (в частности, можно выбрать группу из всех данных n конфет), то существует такой сорт конфет, что выбранная группа содержит в точности 10 конфет этого сорта.
Средняя
Комбинаторика

ВсОШ 2023, 10 класс, задача 1

(7 баллов) В таблице 6 × 6 изначально записаны нули. За одну операцию можно выбрать одну клетку и заменить число, стоящее в ней, на любое целое число. Можно ли за 8 операций получить таблицу, в которой все 12 сумм чисел в строках и столбцах будут различными положительными числами? (А. Кузнецов, П. К
Средняя
Комбинаторика

ВсОШ 2023, 9 класс, задача 7

(7 баллов) На доску записали 99 чисел, среди которых нет равных. В тетрадку выписали dfrac{99 · 98}{2} чисел — все разности двух чисел с доски (каждый раз из большего числа вычитали меньшее). Оказалось, что в тетрадке число 1 записано ровно 85 раз. Пусть d — наибольшее число, записанное в тетрадке.
Средняя
Комбинаторика

ВсОШ 2024, 9, 10, 11 классы, задача 1

(7 баллов) У Олега есть набор из 2024 различных клетчатых прямоугольников размеров 1 × 1, 1 × 2, 1 × 3, ldots, 1 × 2024 (по одному прямоугольнику каждого размера). Может ли он, выбрав некоторые из них, составить какой-нибудь клетчатый квадрат площади больше 1? (О. Подлипский)
Средняя
Комбинаторика