جلسهی 37: هتلِ حیوانات The Animal Hotel
در هر اتاقِ یک هتل یک حیوان هست. دو حیوان را جابهجا میکنیم، ولی هیچکس نباید به اتاقی برود که قبلاً در آن بوده. میشود هر حیوان در همهی اتاقها بماند؟ حالتهای کوچک، شمردنِ جابهجاییها، و اثباتِ اینکه با ۳ اتاق نمیشود.
در این جلسه یاد میگیری
- یک فرایند را با حالتهای کوچک امتحان میکنی.
- تعدادِ قدمها را با یک شمارشِ دوگانه پیدا میکنی.
- غیرممکن بودن را با بررسیِ همهی حالتها (با کمک تقارن) ثابت میکنی.
درس
یک هتل n اتاق دارد و در هر اتاق یک حیوان است. هر بار دو اتاق را انتخاب میکنیم و حیوانهایشان را جابهجا میکنیم؛ ولی هیچ حیوانی نباید به اتاقی برود که قبلاً در آن بوده. هدف: هر حیوان در همهی n اتاق بوده باشد. اگر شدنی باشد، n را «کامل» میگوییم.
n = ۲ کامل است (یک جابهجایی). بازی کن: آیا ۴ کامل است؟ جدولِ پایین نشان میدهد هر حیوان در کدام اتاقها بوده.
یک شمارشِ قشنگ: هر حیوان باید به n − ۱ اتاقِ تازه برود، پس روی هم n(n − ۱) «ورود به اتاقِ تازه» لازم است. طبقِ قانون، در هر جابهجایی هر دو حیوان به اتاقِ تازه میروند: دقیقاً ۲ ورود. پس هر نقشهی کامل دقیقاً n(n − ۱) ÷ ۲ جابهجایی دارد، نه کمتر و نه بیشتر. برای ۴ اتاق: ۶ جابهجایی.
این «شمردن از دو طرف» (یک چیز را دو جور شمردن) در مرحلهی دوم زیاد به کار میآید.
۳ کامل نیست. بنابه تقارن فرض کن اولین جابهجایی بینِ اتاقهای ۱ و ۲ است. حیوانهای این دو اتاق دیگر نمیتوانند با هم جابهجا شوند (هر دو در هر دو اتاق بودهاند)، پس جابهجاییِ دوم باید با اتاقِ ۳ باشد؛ باز بنابه تقارن، ۳ و ۲. حالا یک حیوان هر سه اتاق را دیده و دو حیوانِ دیگر هر کدام یک اتاق کم دارند، ولی تنها جابهجاییِ باقیمانده که هر دو را به اتاقِ تازه ببرد وجود ندارد. (برنامهی کامپیوتر هم میگوید ۲، ۴، ۵ و ۶ کاملاند و ۳ نه.)
سؤالِ اصلیِ المپیاد یک ساختنِ زیبا بود: اگر m و n کامل باشند، m × n هم کامل است.
چالشها
- Two Rooms (آسان)
- Four Rooms (آسان)
- Which Are Complete? (متوسط)
- Counting the Swaps (متوسط)
- Ten Rooms (سخت)
- Why Not Three? (سخت)
- Try It in Python: Search for a Plan (سخت)
← جلسهی 36: شهرهای بههمپیوسته جلسهی 38: آزمونِ تشریحیِ آزمایشی →