Ребят, не ждите тут каких-то выдающихся математических красот или полезных в жизни алгоритмов. Пишу просто из чистого спортивного интереса. Меня заинтересовала задачка опубликованная вот здесь, с которой американские зэки коротают свои огромные срока. Судя по комментариям к статье, она уже вызвала определённый интерес и у сообщества. Понимаю что поступаю не очень хорошо, надо было дать время народу ещё подумать самостоятельно. Однако каюсь, грешен, не могу удержаться. И выкладываю сюда своё решение. Кому интересно, добро пожаловать под кат. Если хотите ещё немного подумать самостоятельно, лучше пока не читайте.
Итак, сама задача. Сформулирую её чуть более понятно чем в самой статье (увы там перевод немного кривоват).
Циферблат (как на рисунке Figure 1) может указывать на любое целое число от 1 до n, если вращать его против часовой стрелки. Отсчёт начинается с 1, затем стрелка поворачивается последовательно (всегда против часовой стрелки) на одну позицию, затем на две, затем на три и так далее, до последнего поворота на n-1 позицию. Собираем последовательность всех чисел, на которые указывает стрелка.
Например, при n=12 получится последовательность 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Видно в ней есть повторяющиеся числа.
А для n=8, последовательность будет 1, 2, 4, 7, 3, 8, 6, 5. И в ней повторяющихся чисел нет.
Спрашивается, для каких значений n числа в последовательности не повторяются?
Представлено Гари Гордоном и Денизом Озбаем, ноябрьский выпуск журнала «Математические горизонты», 2020 год.
Назовём последовательность, которая строится в задаче последовательностью n-циферблата. А числа, n при которых эта последовательность не содержит повторяющихся чисел — подходящими.
Начнём с того, что получим очень серьёзную подсказку. Фактически сразу готовый ответ. По американским тюрьмам я не чалился, и не знаю, доступны ли тамошним сидельцам компы. Но у меня-то на столе стоит мой боевой конь! Так что грех не воспользоваться. Запускаем любимый jupyter notebook и вводим маленькую программку:
def getSeq(n): #Получает последовательность n-циферблата
lst=[]
s=1 # Начальное число
d=1 # Начальное приращение
for i in range(0, n):
lst.append(s)
s=(s+d) % n
if s==0:
s=n
d=d+1 #Приращение каждый раз увеличивается на 1
return lst
def testSeq(lst): #Проверяет список на неповторяемость
if len(set(lst)) == len(lst):
return True
return False
def getList(n): #Ищет подходящие числа, от 2 до n
lst=[]
for i in range(2, n):
if testSeq(getSeq(i)):
lst.append(i)
return lst
Запуск getList(12345) дает список 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Итого, очень похоже, что подходящими числами будут только степени двойки, и более никакие.
Остаётся только это доказать. Точнее доказать придётся два утверждения:
- Любая степень двойки является подходящим числом.
- Любое число, не являющееся степенью двойки, не является подходящим.
Сначала давайте разберемся, откуда вообще в последовательности n-циферблата берутся повторяющиеся числа.
Последовательность начинается с 1. Её приращение на первом шаге тоже равно 1, а затем с каждым шагом увеличивается на 1. В качестве результата берется остаток от деления на n. Причем если остаток равен нулю, то результат полагается равным n. Попробуем построить такую последовательность для какого-нибудь не очень большого числа n. Например n=6:
s(1) = 1 (mod 6) = 1
s(2) = 1+1 (mod 6) = 2
s(3) = 2+2 (mod 6) = 4
s(4) = 4+3 (mod 6) = 7 (mod 6) = 1
s(5) = 7+4 (mod 6) = 11 (mod 6) =1+4 (mod 6) = 5
s(6) = 11 + 5 (mod 6) = 16 (mod 6) = 5+5 (mod 6) = 4
Видим, что совпали две пары: s(1) и s(4), и s(3) и s(6). Причем если брать значения не по модулю, разность между бОльшим и меньшим элементами обеих пар кратна 6. Что в общем-то вполне понятно. Окончательное значение берётся по модулю n. И если до взятия модуля числа различаются на n (или кратное n), то окончательные значения совпадут.
С другой стороны, поскольку приращение у нас на каждом шаге увеличивается на 1. И понятно, что названные выше разности равны суммам каких-то последовательных чисел. Например для пары s(1), s(4):
7 = 1 + (1+2+3)
А для пары s(3), s(6):
16 = 4 + (3+4+5)
Для первой пары разность равна 6, для второй — 12.
Таким образом приходим к важному выводу:
Если в последовательности n-циферблата появились совпадающие числа, значит n или его кратное, представимо в виде суммы каких-то последовательных чисел, наибольшее из которых не превосходит числа n-1.
Сначала докажем вспомогательное утверждение:
Любое число не являющееся степенью двойки можно представить в виде суммы последовательных чисел. Никакую степень двойки суммой последовательных чисел представить нельзя.
Подумаем, как вообще представить какое-то число в виде суммы последовательных чисел. Для нечетных это совсем просто. Если A нечётное, то его можно представить парой:
A = [A/2] + ([A/2] + 1), где [ ] означает целую часть числа.
Например 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
Просто это и для кратных 3. Если A кратно 3, то:
A = (A/3 — 1) + A/3 + (A/3 + 1).
Аналогично и если A кратно 5:
A = (A/5 — 2) + (A/5 — 1) + A/5 + (A/5 + 1) + (A/5 + 2).
И вообще, если число A имеет нечётный делитель B, оно представимо в виде суммы B последовательных чисел, причем число A/B стоит ровно посередине.
Примеры:
27 = 3*9. Отсюда 27 = (9-1) + 9 + (9+1) = 8 + 9 + 10.
50 = 5*10. Отсюда 50 = (10-2) + (10-1) +10 + (10+1) + (10+2) = 8 + 9 + 10 + 11 + 12.
Очевидно и обратное. Если число представимо в виде суммы нечетного количества последовательных чисел, то оно имеет нечетный делитель, а само представление имеет вид, описанный выше. Следовательно степень двойки не может быть суммой нечётного количества последовательных чисел, ибо не имеет нечётных делителей.
Ну а что суммы четного количества последовательных чисел? Сумма двух последовательных чисел всегда нечетна. Это надеюсь очевидно. Сумму четырех можно представить как сумму двух пар, каждая из которых нечетна. А значит сумма четырех четна. Сумма шести опять нечетна, сумма восьми четна, и т.д. Т.е. сумма четного количества последовательных чисел четна, если их количество кратно 4, и нечетна, если кратно только 2.
Пусть четное число A представлено суммой 4*k последовательных чисел. Для простоты пусть k=1, для бОльших k рассуждения совершенно аналогичны:
A = a + (a+1) + (a+2) + (a+3) = 4*a + 6.
Разделим это равенство на 2:
A/2 = (4*a + 6)/2 = 2*a + 3 = (a + 1) + (a + 2).
Т.е. опять получаем сумму последовательных чисел.
Следовательно, если для четного числа A существует представление в виде суммы четного количества последовательных чисел, то какое-то представление в виде суммы последовательных чисел существует и для A/2.
Например:
26 = 5 + 6 + 7 + 8. Отсюда 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Пусть для N-й степени двойки существует представление в виде суммы четного количества последовательных чисел (представления в виде нечетного количества для нее не существует как показано выше). Тогда представление в виде суммы последовательных чисел есть и для степени N-1. И количество слагаемых в нем тоже четно. По индукции, то же самое можно сказать и о степени N-2, и о степени N-3 и вообще о любой степени меньшей N. Но представления в виде суммы последовательных чисел для числа 4 не существует, в чём легко убедиться. Следовательно никакая степень двойки не представима в виде суммы последовательных чисел.
Замечание. По обсуждению в комментариях добавил гораздо более простое и понятное доказательство того, что любая степень двойки не представима в виде суммы последовательных чисел.
Сумма первых n чисел натурального ряда равна s(n) = n*(n + 1)/2.
Следовательно любые частичные суммы равны:
s(m, n) = ((m*(m+1) — n*(n+1))/2.
Преобразуем это выражение:
s(m, n) = (m^2 + m — n^2 — n)/2=((m-n)*(m+n) + (m-n))/2=(m-n)*(m+n+1)/2.
Поскольку речь идёт о степенях двойки, множитель 1/2 можно отбросить.
Речь идёт о равенстве степени двойки выражения (m-n)*(m+n+1).
Но как легко заметить, четность двух сомножителей разная. И оба они одновременно никак не могут быть четными. А значит любая такая сумма обязательно содержит какой-то нечетный делитель. И потому не может быть равна никакой степени двойки.
С другой стороны, любое число, не являющееся степенью двойки, можно представить в виде суммы последовательных чисел. Если это число нечетное, его можно представить в виде пары. Если четное и не является степенью двойки, значит оно имеет хотя бы один нечётный делитель. И представимо через него.
Вспомогательное утверждение доказано.
Рассмотрим всю последовательность n-циферблата.
s(1) = 1 (mod n)
s(2) = 1 + 1 (mod n)
s(3) = 2 + 2 (mod n)
s(4) = 4 + 3 (mod n)
…
s(n) = s(n-1) + n-1 (mod n)
Пусть n является степенью двойки. Тогда 2*n, 4*n, 8*n и т.д, тоже являются степенями двойки. И в виде суммы последовательных чисел непредставимы. Представимы 3*n, 5*n, 6*n, 7*n, 9*n и т.д. Т.е. у числа m*n должен быть хотя бы один нечетный делитель. Однако даже наименьшее из этих кратных, 3*n, должно быть представлено как
(n — 1) + n + (n + 1).
Других представлений числа 3*n нет. Ибо n как степень двойки вообще не имеет представлений(см. вспомогательное утверждение). Но слагаемые в этой сумме не должны превосходить числа n — 1. Следовательно 3*n в качестве разности никогда не появится. Для прочих кратных рассуждения совершенно аналогичны. Разумеется ни n ни 2*n в качестве разностей тоже не появятся никогда, как степени двойки. А значит любая степень двойки является подходящим числом.
Утверждение (1) доказано.
Пусть теперь n не является степенью двойки. Т.е. представимо в виде суммы последовательных чисел. Разность между первым и последним членом последовательности (до взятия модуля по n) будет:
d = 1 + 2 + 3 +… + (n-1).
А разности между членами последовательности n-циферблата (до взятия модуля) будут любыми частичными суммами этого ряда. Если n представимо в виде суммы последовательных чисел, то наибольшие возможные числа, составляющие такую сумму, это
[n/2] и [n/2] + 1. ([ ] — целая часть числа)
Все прочие варианты такой суммы обходятся числами ещё меньшими. А значит члены последовательности n-циферблата, с разностью до взятия модуля равной n обязательно найдутся. И после взятия модуля дадут совпадающие числа. Т.е. любое n не являющееся степенью двойки, а значит представимое в виде суммы последовательных чисел, не является подходящим числом.
Утверждение (2) доказано.
Итого, задача полностью решена. Подходящими числами будут любые степени двойки и никакие другие. На свободу с чистой совестью!!!
Мораль сей басни пожалуй только одна. Парни, даже если вы занимаетесь чистой математикой, не пренебрегайте вычислительными экспериментами. Да, такие эксперименты ничего не доказывают. Однако могут дать вполне обоснованную догадку. Хотя может и не столь простую как здесь. А доказывать уже как правило значительно легче чем догадываться. Буду рад, если кому-то это изложение показалось полезным и интересным.
