Олимпиада имени Леонарда Эйлера
2011-2012 учебный год, I тур дистанционного этапа


У Али-Бабы есть 40 мешков с монетами. Джинн может по просьбе Али-Бабы определить количество монет в каждом из двух указанных ему мешков, но при этом возьмёт за работу одну монету из одного из этих мешков (и Али-Баба не увидит, из какого именно). Сможет ли Али-Баба действовать так, чтобы после не более чем 100 таких процедур точно сказать, сколько монет в данный момент лежит в каждом из мешков, кроме тех двух, которые джинн пересчитывал последними? В каждом мешке — не меньше 1000 монет.
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Ответ. Сможет.
Решение. Пронумеруем мешки: $1, 2, \dots, 40$. Определим последовательно количества монет в следующих мешках: $(1, 2)$, $(2, 3)$, $(3, 4)$, $\dots$, $(39, 40)$. После второй операции мы будем точно знать число монет в мешке 1 (т.к. поймём, изменилось ли после первой операции число монет в мешке 2), после третьей — число монет в мешке 2 и т.д. Тем самым, после 39-й операции мы будем точно знать число монет во каждом из первых 38 мешков.