Question

Вы внедрились в мафиозную группировку под прикрытием. Разумеется, боссу здесь подчиняются все, а босс никому не подчиняется.

В группировке n человек, не считая вас. Вы можете проверить, подчиняется ли человек i человеку j. Сможете ли вы определить босса мафии, сделав менее n проверок? Если да, то как? Если нет, докажите, почему.

Так как группировка работает в Берляндии, то A может подчиняться B, а B подчиняться A одновременно. Так же стоит отметить, что вы, к сожалению, не босс.​

Answer 1

Элементарная логическая задача. Заведем множество потенциальных боссов, изначально там все n человек. Затем, берем любых двух челов из множества и проверяем подчиняется ли i челу j, если да, то удаляем из множества чела i, иначе удаляем из множества чела j. Заметим, что на каждом шаге мы гарантировано удалим 1 чела из нашего списка претендентов. Значит, сделав n - 1 проверку мы добьемся того, что в списке остался лишь 1 человек, который и будет боссом. Доказано, что можно определить босса, сделав менее n проверок