Задача о принцессах, гематрия и хеш-суммирование

Из поста Задача по арифметике   
Было у короля 56 наследных принцев. Красавцы, как на подбор, брюнеты, блондины и лысые.
Стал король им невест подбирать. Со всех концов необъятной Хамсинезии потянулись во дворец претендентки, одна другой родовитее, да пригожее. А всё не то, да не то, возвращались ни с чем.
Прознали девушки в одной деревне, как кастинг проходит: обряжают будущих принцесс в чадру и колонной по одному выводят на торжественный смотр. Каждую берет под руку принц, так и стоят, пара за парой. Стоять приличествует не шелохнувшись, чадра плотная, сеточка узенькая - впереди стоящих видно (всех, по ступеням нисходят), а принца рядом - нет; сдвигать покрывало - нельзя по протоколу, невежу выдворят с позором.
Ученый джин опрашивает испытуемых одну за другой, начиная с задних рядов - какой масти принц с ней рядом. Блондин, брюнет или лысый. Отвечать одним словом, ровным тоном. Угадавшей разрешают лицо открыть. Если все назовут правильно - тогда и пир горой и свадьбы играть. А если больше трех ошибутся, то всем на выход, не солоно хлебавши.
Засобирались девицы во дворец, а с одной младшая сестра набивается: - Мала ты еще, куда тебе замуж? - А возьмите, я вам пригожусь!
Поехали, а на другой день во дворце уже готовили 55 свадеб.
Только самая младшая не прошла испытания. Зато подругам помогла. Как?

Идя встречу пожеланиям юношев нетерпеливых "Нам текстов не надо, ответы давай!",
начнем с краткого и строгого решения в общем виде:

Пусть имеются m участниц испытания и k возможных цветов шевелюры. Припишем этим цветам значения от 0 до k-1.Коллектив принцесс договорился о подсказке: последняя в цепочке участница, отвечая джину, называет закодированную цветом контрольную сумму S, полученную путем сложения по модулю k всех числовых значений, соответствующих впереди-наблюдаемым шевелюрам. В свою очередь каждая n-ая испытуемая вычитает из S по модулю k озвученные значения, как и те, что видит впереди себя.
Это он, ответ.

Тех же, кому любопытно - А можно то же самое по-китайски? с рассказами и пояснениями - приглашаем под кат.

Начинающая хамсинезийская принцесса, искушенная в гематрии, нотариконе и прочих забавах с последовательностями чисел, с большей легкостью увидит подход к описанной ситуации, чем наш современник, с первых шагов приученный к мышлению "в общем виде", с переменными (чуть-чуть повозившись с решением "по действиям" уже на самых простых задачах начинают отрабатывать способ с "иксами" и "игреками").

В поздравительном посте не случайно упомянула гематрию (когда буквы слов или выражений складываются в соответствии с порядковым номером в алфавите и сравниваются с другими, подобным образом вычисленными значениями). А нотарикон - еще одна забава с ивритскими букво-числами. Архаичный текст записывался без пробелов: страница за страницей тянется последовательность символов, и еще древние мудрецы придумали делать выборки: напр., выписывая каждую десятую букву текста. Или пятнадцатую. Или каждую сто двадцать восьмую. Разумеется, иногда на каком-то отрезке получались осмысленные сочетания (учитывая трехбуквенность ивритских корней и отсутствие гласных - оч часто получались). Изыскателей это весьма забавляло (и поныне забавляет, см "Библейский код", при нынешних-то мощностях!), толкования из найденных "вторых" и "третьих" смыслов выводили.

Живое воображение юных хамсинезиек легко перевело шеренгу лысо-белобрысо-чернявых затылков в последовательность символов. Хаотичную. Но всего трехпозиционную. "Алеф"-ы, "Бет"-ы, "Гимел"-и.
Или, в привычных нам обозначениях: лысому припишем значение 0, белому - 1, черному - 2.
И вычислим "гематрию" этого дела =)
Попросту сложим всё вместе, всех алефов-бет-гимелей, сколько их ни наесть.
Типа такого напр 1+1+1+2+2+1+2+1+1+2+2+2+...+1, (разумеется, нули плюсовать нет надобности).
До сих пор ничего сложного? Двойки и единички пересчитать.

Принцесса, не нагруженная алгеброй, искусно управляется со счетом.
И даже знает, что любое число на свете либо делится на 3, либо не делится. Ну правда ведь?
Если делилось, а от него отняли 1, то уже не будет делиться. К чему это мы клоним?

А к тому, что у младшей сестрички, вызвавшейся в подсказчицы (она стала в последнюю пару), есть три возможности закодировать условный сигнал.
(В комментах многие догадались, что младшая забила на жениха рядом с собой, а цвет шевелюры называет так, чтоб на что-то намекнуть подругам).

Может кто-то рискнет остановиться и дальше самостоятельно? - все наводки уже есть.

Не скоро сказка сказывается - на деле все осуществимо гораздо быстрей.

Подсчитала младшая сестра "гематрию" (сумму числовых значений цвета волос женихов)-
и должна указать какой-то признак полученного числа, который поможет остальным.

Три допустимых ответа - "лысый", "блондин", "брюнет" и, вот удача! - три существенных признака:
либо сумма делится на 3 нацело, либо с остатком 2, либо с остатком 1 и - никак больше.

Последняя в колонне участница видит всех принцев впереди.
- Считает блондинов за единицы, брюнетов за двойки, всё складывает (лысых, нули, не считает).

- Если сумма делится на 3 нацело (0 в остатке) - называет кодовое слово "лысый!",
если делится так, что в остатке один - говорит "блондин!", если два то - "брюнет!".

- Девушки еще по дороге, заранее, обо всем договорились, и запомнят "заветное число":
0=лысый, 1=блондин, 2=брюнет.
(На смотре положено отвечать четко, громко, слышно всем присутствующим)

- Делится/не делится, и чем это им поможет? В середине ряда ведь не всех видно.
- Начнем рассуждать с предпоследней. Которой видно _почти_ всех.

Какой вывод может сделать участница, которая сразу перед младшей сестрой стоит?
Церемония дело неспешное, чинное, и она тоже уже свою "гематрию" посчитала -
женихов, которых видит перед собой.
Осталось сравнить.
Ее "заветное" число, отличается от подсчитанного сестрой только на один единственный
затылок - жениха рядом, которого ей не видно.

Посмотрим на примерах:
Если у подсказчицы "заветное" число нацело делилась на три, а у девушки,
которая первой использует подсказку - не нацело, то сколько не достает?
Либо 2, либо 1. Либо брюнет, либо блондин. Вот и ответ!

Если же у нее тоже делится - это может быть только в одном случае -
"гематрия" не изменилась, рядом с ней "лысый".

А если из подсказки следует, что весь ряд женихов делится на три с остатком два,
а у впередистоящей участницы свое "заветное число" делится на три нацело, то?
То значит, как раз жених рядом и есть тот самый "остаток" - 2. "Брюнет" стало быть.

Какой еще случай может быть? - пусть "заветное" число из подсказки "2". А у испытуемой "1".
(Т.е. сумма численных значений всех женихов делится на 3 с остатком 2,
а то, что участница сосчитала - делится с остатком 1). Единички не достает. Где ж она?
Понятно где, рядом с невестой, в той же паре - блондин!

Сложновато?
- Точно не сложней, чем переход через разряд при сложении
в пределах двадцати. А дети ведь справляются! =)

До этого момента достаточно держать в памяти действующих
лиц и представлять их действия.

Дальше единственный пункт в рассуждении, требующий некоторой сосредоточенности:

Пусть в подсказке остаток 1, а у в расчете у героини - 2.
Будто лишний жених образовался.

1 2 2 2 0 - "женихи в числах"
  1 3 5 7 - "гематрия"(сумма) предшествующих
    0 2 1 - остаток от деления на 3

Рассуждаем так: некое число делится на три с остатком 2,
стало быть стоит добавить еще 1 - и поделится нацело, так?
А если не нацело, а еще и один в остатке? - значит добавили 2!
похоже на переход через разряд.

- Делить, остатки находить, да это калькулятор в голове нужен!
- С непривычки.

Девушке, у которой с детства был упор на внимание к рядам чисел ("найду в нотариконе "эм ахува (любимая мама), то-то все обрадуются!" А это сколько придется страниц перелопатить, "через три", "через пять", "через десять" перепробовать) не надо напряженно вычислять каждый раз, ей не трудно увидеть последовательность "в красках" с готовыми "через три":

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22....

начиная с трех через два на третье - делится нацело,
начиная с пяти - через два на третье - с остатком 2.
начиная с 4-х -- с остатком 1.

В школе некогда "наиграться" с числами, как с кубиками.
Признаки делимости и даже четность побегают мельком;
и в будущем "сравнение по модулю" остается невнятной заумью из выч.методов.
Что значит: 32 и −10 сравнимы по модулю 7, так как их разность 42 делится на 7?
Всего-то только, что они отстоят друг от друга на интервал 7 (повторенный шесть раз)
и имеют один и тот же остаток от деления на 7.

Если ученику задают находить в ряду чисел начиная с единицы "каждое седьмое", "каждое восьмое", то он быстро обнаруживает, что все искомые объекты отстоят от приметных десяток на 3, на 2 - в этом смысле архаичное обучение несколько выигрывает: вместо тупо долбить таблицу умножения, ее "распробуют из на ощупь".

Что дальше?

В начале ряда подсказчица, впереди ее сестра, которая уже благополучно определились.
Другие участницы чем-то от нее отличаются?
- Ну да, ей-то почти весь ряд женихов виден,
кроме одного единственного, ей легко сравнивать!

На самом деле и у всех остальных есть на столько же полная информация.
Только не сразу вся - а пополняемая по мере того, как предыдущие дают свой ответ.
С каждым следующим ответом претендентка в середине колонны приближается к тому же
состоянию, которое имела сестра подсказчицы.

Переместимся к следующей паре.
Вот старшая сестра "отстрелялась" использовав подсказку,
что теперь известно девушке перед ней?

Допустим, исходная подсказка давала делимость на 3. У самой очередницы - остаток 1.
И, теперь она еще знает масть жениха сзади.
Ей остается скорректировать подсказку на эту "масть".

В случае брюнета - на 2.
Теперь для нее актуальна подсказка "делится на 3 с остатком 2",
и собственный расчет где в остатке 1.

Мы уже знаем какой из этого следует вывод.
Такой же как и в рассуждениях выше.

Итого:
Все претендентки запоминают исходную подсказку младшей сестры.
И корректируют ее при каждом поступающем ответе.
А когда сзади уже все ответили, очередной соискательнице остается только сравнить
свой расчет со скорректированной подсказкой и определить данные жениха.

- Фуф. Оно стоит того, чтоб заморачиваться? Загадка явно не "салонная",
компанию не потешишь - муторно все это объяснять "с остатками по модулю";
а внукам зачем "число-игровое мышление", когда вся школа под алгебру и преобразования переменных заточена?

- Для салона можем попроще изобразить, без "модулей".
Подобные задачи не зря второй десяток лет бродят по форумам (можете нагуглить целый кластер сюжетов разной степени кровожадности "пэтэушники и инопланетяне", "гномы и людоед", "мудрецы и самоцветы" с обсуждениями на языке алгоритмов и итераций).

Дело в том, что компьютер "думает" числами: нули с единичками складывает да сравнивает;
все развесистые вычисления построены на самых элементарных операциях.
Те, кто учит машинные мозги думать, вынуждены сами думать как компьютер,
прокручивая итерации шаг за шагом.
Собственно задачи на "контрольную сумму" столь популярны потому,
что штука это исключительно распространенная (гуглим: хеш)
- проверка сохранности файлов, номера кредиток, куча всего (только "суммы" там высчитываются не простейшей "гематрией", а хитрозакрученными алгоритмами).

Совсем недавно спорили об особенностях мышления, кто вырастет перспективным программистом - мальчики или девочки?
А мы теперь знаем кто - хамсинезийские принцессы!

Хотите фокус, сразу с разоблачением?

Свежеиспеченный, по мотивам
номер для двух исполнителей - бабушки с внуком, дедушки с внучкой - и компании гостей.
Исполнители отворачиваются.
Гости берут из коробки шашек десять-двенадцать штук, выставляют в ряд на столе,
белые-черные, случайным образом. Если есть малыш в комнате, его просят забрать одну шашку,
ну или кто-нибудь из гостей снимает, держит в кулаке, повернувшейся бабушке не показывает.
Бабушка называет цвет. Когда угадывает, когда нет.
Снимают еще одну. Внук поворачивается, называет изъятую шашку. Всегда угадывает.

Как бабушка подсказывает, она же сама не знает какую снимут?

Ни складывать, ни остатки вычислять - бабушка подсказывает четность черных.
"Белая" - условный знак, что черных перед ней нечетное число и наоборот.
Внуку остается проверить хеш-сумму четность того, что осталось на столе.
Если четность черных не изменилась - значит сняли белую. Изменилась - черную.

Еще незаметнее пройдет, если других гостей привлечь;
внуку не обязательно отвечать сразу после бабушки, достаточно корректировать
ее подсказку: при каждом очередном ответе игроков -
учитывать изменяющуюся четность черных.