سؤال ۱۷
۸ خانواده به یک مهمانی دعوت شده‌اند. تعداد اعضای خانواده‌ها به ترتیب برابر ۴، ۴،۴ ، ۴، ۵، ۵، ۵ و ۵ نفرند. میزبان برای شام تعدادی میز در نظر گرفته است که هرکدام دقیقاً ۷ جای صندلی دارد. میزبان می‌خواهد جای نشستن هر فرد را از قبل تعیین کند به‌طوری که هیچ دو نفر از اعضای یک خانواده دور یک میز ننشینند. حداقل تعداد میزهای موردنیاز چند تاست؟
- ۴
- ۵
- ۶
- ۷
- ۸
پاسخ
گزینه (۳) درست است.
تعداد کل افراد آن خانواده برابر $4\times5+4\times4$ یعنی ۳۶ می‌شود. معلوم است که جا دادن ۳۶ نفر در دور میزهای ۷ نفره به طوری که تعداد آن‌ها ۵ یا کم‌تر باشد٬ امکان‌ناپذیر است(۵ میز ۷ نفره حداکثر ۳۵ نفر در خود جای می‌دهند). جا دادن افراد در دور ۶ میز با شرط اشاره شده امکان‌پذیر است٬ کافی است خانواده‌ها به ترتیب با $a$،$b$،$c$،$d$،$e$،$f$،$g$ و $h$ نام‌گذاری کرده و دور هر میز دقیقا ۶ نفر قرار دهید؛ یعنی دور هر میز دقیقا از دو تا از خانواده‌ها موجود نباشد که حالت‌بندی آن به شکل زیر می‌شود:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
