|
На доске написано несколько чисел Фибоначчи. Разность любых двух из них содержит только цифры 2, 3, 6, 9 (не обязательно все эти цифры). Какое наибольшее количество чисел может быть на доске? задан 28 Июн '14 11:18 
Сардаана |
|
Полного решения я пока не знаю, но изложу те соображения, которые есть. Может, их кто-нибудь разовьёт. Пример из четырёх чисел легко строится: 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 
falcao Доказаательство невозможности шести горааздо проще. По принципу Дирихле из шести чисел хотя бы два дают одинааковый остааток при делении на 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
|
@Сардаана, Если вы получили исчерпывающий ответ, отметьте его как принятый.