فهرست مندرجات
سوالات ۱۲ و ۱۳ و ۱۴
در فرودگاه شهری که شنگدباو در آن زندگی می‌کند یک هواپیمای مرموز وجود دارد. در بخش مسافران هواپیما، تنها یک ردیف ۱۰تایی صندلی با شماره‌های ۱ تا ۱۰ وجود دارد و هیچ صندلی دیگری نداریم!
این صندلی‌ها مانند صندلی‌های همه‌ی هواپیما‌های دیگر هستند و ۱۱ دسته‌ی صندلی دارند که بین هر دو صندلی و همچنین در دو انتهای ردیف قرار دارند. روی هر یک از ۱۱ دسته، شامل دو دسته‌ی انتهای ردیف، دو کمربند قرار دارد که یکی قفلی کمربند و دیگری قلاب آن است. هر فردی که روی یک صندلی نشسته، برای بستن کمربند خود باید قلاب یکی از دو دسته‌ی مجاورش را بردارد و به قفلی دسته‌ی دیگر ببندد.
همه‌ی اعضای شهر درگیر مسئله‌ی این ده صندلی شده‌اند و شنگدباو به‌عنوان یک دانشمند می‌خواهد به سوالات مردم شهر جواب دهد تا آن‌ها را آرام کند! اما ما می‌دانیم شنگدباو برای حل این معما‌ها به کمک شما احتیاج دارد. در تمامی سوالات، دو حالت بستن کمربندها را متمایز می‌دانیم اگر حداقل یک قفلی یا قلاب وجود داشته باشد که در یکی از حالات استفاده شده و در حالت دیگر استفاده نشده باشد. همچنین، به حالتی که تمامی صندلی‌ها سرنشین دارند و تعدادی از افراد، طوری کمربند‌های خود را بسته‌اند که هیچ یک از افراد باقی‌مانده نتوانند کمربند خود را ببندند، حالت مزاحم می‌گوییم. حالتی که تمامی افراد کمربندشان را بسته باشند، حالت مزاحم نیست.
سوال ۱۲
در چند حالت تمامی ۱۰ سرنشین کمربندشان را بسته‌اند؟
- 2
- 20
- 1
- 10
- 11
پاسخ
گزینه (۱) درست است.
در تمامی زیر مسئله‌ها فرض کنید کسانی که از قفلی راست استفاده می‌کنند را با «R» و کسانی که از قفلی چپ استفاده می‌کنند را با «L» و کسانی که کمربند نبسته‌اند را با «#» نشان دهیم. همچنین به کسی که نمی‌تواند کمربند خود را ببندند محدود می‌گوییم.
تنها در حالتی که همه R یا همه L باشند همه می‌توانند کمربند خود را بسته باشند. چون در صورتی که یک LR یا RL باشد یک قفلی یا یک قلاب هست که مشترکا استفاده شده است.
سوال ۱۳
کمینه‌ی تعداد سرنشین‌ها با کمربند بسته میان تمامی حالات مزاحم چند است؟
- 6
- 5
- 9
- 10
- 7
پاسخ
گزینه (۱) درست است.
می‌توان ثابت کرد در هر حالت از حالت مزاحم دو نفر متوالی وجود ندارند که هر دو محدود باشند(؟). همچنین نفر ابتدایی و انتهایی همواره می‌توانند کمربند خود را ببندند. پس حداقل ۶ نفر می‌توانند کمربند خود را ببندند. در مثال «R#L#R#L#RR» دقیقا ۶ نفر کمربند خود را بسته‌اند و باقی افراد نمی‌توانند کمربند خود را ببندند.
سوال ۱۴
چند حالت مزاحم وجود دارد؟
- 108
- 54
- 296
- 10
- 110
پاسخ
گزینه (۱) درست است.
با توجه به نتایج سوال قبلی می‌دانیم در بین 8 صندلی وسط دو صندلی متوالی محدود وجود ندارد.
به $fib(10)=54$ طریق می‌توان جای صندلی‌های محدود را میان ۸ صندلی وسط مشخص کرد(؟). همچنین حالتی که همه کمربند خود را بسته باشند نیز حساب نمی‌شود، پس به ۵۴ طریق می‌توان جای صندلی‌های محدود را مشخص کرد. حال با توجه به اینکه نفر سمت راست کمربند خود را از سمت چپ یا راست ببندد، به صورت یکتا مشخص می‌شود که هر یک از افراد دیگر از کدام قفلی و قلاب استفاده کنند تا صندلی‌های مشخص شده محدود شوند(؟). پس در مجموع ۱۰۸ حالت مزاحم وجود دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
