красивая задача

(рассказал Питер Гач): задумано натуральное число x от 1 до миллиона, его нужно отгадать, для чего разрешается задать 1000 вопросов вида "x больше ...?", при этом противнику разрешается дать до 100 неверных ответов. (Следующий вопрос задаётся после получения ответа на предыдущий, иначе это невозможно - кстати, тоже задача, почему)

(Решение простое и изящное, хотя догадаться, наверно, не просто)