Отравленное вино
АлгоритмыНаходчивому трактирщику стало известно, что поборники нравственности тайком пробрались в его погреб и отравили одну из 64 бочек вина. Тот, кто попробует отравленное вино, в ближайшую полночь провозгласит себя трезвенником и отныне не сможет выпить ни капли спиртного. У трактирщика четверо пьющих слуг. Какое минимальное число дней ему понадобится, чтобы гарантированно найти отравленную бочку, наливая вино своим слугам? Определите максимальное число бочек, при котором можно справиться с задачей за тот же срок.
Трактирщик не может участвовать в дегустации вина.
1) Вам нужно найти такое число D, что за D дней можно проверить 64 бочки (и доказать это), но ни для какого d < D за d дней проверить 64 бочки нельзя (и доказать это).
2) Вам нужно найти такое N, что за D дней можно проверить N бочек (и доказать это), но ни для какого n > N за D дней проверить n бочек нельзя (и доказать это).
47 комментариев