علی کوچولو جمع اعداد دودویی را تازه یاد گرفته است و هنوز برخی از جمع‌ها را به‌خوبی انجام نمی‌دهد. درواقع او هنوز «دو بر یک» (همان ده بریک در مبنای دو) را حساب نمی‌کند. مثلاً اگر او بخواهد دو عدد ۱۰۱۰ و ۰۰۱۱ را جمع کند حاصل جمع را صورت ۱۰۰۱ می‌نویسد٬ در صورتی که اگر «دو بر یک»‌ها را درنظر می‌گرفت جواب برابر ۱۱۰۱ می‌شد. در ضمن علی‌‌کوچولو یک بازی جدید یاد گرفته و بسیار هیجان‌زده است.

الف) او تمام رشته‌های از ۰ و ۱ به طول ۴ (به استثنای رشته‌ی ۰۰۰۰) را روی یک صفحه‌ی کاغذ نوشته است (جمعاً ۱۵ رشته)٬ هدف او از این بازی این است که این رشته‌ها را به ۴ دسته طوری تقسیم کند که وقتی دو عدد را از یک دسته جمع می‌کند حاصل‌جمع در یک دسته‌‌ی دیگر قرار داشته باشد (توجه کنید که علی کوچولو جمع دو عدد را به صورت بالا انجام ‌می‌دهد). او چند روش را برای این تقسیم‌بندی امتحان کرده است ولی نتوانسته است این مسئله را حل کند و اکنون از شما می‌خواهد که به او کمک کنید.

این ۴ دسته‌بندی را بروی برگه‌ی پاسخ خود بنویسید.

ب) مادر علی‌کوچولو به او گفته که بلد است سوال قسمت قبل را با ۳ دسته حل کند (یعنی ۱۵ رشته را به ۳ دسته و با همان شرایط تقسیم کند). با توجه به این اطلاعات ثابت کنید می‌توان تمام رشته‌های به طول $۴n$ به‌استثنای رشته‌ی ۰…۰۰ را به $3n$ دسته طوری تقسیم کرد که جمع هیچ دو عدد از یک دسته (به روش علی‌کوچولو) در همان دسته نباشد.

• سوال بعد