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

Поиск
?

Всего: 2 1–2

Добавить в вариант

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

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

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Доказано, что в М не больше 7 элементов.	5
Пример для 7 элементов.	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

Рассмотрим девять чисел k₁, ..., k₉, где $k_i принадлежит левая фигурная скобка 0, 1, 2 правая фигурная скобка .$ При этом хотя бы одно число k_i отлично от нуля. С помощью этих чисел вырабатывают последовательность u₁, u₂, ..., u₂₀₁₉ по формулам:

$u_1=k_1,$ $u_2=k_2,$ $\ldots,$ $u_9=k_9,$ $u_i плюс 9=r_3 левая круглая скобка u_i плюс u_i плюс 1 правая круглая скобка ,$ $i=1, 2, \ldots, 2010,$

где r₃(a)  — остаток от деления числа a на 3. Найдите такое наименьшее натуральное число l, что какие бы исходные числа k₁, ..., k₉ мы ни взяли, в последовательности u₁, u₂, ..., u_l каждое из чисел 0, 1 и 2 гарантированно встретится хотя бы один раз.

Решение.

Для каждого набора $k= левая круглая скобка k_1, \ldots, k_9 правая круглая скобка$ укажем такое минимальное l, что в соответствующей последовательности u₁, u₂, ..., u_l присутствует каждое из чисел 0, 1 и 2. Затем среди всех таких l останется выбрать наибольшее  — это и будет ответом в задаче.

1.  В наборе k встречается каждое из чисел 0, 1 и 2. Тогда искомое l не превосходит 9.

2.  Набор k состоит только из 1. Тогда $u_10= умножить на s=u_17=2$ и $u_18=0.$ Значит, $l=18.$

3.  В наборе k присутствуют и 1, и 2, но нет 0. Значит, среди чисел u₁, u₂, ..., u₉ есть два соседних (u_s и u_s + 1), одно из которых равно 1, а другое 2. Тогда $u_s плюс 9=0$ и $l меньше или равно 17.$

4.  Набор k состоит из 0 и 1. Число 2 впоследствии дадут только две рядом стоящие 1. Поэтому рассмотрим варианты:

а) в k есть рядом стоящие 1. Тогда $l меньше 19;$

б) в k нет рядом стоящих 1. Здесь возможны следующие случаи:

— есть хоть одна единица «не с краю». То есть найдется номер s такой, что $2 меньше или равно s меньше или равно 8$ и $k_s=1.$ Рядом стоящих единиц нет, поэтому $k_s минус 1=k_s плюс 1=0.$ Тогда $u_s плюс 8=u_s плюс 9=1.$ Следовательно, $u_s плюс 17=2$ и $l меньше или равно 25;$

— единица есть только «с краю». Пусть $k= левая круглая скобка 1, 0, \ldots, 0 правая круглая скобка .$ В этом случае начало последовательности u₁, u₂, ... можно вычислить непосредственно:

$левая фигурная скобка u_n правая фигурная скобка = левая фигурная скобка 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, \ldots правая фигурная скобка$

и убедиться, что $l=27.$ Пусть $k= левая круглая скобка 1, 0, \ldots 0, 1 правая круглая скобка .$ Тогда

$левая фигурная скобка u_n правая фигурная скобка = левая фигурная скобка 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0 \ldots правая фигурная скобка$

и $l=18 .$ И, наконец, для $k= левая круглая скобка 0, \ldots 0, 1 правая круглая скобка$ находим

$левая фигурная скобка u_n правая фигурная скобка = левая фигурная скобка 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, \ldots правая фигурная скобка$

и $l=26.$

Отметим, что случаи, «k состоит только из 2» и «k состоит только из 0 и 2» эквивалентны случаям 2 и 4 соответственно. Действительно, если в последовательности {u_n}, отвечающей набору $2 умножить на k,$ заменить все 2 на 1, а 1 на 2, то получится последовательность, соответствующая набору k.

Ответ: $l=27 .$

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

Всего: 2 1–2