سوال ۱۱
در مدرسهای ۱۰ دانشآموز با شمارههای ۱ تا ۱۰ داریم که روابط دوستی میان آنها به شکل روبرو است.
دو نفر با یکدیگر دوستاند اگر و تنها اگر شمارههای متناظر آنها، در شکل به یکدیگر متصل باشند (واضح است که دوستی یک رابطهی دوطرفه است).
قرار است این دانشآموزان به صورت تک به تک به دفتر مدیر مدرسه بروند. میدانیم هر دانشآموزی که به دفتر مدیر میرود، به اندازهی مجموع شمارهی تمام دوستانش که هنوز به دفتر نرفتهاند دلگرم میشود. برای مثال، اگر ابتدا دانشآموز شمارهی ۱۰ به دفتر مدیر برود، چون تنها دوست او دانشآموز شمارهی ۴ است، به اندازهی ۴ واحد دلگرم خواهد شد. سپس اگر نفر بعدی دانشآموز شمارهی ۴ باشد، از آنجا که دو دوست دیگرِ او یعنی ۱ و ۷ هنوز به دفتر نرفتهاند، $1+7=8$ واحد دلگرم خواهد شد. دانشآموزان میخواهند به ترتیبی به دفتر مدیر بروند که در پایان، مجموع دلگرمی آنها بیشترین مقدار ممکن باشد. این مقدار بیشینه چقدر است؟
- ۶۰
- ۷۵
- ۱۲۶
- ۵۵
- ۴۰
پاسخ
گزینهی ۲ درست است.
اگر دو دانشآموز با هم دوست باشند، این دوستی دقیقاً یکی از آنها را دلگرم خواهد کرد. به عبارت دیگر به ازای هر رابطهی دوستی، شمارهی دقیقاً یکی از آن دو دوست به مجموع دلگرمیها اضافه خواهد شد، چون یکی از آنها زودتر به دفتر مدیر میرود و دیگر در دلگرمی دوستش تاثیری نخواهد داشت. پس بیشترین مجموع دلگرمی در صورتی رخ می دهد که به ازای هر دو نفر که با هم دوست هستند، کسی که شمارهاش کمتر است زودتر به دفتر مدیر برود. اگر دانشآموزان با شمارههای ۱، ۲، $\dots$، ۱۰ به همین ترتیب به دفتر مدیر بروند، این شرط برآورده میشود. در این حالت مجموع دلگرمی آنها برابر است با: $11 + 9 + 7 + 17 + 7 + 15 + 9 + 0 + 0 + 0 = 75$
| < سوال قبل | سوال بعد > |