Константин Кноп (knop) wrote,
Константин Кноп
knop

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

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

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

Posts from This Journal “Взвешивания” Tag

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 3 comments