المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۷

ده شرکت تولید‌کننده‌ی کنسرو مورد آزمایش قرار گرفتند. می‌دانیم که دقیقاً یکی از شرکت‌ها از گوشت فاسد استفاده می‌کند. آزمایش به این صورت بود که به هر داوطلب، دو کنسرو از دو شرکت مختلف داده شد و به هیچ دو نفری جفت کنسروهای یکسانی داده نشد. می‌دانیم اگر کسی کنسرو فاسد بخورد، می‌میرد. پس از این‌که داوطلب‌ها کنسروهایشان را خوردند، اطلاعات بدست آمده از مرگ دوطلبان برای یافتن شرکت متخلّف، کافی نبود. تعداد داوطلب‌ها حدّاکثر چند نفر بوده است؟

  1. ۲۰
  2. ۲۸
  3. ۲۹
  4. ۳۶
  5. ۴۵

پاسخ

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

می‌دانیم اگر فردی بمیرد مشخص می‌شود که یکی از دو شرکت سازنده کنسرو او کنسرو فاسد تولید می‌کنند. در نتیجه این دو شرکت در غذای هر کدام از افراد دیگر آمده باشند شرکت فاسد مشخص خواهد شد (اگر شرکت سالم در غذای فردی بیاید او نخواهد مرد زیرا فقط یک شرکت فاسد داریم و در این صورت شرکت فاسد مشخص می‌شود و در صورتی که شرکت فاسد در غذای فردی دیگر بیاید او خواهد مرد و در این صورت نیز شرکت فاسد شناسایی خواهد شد). پس تنها حالت ممکن این است که شرکت فاسد و شرکتی که با شرکت فاسد آمده است دیگر در هیچ گروهی نیایند که در این صورت بقیه شرکت‌ها 28=$\binom{8}{2}$ حالت امکان تشکیل گروه را دارند. پس در کل 29 دسته می‌توانند تشکیل شوند که باعث کشته شدن فقط یک نفر خواهند شد و شرکت فاسد نیز مشخص نخواهد شد.


ابزار صفحه