سوال ۵
محمدحسین می‌خواهد یک نمایشگاه وسایل خانگی را برق‌کشی کند. متأسفانه در کل این نمایشگاه تنها یک پریز برق وجود دارد. البته محمدحسین فکر این‌جا را کرده و با خود تعداد زیادی $n$راهی آورده است. به یک $n$-راهی ($۱\le n$) می‌توان $n$ تا دو شاخه‌ی برق وصل کرد و یک دوشاخه دارد که باید به طریقی (مستقیم به پریز یا توسط $n$-راهی‌های دیگر) به برق وصل شود تا دوشاخه‌هایی که بدان وصلند را برق‌دار کند. اگر محمدحسین ده تا ۱۰راهی٬ هفت تا ۷راهی٬ پنج تا ۴راهی٬ چهار تا ۲راهی و صدتا ۱راهی داشته باشد٬ حداکثر چند وسیله‌‌ی خانگی را می‌تواند به برق متصل کند؟
- ۱۵۰
- ۱۵۲
- ۱۲۶
- ۱۲۷
- هیچ‌کدام
پاسخ
گزینه (۲) درست است.
هر $n$راهی یک دوشاخه دارد که باید به یکی از راه‌های یک $m$راهی وصل می‌شود٬ بنابراین هر $n$راهی یک راه را از بین برده و$n$راه جدید ایجاد می‌کند که برایند آن تولید $n-1$ راه می‌شود٬ در نتیجه تعداد کل راه‌های موجود با احتساب پریز اولیه به شکل زیر به‌دست می‌آید:
$$x=1+10\times(10-1)+7\times(7-1)+5\times(4-1)+4\times(2-1)+100\times(1-0)=152$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
