سوال ۱۵
یک جدول ۳ × ۳ داریم که در یکی از خانههای آن موشی کور پنهان شده است. به هر سه خانهای از جدول که هیچ دوتایی از آنها همسطر یا همستون نباشند یک قطر پراکنده و به هر سه خانهای از جدول که در یک سطر، ستون یا قطر پراکنده باشند یک گروه میگوییم. هدف آن است که در کمترین تعداد مرحله موش کور را پیدا کنیم. در هر مرحله یکی از خانههای دلخواه جدول مانند $A$ را بازبینی میکنیم و اگر موش کور در آنجا بود او را دستگیر میکنیم. در غیر این صورت اگر موش کور در خانهای مانند $B$ باشد، پس از اتمام بازبینی فرار کرده و به خانهی همگروهی $A$ و $B$ میرود. حداقل تعداد مراحل لازم برای دستگیری موش کور چند است؟
- ۱۲
- ۱۷
- ۸
- ۹
- نمیتوان با یک روش قطعی موش کور را دستگیر کرد.
پاسخ
گزینهی ۴ درست است.
در ابتدای کار موش کور میتواند در هرکدام از ۹ خانهی جدول قرار داشته باشد. پس در مرحلهی اول ۹ گزینه برای انتخاب داریم و مجبوریم یکی از آنها را انتخاب کنیم. اگر موش کور در خانهای که ما انتخاب میکنیم قرار داشته باشد در همان مرحلهی اول دستگیر میشود. اما اگر در خانهی دیگری باشد با توجه به اینکه در کدام خانه قرار دارد، محل بعدی آن به طور یکتا تعیین میشود و همچنین هیچگاه امکان ندارد موش کور از دو خانهی متفاوت به یک مقصد مشترک حرکت کند.
پس اگر موش کور در مرحلهی اول دستگیر نشود، در یکی از ۸ خانهی دیگر بوده و حال برای هر کدام از آن ۸ خانه میتوانیم ببینیم که مقصد بعدی آنها با توجه به حرکت ما کدام خانه است. پس در مرحلهی دوم ۸ گزینه برای انتخاب داریم. دوباره اگر نتوانیم خانهی درست را انتخاب کنیم، موش کور در یکی از آن ۷ خانهی دیگر قرار داشته که دوباره میتوان مقصد هر کدام از آنها را به صورت یک به یک تعیین کرد که یعنی در مرحلهی سوم ۷ خانه برای انتخاب داریم. همین ترتیب میتوان در حداکثر ۹ مرحله موش کور را دستگیر کرد و ثابت کرد که هیچ روشی نداریم که بتوان تضمین کرد که موش کور در کمتر از ۹ مرحله پیدا میشود.
| < سوال قبل | سوال بعد > |