Задача "Помогите нумизмату"

Очередное моё творчество для "Элементов".
http://elementy.ru/problems/1093
На сей раз в качестве задачи выбран сюжет 10.8 из Всероса этого года (авторы - Илья Богданов и Сергей Берлов), хотя доказательство оптимальности я написал по-другому. В "Послесловии" показаны еще две задачки, в которых оптимальность алгоритма доказывается тем же методом - рассмотрением Соперника, который играет против произвольного алгоритма.

Если вы знаете еще какие-нибудь нетривиальные задачи, в решении которых появляется Adversary/Соперник, - напишите, пожалуйста.