На доске написано несколько чисел Фибоначчи. Разность любых двух из них содержит только цифры 2, 3, 6, 9 (не обязательно все эти цифры). Какое наибольшее количество чисел может быть на доске?

задан 28 Июн '14 11:18

изменен 28 Июн '14 16:21

falcao's gravatar image


259k23750

@Сардаана, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(1 Июл '14 21:54) Deleted
10|600 символов нужно символов осталось
2

Полного решения я пока не знаю, но изложу те соображения, которые есть. Может, их кто-нибудь разовьёт.

Пример из четырёх чисел легко строится: 2, 5, 8, 34. Можно также показать, что шесть чисел указать нельзя. А именно, рассмотрим пять чисел $%a < b < c < d < e$%, и посмотрим на последние цифры разностей $%b-a$%, $%c-b$%, $%d-c$%, $%e-d$%. Утверждается, что это могут быть только тройки. В самом деле, цифра 2 в сумме с любой из допустимых цифр даёт ту, которая встретиться не может. Цифра 9 может соседствовать только с 3, но тогда вместе они дают 2, и больше уже ничего не добавить. Остаются цифры 3 и 6, и здесь 6+6 даёт на конце 2, а 3+6 даёт 9, что уже было исследовано выше. Поэтому четыре допустимых разности могут возникнуть только с тройкой на конце. И тогда к ним больше уже ничего не добавить (в сумме будет 2 на конце).

Пример из пяти чисел мне не известен, но и опровергнуть его существование я пока что не умею.

ссылка

отвечен 28 Июн '14 16:21

Доказаательство невозможности шести горааздо проще. По принципу Дирихле из шести чисел хотя бы два дают одинааковый остааток при делении на 5, а это каак рааз и означаает, что их раазность окаанчивается либо на 5, либо на 0. :)

(29 Июн '14 2:36) Сардаана

Да, это правда. Но здесь есть смысл проанализировать, как могли бы быть расположены пять чисел -- если задаваться целью доказать невозможность такого примера. Тогда анализ и описание этого случая могли бы как-то пригодиться. Но я полного решения, так или иначе, не знаю.

(29 Июн '14 2:41) falcao

Но рассуждения с остатками от деления можно продолжить. Из пяти чисел хотя бы два дают одинаковый остаток при делении на $%4$%, тогда их разность делится на $%4$%, а значит, может оканчиваться только на $%32$%, $%36$%, $%92$% и $%96$%. Для определенности будем считать, что эти числа $%a$% и $%b$%, $%a<b$%.

Далее для произвольного $%x$% из этого набора $%b-x=(b-a)+(a-x)$%, а $%a-x$% содержит только цифры из условия. Чтобы $%b-x$% оканчивалось на цифры из условия необходимо, чтобы $%a-x$% оканчивалось на $%3$% или $%6$%, а $%b-a$% - на $%6$% (т.е. $%36$% или $%96$%).

(29 Июн '14 15:29) cartesius

Получается, мы имеем, что $%a-x$%, для любого $%x$% из этого набора оканчивается на $%3$% или $%6$%. Но тогда найдутся такие $%a-x$% и $%a-y$%, что $%x-y=(a-y)-(a-x)$% оканчивается нулем. Что противоречит условию.

Здесь я не обращаю внимания на знаки (какое из чисел больше при вычитании), но вроде бы это несущественно.

(29 Июн '14 15:34) cartesius

@cartesius: здесь главный момент -- как использовать ограничение, что это числа Фибоначчи. Если брать просто числа, то примеров много -- скажем, 2, 5, 8, 31, 34. В этом случае почему бы не найтись числам Фибоначчи вида 33...301 и 666...634?

(29 Июн '14 15:49) falcao

Нет, все-таки знаки тоже надо учитывать.

(29 Июн '14 16:10) cartesius

@cartesius: в каком смысле знаки надо учитывать?

(29 Июн '14 17:03) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,129
×258
×42

задан
28 Июн '14 11:18

показан
1549 раз

обновлен
1 Июл '14 21:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru