سارا علاقه‌ی زیادی به نمایش اعداد در مبنای ۲ دارد! یک روز صبح٬ او تمام اعداد ۰ تا $2^n-1$ را روی $2^n$ عدد نوار کاغذی٬ در مبنای ۲ می‌نویسد و در سمت چپ اعدادی که کم‌تر از $n$ رقم دودویی (اصطلاحاً «بیت») دارند٬ آن‌قدر صفر می‌گذارد تا تمام اعداد دقیقاً $n$ بیتی بشوند.

عصر همان روز٬ دارا (برادر سارا)٬ نوارهای او را برداشته و به اتاق خودش می‌رود. سپس٬ دور از چشم سارا٬ ابتدا نوارها را با یک ترتیب دل‌خواه زیر هم قرار می‌دهد (تا چیزی شبیه یک جدول با $2^n$ سطر و $n$ ستون از ارقام ۰ یا ۱ درست شود)؛ و بعد از آن روی هر کدام از $2^n \times n$ بیت این نوارها٬ یک سکه قرار می‌دهد تا بیت زیر آن دیده نشود. پس از این کار٬ دارا از سارا می‌خواهد که به اتاقش بیاید و با برداشتن حداقل تعداد سکه‌ از روی بیت‌های نوارها٬ تعیین کند که نوار هر کدام از سطرها٬ دقیقاً کدام یک از اعداد تا $2^n-1$ اولیه است.

بعد از کمی فکر کردن٬ سارا تمام سکه‌های همه‌ی نوار‌ها به جز نوار آخر را برمی‌دارد (تا اعداد آن‌ها را به سادگی ببیند) و سپس نتیجه می‌گیرد که بیت‌های زیر سکه‌های آخرین نوار٬ عددی از اعداد ۰ تا $2^n-1$ را تشکیل می‌دهند که در نوار‌های دیگر نیامده است! دارا که چندان از ایده‌ی سارا خوشش نیامده٬ از او می‌خواهد که سعی کند با برداشتن تعداد کم‌تری سکه٬ ماهیت همه‌ی نوارها را تشخیص دهد.

به سارا کمک کنید و روشی ارائه دهید که برای هر $2 \le n$٬ او بتواند با برداشتن حداکثر $((n-1) \times 2^n) + 1$ سکه٬ تمام نوار‌ها را به طور دقیق شناسایی کند.

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