Теория чисел на Звезде —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на Звезде

Тема Звезда (только задачи по математике)

Теория чисел на Звезде

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

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

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

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

Подтемы раздела звезда (только задачи по математике)

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

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

Задача 1#75750

В бесконечной последовательности цифр $2,0,1,9,...$ каждая цифра, начиная с пятой, равна последней цифре суммы предшествующих четырёх цифр этой последовательности. Встретятся ли в этой последовательности:

(a) подряд числа $4,3,2,1$ ;

(b) вторично четвёрка $2,0,1,9$ (в этом же порядке)?

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

Пункт а, подсказка 1

Т.к. нам дана последовательность и мы хотим показать, бывает что-то или нет, попробуем найти полуинвариант (то, что нечасто меняется в последовательности в процессе добавления новых элементов).

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

a) Последовательность начинается с $2,0,1,9,...$ , рассмотрим остатки цифр при делении на два. Так как каждая цифра, начиная с $5$ -ой, равна последней цифре суммы $4$ предыдущих (т. е. она той же четности, что и сумма $4$ предыдущих), то остатки изменяются следующим образом $0,0,1,1,0,0,0,1,1,0,...$ . Так как цифра определяется однозначно по $4$ предыдущим, то заметим, что в последовательности остатков возникает период $(0,0,1,1,0)$ .

Но тогда подряд числа $4,3,2,1$ не могли встретиться, их остатки при делении на $2$ равны $0,1,0,1$ соответственно, а такой подпоследовательности нет в периодической последовательности остатков с периодом $(0,0,1,1,0)$ .

b) Различных четверок подряд идущих цифр конечное число, при этом цифра определяется однозначно по $4$ предыдущим. Тогда исходная последовательность цифр периодична.

Также по четырём рядом стоящим цифрам $abcd$ однозначно определяется предшествующая им цифра: это единственная цифра, сравнимая по модулю $10$ с $-- -- d,a,b,c.$ Тогда у последовательности нет предпериода, иначе бы предпериод $x1,x2,...,xm$ - совпадал с несколькими последними цифрами периода $y1,y2,...,yn$ , но тогда просто был неправильно выбран период, нужно было взять период $x1,x2,...,xm,y1,y2,...,yn−m$ и тогда не было бы предпериода.

Ответ:

a) нет

b) да

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

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

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

Задача 2#49163

По кругу записаны $2019$ чисел. Для любых двух соседних чисел $x$ и $y$ выполняются неравенства $|x− y|≥ 2,x +y ≥6$ . Найдите наименьшую возможную сумму записанных чисел.

Источники: Звезда - 2019 (см. zv.susu.ru)

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

Подсказка 1

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

Подсказка 2

Верно, можно было просто оценить по парам. А как нам оценить нечетное кол-во чисел? Думается, сначала как-то выделить подгруппу нечетного кол-ва чисел, а потом , также как с четными кол-вом до этого, оценить. Но сколько надо взять чисел на оценку? Одно, кажется, вообще непонятно как оценивать. А вот три?

Подсказка 3

Скажем, если бы нашлись три подряд идущих числа x,y,z : x>=y>=z , то что бы это дало? Как бы мы могли оценить такую тройку чисел?

Подсказка 4

Да, мы могли бы сказать, что y-z>=2 , y+z>=6 => y>=4. Однако, так же можно оценить x>=y+2>=6 , но при этом y+z>=6, значит x+y+z>=12. То есть, сумма чисел в этой тройке хотя бы 12. И также, мы можем оценить по парам остальные числа(которых четное кол-во). Но остается один вопрос, а правда, что найдутся три таких подряд идущих числа, что x>=y>=z?

Подсказка 5

Да, это правда, в силу нечетности кол-ва чисел(если у вас сходу не нашлось такой пары, это значит, что числа как бы чередуются : сначала большое, потом маленькое, большое, маленькое и тд. Но вот это чередование(так как числа по кругу) оно рано или поздно сойдется и на стыке нельзя будет чередовать, если чисел нечетное кол-во). Значит, оценка есть, осталось привести пример(который строится по этой оценке).

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

Всего чисел нечётное количество, поэтому найдутся такие три подряд идущих числа $x,y,z$ , что $x ≥y ≥z$ . Тогда $y− z ≥ 2,y+ z ≥ 6$ , откуда $y ≥ 4$ . Отсюда $x≥ y+ 2≥ 6$ , то есть хотя бы одно из чисел не меньше $6$ . Остальные разбиваем на пары (в каждой паре сумма не меньше $6$ ) и получаем, что сумма чисел по всему кругу не меньше $6+1009⋅6= 6060$ .