Вълшебен камък

[Гост]

(Откраднато от списание "Квант")
В Средната земя има n графства и Гандалф знае, че в някое от тях е скрит вълшебния пръстен. За щастие, разполага с вълшебен камък, с който всеки ден може да извършва следната операция: На камъка се дава множество от графства и той отговаря дали пръстенът е в някое от тези графства. Проблем е, че камъкът може да послъгва, но никога не лъже 2 последователни дни.
Гандалф може да прилага горната операция краен брой пъти и накрая да избере k графства, така че пръстенът гарантирано е в някое от тях (и съответно да се запъти към тях, за да го намери). Да се намери най-малката възможна стойност на k.