| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Задача о греческом алфавите http://mathhelpplanet.com/viewtopic.php?f=54&t=84168 |
Страница 2 из 2 |
| Автор: | Booker48 [ Вчера, 23:08 ] |
| Заголовок сообщения: | Re: Задача о греческом алфавите |
По последовательности Фибоначчи (ПФ) какие претензии? Только одна - такая последовательность (если она не содержит сразу 10 чисел, все парные суммы которых различны - а ПФ именно такова) оставляет открытым вопрос - а вдруг такая последовательность ("меньшая", чем ПФ) всё же существует на заданном отрезке? 10 первых членов ПФ, не содержащая двух одинаковых попарных сумм по условию - та, начало которой привёл Захар: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Т.е., если алфавит состоит из 89 букв, то 10 букв с указанными индексами являют собой контрпример к вопросу задачи: "Обязательно ли найдутся такие четыре различные буквы, что сумма алфавитных номеров первой и второй из них окажется равной сумме алфавитных номеров третьей и четвёртой?". Ответ - необязательно. Пример выше. Но если букв меньше, например 81? Можно взять 9 первых членов ПФ, но ниоткуда не следует, что добавление к ней ещё одного члена приведёт к тому, что все возможные попарные суммы не будут уникальными. И потом - что мы прицепились к ПФ? А если последовательность другая? И - опаньки! - оказывается такая ПФ есть! В OEIS! Как в Греции! Внезапно выясняется, что какие-то Абдул Маджид Миан и Сарвадаман Чоула аж в 1944 году опубликовали статью про некую последовательность (ПМЧ), которая в OEIS содержится под номером A005282. Это специально сконструированная последовательность, в которой [math]a_1=1[/math], а [math]a_{n+1}[/math] - есть минимальное натуральное число, большее чем [math]a_n[/math] такое, что все суммы [math]a_i+a_j, i,j \leqslant n[/math] - различны. И первые 10 членов ПМЧ: 1, 2, 4, 8, 13, 21, 31, 45, 66, 81. Она начинает быть "меньшей", чем ПФ как раз с 10-го члена. Но дальше растёт медленнее, чем ПФ. Я без понятия, почему они решили, что эта последовательность "минимальная". Но по самому способу построения понятно, что таких последовательностей много. И то, что нет таких последовательностей для, например, алфавита из 33 букв - надо доказывать. Или перебрать все возможные 10-буквенные комбинации из 33 букв и убедиться, что нет таких, в которых все возможные попарные суммы уникальны. Их всего-то 92561040. |
|
| Страница 2 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|