Данную задачу вряд ли можно считать алгоритмической, и тем не менее она может пойти на пользу при разработке какой-нибудь архитектуры.
Итак, 12 пиратов награбили богатств и теперь должны поделить всю добычу поровну.
Вроде бы ничего сложного, но проблема в том, что добыча – не деньги. Она состоит из самых разных предметов – золотой кубок, сабля, часы, цепочка, сапоги, пистолет и так далее.
Эти предметы в принципе нельзя разделить поровну, и у каждого из них есть собственная уникальная ценность.
Как же пиратам выйти из ситуации?
Первое решение это конечно продать все эти вещи и поделить полученные деньги. Но в данном случае оно не работает, надо поделить сами вещи.
Авторитет
Скажем, у пиратов есть капитан, который просто разделит кучу на 12 каких-то частей и всем раздаст. Несмотря на то, что у него есть некий авторитет, пираты могут остаться недовольны раскладом и поднять бунт.
Справедливость
Необходимо отметить, что разделение при любом раскладе окажется неравным. Кому-то условно достанется больше, кому-то меньше. Но главное, чтобы все 12 пиратов понимали, что именно такое разделение справедливо. В этом случае они смогут избежать конфликта.
Случайность
Можно сделать так, чтобы предметы из кучи выдавались каждому следующему пирату случайным образом, как лотерея. Выдачу продолжать, обходя пиратов по кругу, пока все предметы не кончатся. В таком случае это будет справедливо, но неравенство в выигрыше может только усилиться, так как одному и тому же пирату может выпасть несколько самых лучших вещей.
Необходимо объединить принципы авторитета, справедливости и случайности.
Решение
Пираты выбирают одного ответственного.
Ответственный делит кучу на 12 частей. Эти части не обязаны быть равными или равноценными. Делить можно как угодно.
Затем 11 пиратов (кроме ответственного) кидают между собой жребий, и тот, кто выиграл, забирает себе любую из 12 частей.
Процесс повторяется с оставшимися пиратами и частями.
Наконец, ответственный пират забирает себе последнюю оставшуюся часть.
Почему это работает
Ответственный понимает, что в любом случае ему достанется последняя часть. Для своей выгоды он мог бы положить самое ценное в последнюю часть. Но он не знает, какая часть будет последней. Во время розыгрыша любой пират может забрать любую часть.
Его единственный выход – сделать так, чтобы в каждой части было что-то ценное, и чтобы каждая часть не была ценнее других.
Следовательно, он поделит части так, чтобы они все имели одинаковую ценность для него, а значит и для других пиратов.
Вся подборка задач: