buka, будем искать остатки от деления суммы видимых каждым мудрецом номеров на K и складывать с заранее оговоренным для каждого остатком в диапазоне [0; К-1]?
Примерно так. Но моя цель - объяснить КОНЦЕПЦИЮ, чтобы это не выглядело как фокус-покус.
1. Представьте себе такую тупую задачу: собрали 100 мудрецов и сказали им: "вот ящик, в нем бриллиантов некое кол-во, но не более 100. Хоть один из вас обязан угадать сколько там бриллиантов".
Понятно, что эта "задача" - проста до неприличия - всё, что требуется от мудрецов - это не повторяться в догадках- тогда 1 из них угадает, потому что их 100 и число бриллиантов там - от 1 до 100...
2. Именно этот принцип надо положить в основу решения и нашей задачи:
2.1 Найти - ЧТО им надо угадывать.
2.2 Договориться о том, чтобы им не повторяться ("Ты предполагаешь, что 1, ты - 2 и т.д.")
2.3 Найти способ, как получить то, что надо угадать в задаче (а это - не то, что в п.2.1) - из угаданного в п.2.1
3. Самое главное здесь - это обеспечить п. 2.1. Это и рассмотрим подробнее.
3.1 То, что надо угадывать, должно быть общим для всех.
3.2 Оно должно иметь кол-во возможных значений <= числу мудрецов
3.3 Из него можно получить то, что требуется угадать на саом деле.
4. Если угадывать сумму чисел у всех, то тот, кто угадает эту сумму легко получит то число, которое на нём.
Однако у суммы чисел число вариантов намного больше числа мудрецов: от 0 до (К-1)^2 (если 0 - минимальное число) или от К до К^2, если числа начинаются с 1.
Значит, надо угадывать нечто подобное, но имеющее меньший разброс вариантов.
4.2 И это нечто - остаток от деления этой суммы на К, где К - кол-во мудрецов.
4.2.1 Этот остаток может быть от 0 до К-1, что нас устраивает.
4.2.2 Тот, кто угадал этот остаток, тот угадал своё число. Понять это - просто.
Пусть он подсчитал сумму всех чисел (кроме своей) Сп. Вся сумма Сх = Сп + Х
Он не знает ни Сх ни Х, но полагает, что остаток от деления Сх на К равен Р
тогда ему нужно определить, каким должен быть Х, чтобы Сп + Х давало остаток Р.
И это просто. Это всегда однозначно определяет Х, если Х находится в диапазоне 0...К-1.
При нумерации с 1-цы практически ничего не меняется, просто всё сдвигается на единицу.
