به نظر ِ من که آسون بود. قرار هم بود که آسون باشه، تا کف حتمن 3رقمی باشه! خیلی از بچه‌ها می‌گن سخت بوده، ولی، اون‌ایی ام که می‌گن دست ِ
کم 6 تا رو حل کردیم، کم نیستن. حدس می‌زنم کف 105 باشه.
1. هر یک از جدول‌هایِ 3 * 3 دقیقن یکی از
خانه‌هایِ (2, 2)، (2, 5)، (5, 2)، و (5, 5) را دارد. پس، با حد ِ اکثر 3
پرسش، این خانه را می‌یابیم. گیرید این خانه خانه‌یِ (2, 2) باشد. اکنون،
با پرسش در باره‌یِ خانه‌هایِ (1, 2) و (2, 1)، مربع پیدا می‌شود.
در آغاز، تعداد ِ مربع‌هایِ 3 * 3یِ ممکن 42=16 است.
با هر پرسش، تعداد ِ مربع‌هایِ ممکن حد ِ اکثز نصف می‌شود، چون، هر پرسش
دو پاسخ ِ ممکن دارد. از سویی، در گام ِ یکم، هیچ پرسشی نمی‌تواند تعداد ِ
مربع‌هایِ ممکن را در هر دو حالت ِ پاسخ برابر با 8 گرداند.
2. اگر a = (10101...01)2 با 100 تا 1 و b = (000...0)2،
آن گاه، با کم‌تر از 100 پرش، نمی‌توان از a به b رسید. برایِ اثبات ِ این
ادعا، کافی است بررسی نمایید که، در هر گام، از تعداد ِ دسته‌هایِ 1 ِ
کنار ِ هم، حد ِ اکثر یکی کم می‌شود.
3. گیرید، با قرینه کردن‌هایِ پی‌درپی، یک
مربع ِ بزرگ‌تر به دست آید. بنا بر این، با انجام ِ عمل‌هایِ عکس، از مربع
بزرگ‌تر، می‌توان به مربع ِ کوچک‌تر رسید. از آن جا که، با قرینه کردن ِ
نقطه‌های ِ شبکه‌یی، هم‌واره، نقطه‌هایی شبکه‌یی به دست می‌آیند، باید، با
انجام ِ عمل‌هایِ عکس، از مربع ِ آغازین به مربعی کوچک‌تر رسید. تناقض!
4. مریم درخت را ریشه‌دار می‌کند، و
رنگ‌ها را به دو دسته‌یِ 3تایی تقسیم می‌کند. او، در گره‌ها با فاصله‌یِ
فرد از ریشه، رنگ ِ دسته‌یِ یکم، و در گره‌ها با فاصله‌یِ زوج از ریشه،
رنگ ِ دسته‌یِ دوم را به کار می‌گیرد. با هر بازی‌یِ مینا رویِ یک گره،
نیز، او پدر ِ آن گره را، در صورت رنگ‌نشده بودن، رنگ می‌کند. [به خاطر ِ نوژن! اگر پدر ِ گره رنگ شده بود، او یکی از برگ‌هایِ رنگ‌نشده را به دل‌خواه رنگ می‌کند.]
5. با شترنجی رنگ کردن ِ خانه‌هایِ جدول،
50 خانه‌یِ سیاه به دست می‌آیند، که هر یک می‌تواند به 2 حالت رنگ شود.
بنا بر این، حد ِ اقل، 1015 < 250
روش برایِ رنگ‌آمیزی‌یِ پراکنده‌یِ جدول وجود دارند. با فرش کردن ِ جدول
با 50 دامینو، دیده می‌شود که، هر یک از دامینوها می‌تواند به 3 حالت رنگ
شود. بنا بر این، حد ِ اکثر، 1025 > 350 روش برایِ رنگ‌آمیزی‌یِ پراکنده‌یِ جدول وجود دارد.
6. تعداد ِ مهره‌هایِ پخش‌شده در حرکت ِ iم را با ni نشان دهید. گیرید سطل ِ به کار گرفته‌شده در مرحله‌یِ iم در آغاز دارایِ mi مهره بوده باشد. داریم ni <= mi + i - 1. اگر، برای i = 1, 2, 3, ..., 8، داشته باشیم ni >= 10، آن گاه باید 10 <= mi + i - 1 برایِ هر i. با جمع بستن، داریم sigmai=18 10 <= sigmai=18 (mi + i - 1)، یا 80 <= 50 + 28 = 78. تناقض!
7. رویِ تعداد ِ کلیدها استقرا می‌زنیم.
با کنار گذاشتن ِ یک کلید، همه‌یِ لامپ‌هایِ متصل به آن را نیز کنار
می‌گذاریم. با توجه به فرض استقرا، می‌توان با کلیدهایِ دیگر بیش از نیمی
از لامپ‌هایِ باقی‌مانده را روشن کرد. اکنون، اگر تعداد لامپ‌هایِ
روشن‌شده در میان ِ لامپ‌هایِ کنار گذاشته‌شده کم‌تر از نصف باشد، کلید ِ
کنار گذاشته‌شده را تغییر ِ وضعیت می‌دهیم.
8. با استقرا، حکم ِ قوی‌شده‌یِ زیر را ثابت می‌کنیم.
با (n - 1)d + m پرسش، که m < d، می‌توان، در میان ِ n کارت، یک کارت
را با m اختلاف با کارت ِ کیان یافت، و اگر، در میان ِ n کارت، یک کارت با
کم‌تر از d اختلاف وجود داشته باشد، این کارت هم کم‌تر از d اختلاف دارد.
رقم ِ iم را، که همه‌یِ کارت‌ها در آن رقم یکی نیستند، می‌پرسیم. به این ترتیب، n1 کارت با رقم iم ِ درست و n2 کارت با رقم ِ iم ِ نادرست به دست می‌آیند. طبق ِ فرض ِ استقرا، با (n1 - 1)d + m1 پرسش، می‌توان یک کارت با m_1 اختلاف، و با (n2 - 1)(d - 1) + (m2 - 1) پرسش، می‌توان یک کارت با m2 اختلاف پیدا کرد. اکنون، روی ِ هم، (n - 1)d + m1 + m2 - d - n2 پرسش انجام شده، و دو کارت با m1 و m2 اختلاف به دست آمده اند. با حد ِ اکثر 2d - (m1 + m2) = (d - m1) + (d - m2) پرسش ِ دیگر، کارت ِ مطلوب به دست می‌آید.