Форум умных людей

РЕШЕНИЕ. Прежде всего, сведем задачу к дискретной. Разделим каждую кучу (с остатком) на мелкие части, размер каждой 10^-6 от общего количества песка. Остатком пренебрежем, ибо суммарный размер остатков не больше 10·10^-6 = 10^-5 от общего числа песка. Будем рассматривать каждую часть как «монетку» и укажем алгоритм, позволяющий Али-Бабе получить более 99% от общего числа монет. Алгоритм действий Али-Бабы заключается в следующем:

1. Всякий раз выбираются 4 самых больших кучи.

2. От самой большой откладывается вправо одна монетка, от второй по величине две, от третьей три, от четвертой четыре.

3. Эти правые части разбойник переставляет, после чего происходит слияние.

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

а) либо увеличивается максимальная куча,

б) либо не меняется максимальная, но увеличивается вторая по величине,

в) либо не меняются первые две, но увеличивается третья. Ясно, что шагов первого типа конечое число, а когда они кончатся, будет конечное число шагов второго типа, а когда кончатся эти шаги - то третьего. Поэтому процесс остановится. (А.Я. Канель)