جو در بازی کاکتوس نامردی کرد و با استفاده از فاصله‌ای که با لوک پیدا کرد٬ همان اول بازی پا به فرار گذاشت. او به مخفی‌گاه همیشگی دالتون‌ها در کوه‌های راکی گریخت. شهردار، آوریل را به همراه لوک به سمت آن منطقه فرستاد. آن‌ها به غار هولناکی رسیدند.

اگر فردی در این غار حرکت کند، در مسیر خود به دو راهی‌های متعددی می‌رسد که اگر هر بار یکی از آن دو راه را برای ادامه‌ی حرکت انتخاب کند، در نهایت به یک بن‌بست می‌رسد. می‌دانیم از ابتدای غار تنها یک مسیر به هر بن‌بستی وجود دارد و در این مسیر حداکثر به $n$ دو راهی برخورد می‌کنیم.

لوک می‌دانست که جو در یکی از این بن‌بست‌ها مخفی شده. او از آوریل خواست تا وی را در رسیدن به جو هدایت کند. آوریل این کار را پذیرفت، او فکر کرد با دروغ گفتن می‌تواند جو را نجات دهد. آوریل از بقیه‌ی دالتون‌ها خوش طینت‌تر بود و نمی‌خواست زیاد دروغ بگوید ولی در عین حال به خاطر حماقتش فکر کرد با یک دروغ می‌تواند لوک را گمراه کند، پس تصمیم گرفت یک دروغ بگوید.

سر هر دو راهی لوک به یکی از دو راه اشاره ‌می‌کرد و از آوریل می‌پرسید که آیا این راه ما را به مخفی‌گاه می‌رساند یا نه؟ و آوریل هم جواب بله و خیر را می‌داد. توجه داشته باشید که دادن جواب نه به یکی از دو راه لزوما به معنای آن نیست که راه دیگر به مخفی‌گاه ختم می‌شود، بلکه ممکن است به‌خاطر دروغ آوریل، قبلا راه را اشتباه آمده باشیم و الان هیچ‌یک از دو راه به مخفی‌گاه نرسد. نکته‌ی دیگر این که لوک همواره می‌دانست از کدام مسیر آمده است و بنابراین می‌توانست هر زمان که نیاز داشت، به سمت ابتدای غار تا هر کجا برگردد و در مسیر برگشت، دیگر لازم نبود سر دو راهی‌ها از آوریل سوال کند.

ثابت کنید لوک می‌تواند با حداکثر $n+f(n)$ پرسش، خود را به مخفی‌گاه جو برساند. در این جا $f(n)$ تابعی است که مرتبه‌ی رشد آن اکیدا کم‌تر از $n$ است. یعنی اگر $n$ به سمت بی‌نهایت میل کند، $\frac{n}{f(n)}$ به سمت بی‌نهایت میل کند.

• سوال بعد
• سوال قبل