Перевод для mixstuff – Onriom

Правильный ответ – 341 монета.

MC111-1024x576

Вообще, существует бесконечное число решений, но в случае, если общее число монет меньше 1000, ответ будет всего один. Эта задачка является примером китайской теоремы об остатках (китайской леммы).

Ответ с наименьшим числом будет находится в диапазоне до 1000, и равен числу 341. Чтобы решить задачку, нужно решать ее с конца. С 11-ю пиратами все монеты распределялись поровну, значит ответ будет в следующем списке чисел:

11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143…

Что произойдет, если мы возьмем эти числа и разделим их на 12 пиратов? Сколько золотых останется? Очевидно, нам нужно, чтобы после деления 5 монет уходило в остаток. Следовательно, список сокращается до:

77, 209, 341, 473…

Все эти числа делятся на 11 без остатка и дают 5 в остатке, если их поделить на 12. Теперь мы берем эти числа и делим их на 13, пока не найдем число, которое дает в остатке 3-ку. Таким образом, ответ – 341 золотая монета.

.