В Neverhood в лазерной установке надо было подобрать 5 цветов. Подсказка — слово, написанное на установке BOBBY — blue orange blue blue yellow. Нужно знать английский. А даже если и знаешь, то не факт, что догадаешься.
В 1877 году Э.Лукас доказал, что число 2^127-1 простое. Для этого понадобилось около ста часов вычислений… ручных.
«… Лукас сделал себе шахматную доску и записывал числа по линиям этой доски, расставляя ладьи на местах единиц и оставляя пустыми клетки нулей. Циклически есложения можно тогда осуществлять как „игру“, следуя нескольким простым правилам. Потребовалось примерно 100 часов такой игры, чтобы вычислить r_127 по модулю 2^127-1.»
При каких n существует перестановка p \in S_n (группа перестановок из n элементов), такая что p^2 = (1 2 ... n) (перестановка, состоящая из одного цикла длины n)?
Решение.
Считаем, что n>=2 (для n=1 задача тривиальна). Пусть q = (1 2 ... n). Очевидно, что q^n=1 и q^k != e, если k \in [1,n-1] (через e обозначена тождественная перестановка). Наше уравнение на p приобретает вид p^2 = q.
Т.к. степени перестановки q действуют на множестве {1,2,...,n} транзитивно, то и степени перестановки p тоже действуют на этом множестве транзитивно. Следовательно, перестановка q состоит из одного цикла длины n.
Предположим, что n нечетно. Тогда p = q^((n+1)/2) и p^2 = q^(2*(n+1)/2) = q^(n+1) = q. Явный вид для p = (1 1+n1 1+2*n1 ...), где n1=(n+1)/2.
Рассмотрим случай четного n. Тогда q^(n/2) = p^(2*n/2) = p^n = e и n/2 \in [1,n-1]. Противоречие.
Ответ: для нечетных положительных n.
Обобщение: условие "первый придворный из списка следит за тем, кто следит за тем, кто следит за вторым придворным из списка" записываеся уравнением p^3 = q. И вообще: решить уравение p^b=q, где q = (1 2 .. n). Решение существует для b взаимно простых с n.
Первый раз задачу увидел задачу в жж knop-а.
В 1877 году Э.Лукас доказал, что число 2^127-1 простое. Для этого понадобилось около ста часов вычислений… ручных.
«… Лукас сделал себе шахматную доску и записывал числа по линиям этой доски, расставляя ладьи на местах единиц и оставляя пустыми клетки нулей. Циклически есложения можно тогда осуществлять как „игру“, следуя нескольким простым правилам. Потребовалось примерно 100 часов такой игры, чтобы вычислить r_127 по модулю 2^127-1.»
http://www.mccme.ru/free-books/matpros/i5127139.pdf.zip
При каких n существует перестановка p \in S_n (группа перестановок из n элементов), такая что p^2 = (1 2 ... n) (перестановка, состоящая из одного цикла длины n)?
Решение.
Считаем, что n>=2 (для n=1 задача тривиальна). Пусть q = (1 2 ... n). Очевидно, что q^n=1 и q^k != e, если k \in [1,n-1] (через e обозначена тождественная перестановка). Наше уравнение на p приобретает вид p^2 = q.
Т.к. степени перестановки q действуют на множестве {1,2,...,n} транзитивно, то и степени перестановки p тоже действуют на этом множестве транзитивно. Следовательно, перестановка q состоит из одного цикла длины n.
Предположим, что n нечетно. Тогда p = q^((n+1)/2) и p^2 = q^(2*(n+1)/2) = q^(n+1) = q. Явный вид для p = (1 1+n1 1+2*n1 ...), где n1=(n+1)/2.
Рассмотрим случай четного n. Тогда q^(n/2) = p^(2*n/2) = p^n = e и n/2 \in [1,n-1]. Противоречие.
Ответ: для нечетных положительных n.
Обобщение: условие "первый придворный из списка следит за тем, кто следит за тем, кто следит за вторым придворным из списка" записываеся уравнением p^3 = q. И вообще: решить уравение p^b=q, где q = (1 2 .. n). Решение существует для b взаимно простых с n.