المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۱۷

سوال ۱۷

می خواهیم هشت توپ یکسان را در سه کیسه ی یکسان قرار دهیم به طوری که هیچ توپی بیرون کیسه ها نباشد و همچنین در هر کیسه تعداد فردی توپ وجود داشته باشد. با فرض اینکه کیسه ها می توانند در داخل یکدیگر قرار گیرند، به چند طریق این کار ممکن است؟ توجه کنید که اگر کیسه ی $a$ درون کیسه ی $b$ باشد، توپ های درون کیسه ی $a$ برای کیسه ی $b$ هم شمرده می شود.

  1. ۱۶
  2. ۷
  3. ۹
  4. ۱۰
  5. ۸

راهنمایی

ابتدا سعی کنید وضعیت کیسه‌ها نسبت به یکدیگر را تعیین کنید.

راهنمایی

در راستای راهنمایی پیشین، اگر سه کیسه خارج از هم وجود داشته باشد، یا دو کیسه درون کیسه‌ی دیگری قرار داشته باشند،‌ آیا حالت مطلوبی قابل ساختن است؟

راهنمایی

طبق راهنمایی پیشین،‌ تنها حالت قرارگیری کیسه‌ها بدین صورت است که یک کیسه درون کیسه‌ی دیگر، و کیسه‌ی سوم مجزا از دو کیسه‌ی دیگر قرار داشته باشد.

راهنمایی

بر تعداد سکه‌های درون کیسه‌ی مجزا حالت بندی کنید.

پاسخ

گزینه‌ی ۴ درست است.

ابتدا وضعیت کیسه‌ها نسبت به یک‌دیگر را به‌دست می‌آوریم. در صورتی که تعداد کیسه‌های بیرونی فرد باشد، یکی از کیسه‌ها حاوی زوج توپ خواهد بود. در نتیجه تعداد کیسه‌های بیرونی دو تا خواهد بود و کیسه‌ی سوم درون یکی از آن‌ها است. کیسه‌ی بیرونی که کیسه‌ای در آن نیست، می‌تواند ۱، ۳، ۵ یا ۷ توپ داشته باشد. همچنین توپ‌های باقی‌مانده در بین دو کیسه‌ی دیگر تقسیم می‌شوند (اگر توپ‌های باقی‌مانده به ترتیب ۷، ۵، ۳ و ۱ باشد به ۴، ۳، ۲ و ۱ حالت در این دو کیسه قرار می‌گیرد).

در نتیجه جواب نهایی برابر است با: $4+3+2+1=10$


ابزار صفحه