المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۷

۷ تا کره‌ی یک‌شکل و یک‌رنگ داریم که از جنس‌های متفاوت ساخته‌شده‌اند. می‌دانیم که حداقل ۴ تا از این کره‌ها از یک جنس هستند ( به این جنس، «غالب» می‌گوییم). دو تا کره را برمی‌داریم و به هم می‌چسبانیم، اگر از یک جنس باشند جرقه می‌زند، در غیر این صورت اتفاقی نمی‌افتد. با حداقل چند بار چسباندن کره‌ها به هم مطمئناً می‌توان یک کره پیدا کرد که از جنس غالب باشد؟

  1. ۳
  2. ۴
  3. ۵
  4. ۶
  5. ۷

پاسخ

گزینه (۲) درست است.

ابتدا کره‌ها را به سه دسته دوتایی یک دسته یکی‌ای تقسیم کرده و کره‌های موجود در هر دسته دوتایی را به هم می‌چسبانیم که یکی از حالات زیر اتفاق می‌افتد:

  1. هیچ زوجی جرقه نزند. در این حالت معلوم می‌شود که کره تنها٬ از جنس غالب است.
  2. فقط یک زوج جرقه بزند. معلوم می‌شود که هر دو کره موجود در آن دسته از جنس غالب است.
  3. فقط دو زوج جرقه بزند. از هر یک ازاین دسته‌ها یک کره بیرون آورده و آن دو را به هم می‌چسبانیم که اگر جرقه زد٬ آن‌گاه هر دو از جنس غالب هستند و اگر جرقه نزد کره تنها٬ از جنس غالب خواهد بود.
  4. هر سه زوج جرقه بزنند. از هر یک از دسته‌های اول و دوم یک کره بیرون آورده و به هم می‌چسبانیم٬ اگر جرقه بزند که غالب هستند و اگر جرقه نزند هر دو کره موجود در دسته سوم غالب هستند.

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


ابزار صفحه