Пришел ко мне недавно наш LABораторный математик, Сережа Ольшевский. Пришел и попросил спросить совета у нашего всезнающего междисциплинарного сообщества.
А началось с того, что Сергей со своим учеником решал классическую олимпиадную задачу, которую знают, наверное, все айтишники. Про то, какое минимальное количество вопросов с ответом «да/нет» нужно, чтобы гарантированно угадать число от 1 до 20? Суть в том, что Сергею попался какой-то непростой подопечный (может новый Перельман?) который (внезапно) выдал очень нестандартное видение. Подробнее сам ход описан в статье. Ну ладно, не буду спойлерить, просто возьму фрагмент из этой самой статьи, с главным вопросом, помощи в ответе на который и ищет математик. Итак ⬇️
Если мы можем: преобразовать множество из 20 чисел в множество из 13 (≤16) значений, то означает ли это, что задачу можно решить за 4 вопроса? Или здесь есть фундаментальное ограничение, которое не позволит это сделать, даже при таких преобразованиях дальнейших множеств?
Поэтому, если вы любите математику, занимаетесь теорией информации или просто любите красивые задачи, то подключайтесь. Я буду очень благодарен, даже если кто-то покажет уже существующее решение или докажет, что такой подход невозможен. Потому что сейчас для меня это редкое состояние, когда кажется, что классическая задача ещё не сказала своего последнего слова.
Есть предложения? Пишите в комментарии или прямо под сообщение Сергею