Loading [Contrib]/a11y/accessibility-menu.js
ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79286
Темы:    [ Последовательности (прочее) ]
[ Принцип крайнего (прочее) ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Лифшиц А.

Существует ли такая последовательность натуральных чисел, чтобы любое натуральное число $1$, $2$, $3$, ... можно было представить единственным способом в виде разности двух чисел этой последовательности?

Решение

Будем строить последовательность, начав с двух чисел с разностью $1$ (например, с чисел $1$ и $2$) и добавляя по два числа.

Предположим, что мы построили конечную последовательность, обладающую следующими свойствами:

  1. все попарные разности между членами этой последовательности различны;
  2. числа $1$, $2$, ..., $k$ можно представить в виде разности двух её членов.
  3. число $k + 1$ нельзя представить в виде разности двух её членов.
Пусть максимальный член этой последовательности равен $M$. Добавим теперь к последовательности числа $2M+1$ и $2M+k+2$. Покажем, что последовательность с двумя добавленными членами всё ещё удовлетворяет свойствам 1 и 2.

Заметим, что каждое новое добавленное число больше всех предыдущих, поэтому строящаяся последовательность возрастает. Это значит, что наибольшая разность среди «старых» чисел была меньше $M$, и при этом разность любого из двух новых чисел и любого из старых не меньше $M+1$. Разность двух новых чисел равна $k+1$ и по построению ещё не встречалась; если же оказались равными разности новых чисел и старых, то разность этих старых равна разности новых, то есть $k+1$ – но по предположению $k+1$ нельзя представить как разность старых чисел. Значит, все разности в дополненной последовательности также различны, а первая не реализуемая разность увеличилась по крайней мере на $1$.

Таким образом, применяя такое «дописывание», получим бесконечную последовательность, удовлетворяющую условиям задачи.

Ответ

Существует.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 9
Тур 2
задача
Номер 1
олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 10
Тур 2
задача
Номер 1
журнал
Название "Квант"
год
Год 1974
выпуск
Номер 10
Задача
Номер М287

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .