Элементарная логическая задача. Заведем множество потенциальных боссов, изначально там все n человек. Затем, берем любых двух челов из множества и проверяем подчиняется ли i челу j, если да, то удаляем из множества чела i, иначе удаляем из множества чела j. Заметим, что на каждом шаге мы гарантировано удалим 1 чела из нашего списка претендентов. Значит, сделав n - 1 проверку мы добьемся того, что в списке остался лишь 1 человек, который и будет боссом. Доказано, что можно определить босса, сделав менее n проверок
Формально, количество бит для представления значений определяется двоичным логарифмом от числа значений. Здесь число десятичных цифр равно 10, значит, число возможных значений равно 10. Осталось вычислить log₂10 — получится приблизительно 3,322 бита.
Иными словами, спросите себя: в какую степень нужно возвести число 2 чтобы получить 10? Правильный ответ: число 2 в степени 3,322 приблизительно равно 10.
Если вам трудно воспринять тот факт, что число бит оказалось нецелым числом, округлите в большую сторону — получится 4 бита. Но тогда и вопрос нужно было начать словами: «Какое минимальное количество бит потребуется, чтобы...»
Нецелое число бит может иметь практический смысл в вычислениях. Например, у вас есть цветное изображение, где каждый пиксель представлен смешением красного, зелёного и синего сигнала, причём для каждого сигнала возможны 10 значений яркости. Сколько бит потребуется для представления одного пикселя? Умножаем 3,322 бита на 3 сигнала — получим 9,966 бит на пиксель. На практике вы будете использовать для представления пикселя не менее 10 бит, округлив до целого числа бит.
Но было бы неправильно сказать, что для пикселя требуется как минимум 12 бит, потому что якобы для 10 значений яркости сигнала нужно целых 4 бита.