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