Архив задач олимпиады по математике и криптографии

Подбор пароля

Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите {a,b,c}. Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор P в набор Q=j(P). Отображение j держится в секрете, однако про него известно, что оно определено не для каждого набора букв и обладает следующими свойствами. Для любого набора букв P
1) j(aP)=P;
2) j(bP) = j(P)aj(P);
3) набор j(cP) получается из набора j(P) выписыванием букв в обратном порядке.
Устройство признает предъявленный пароль верным, если j(P)=P. Например, трехбуквенный набор bab является верным паролем, так как j(bab) = j(ab)aj(ab)=bab. Подберите верный пароль, состоящий более чем из трех букв.

  • Решение

    • Решение

    Обозначим [j(P)] - набор j(P) , выписанный в обратном порядке.

    j(cbcacbc)=[j(bcacbc)] = [j(cacbc)aj(cacbc)] = [[j(acbc)]a[j(acbc)]] = [[cbc]a[cbc]]=[cbcacbc]=cbcacbc.
    В общем случае можно показать, что множество искомых наборов состоит из слов вида:
    P= м
    п
    н
    п
    о
    cb

    c... c
    k раз 
    		 acb

    c... c
    k раз 
    k - нечетное;
    b

    c... c
    k раз 
    		 ab

    c... c
    kраз 
    k - четное.
  • Ответ

    • Ответ

    например, cbcacbc.