مرتضی $n$ کارت و کیان ۱ کارت دارند که روی هر یک از آن‌ها یک رشته از صفر و یک به طول $l$ نوشته شده است. در بین کارت‌های مرتضی٬ دست‌کم یک کارت وجود دارد که رشته‌ی آن با رشته‌ی نوشته شده روی کارت کیان کم‌تر از $d$ رقم اختلاف دارد. منظور از اختلاف دو رشته٬ تعداد رقم‌های متفاوت در آن‌هاست٬ مثلاً اختلاف دو رشته‌ی ۱۰۱۱۰۱ و ۰۰۱۱۱۱ برابر ۲ است زیرا در اولین و پنجمین رقم (ازسمت چپ) تفاوت دارند. هدف مرتضی این است که با تعداد کمی پرسش٬ کارتی را پیدا کند که اختلاف رشته‌ی آن با رشته‌ی کارت کیان کم‌تر از $d$ رقم باشد.

هر بار مرتضی یک عدد $i$ انتخاب می‌کند و کیان رقم $i$ام رشته‌ی خود را به او می‌گوید. ثابت کنید مرتضی می‌تواند با کم‌تر از $nd$ پرسش کارت مورد نظرش را پیدا کند.

• سوال قبل