فرض کنید $n$ یک عدد طبیعی $(n>2)$ و $r$ یک عدد حقیقی $(0\leq r \leq 1)$ باشد.

دو نفر با نام‌های $A$ و $B$ با یک‌دیگر بازی زیر را انجام می‌دهند: $A$ یک عدد طبیعی $x$ $(1\leq x \leq n)$ را در نظر می‌گیرد. $B$ باید عدد $x$ را پیدا کند. برای این منظور، سوال‌هایی از $A$ می‌پرسد. سوال‌هایی که $B$ از $A$ می‌پرسد به این صورت هستند که «آیا $x$ از $k$ بزرگ‌تر است؟» ($k$ می‌تواند هر عدد طبیعی بین ۱ و $n$ باشد و توسط $B$ انتخاب می‌شود). جواب‌های $A$ به صورت «بله» یا «خیر» است. $A$ ممکن است در جواب بعضی از سوالات دروغ بگوید. اما می‌دانیم که برای هر عدد طبیعی $i$ تعداد دروغ‌هایی که $A$ می‌تواند در جواب سوالات اول تا $i$ ام بگوید از $\lfloor ri \rfloor$ تجاوز نمی‌کند. ( منظور از $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیح نابیش‌تر از $x$ است).

الف) الگوریتمی بنویسید که با فرض $r< \frac{1}{2}$ عدد طبیعی $n$ و عدد حقیقی $r$ را از ورودی دریافت کرده و به جای $B$ بازی کند. یعنی سوالاتی به شکل «$Is \quad x >k?$» در خروجی چاپ کرده پاسخ‌های $A$ را از ورودی دریافت نماید و با توجه به این پاسخ‌ها و این شرط که $A$ نمی‌تواند به بیش از $\lfloor ri \rfloor$ تا از $i$ سوال اول پاسخ دروغ دهد، عدد $x$ را پیدا کند.

در مورد ایده‌ی الگوریتم حرز توضیح داده و متغیرهای آن‌را معرفی نمایید. مثال:

ب) ثابت کنید که اگر $r \geq \frac{1}{2}$ باشد $A$ می‌تواند طوری به سوالات $B$ جواب دهد که $B$ هیچ‌گاه نتواند عدد $x$ را پیدا کند. (یعنی همواره بیش از یک امکان برای عدد $x$ موجود باشد).

• سوال قبل