سوال ۹
در مسئله‌ی قبل، فرض کنید تعداد درخت‌ها ۵۰ و ارتفاع هر درخت یک عدد صحیح غیرتکراری از ۱ تا ۵۰ است. همچنین فاصله‌ی بین تمامی درخت‌ها عدد صحیح x است. در ضمن ترتیب چیدن درخت‌ها نیز در اختیار ما است. می‌خواهیم x را طوری تعیین کنیم که بتوان با یک برش تمامی درخت‌ها را انداخت. مقدار x حداکثر چند است؟
- ۱۶
- ۱۷
- ۱۸
- ۱۹
- ۲۰
راهنمایی
طول درخت‌هایی را که هیچ‌گاه افتادنشان باعث افتادن درخت‌های جلوترشان نمی‌شود، بیابید.
راهنمایی
برای این که درخت‌های فوق بیفتند و دنباله افتادن‌ها نیز ادامه بیابد، با توجه به این که نمی‌خواهیم درخت جدیدی را ببریم، درخت‌های پیش از هر یک از آن‌ها باید چه شرایطی داشته باشند؟
راهنمایی
روی این که درخت با حداکثر ارتفاع ($50$) حداکثر چند درخت از درختان فوق را می‌اندازد، حالت‌بندی کنید. مقدارهای ممکن برای $x$ را در حالت‌بندی خود در نظر بگیرید. سپس این نکته را به همه‌ی درخت‌ها تعمیم دهید.
پاسخ
گزینه‌ی ۲ درست است.
افتادن هر درخت معادل با افتادن چند درخت دیگر خواهد بود در صورتی که ارتفاع آن از x بیش‌تر باشد. در نتیجه باید تعداد این چنین درخت‌هایی با ضریب انداختنشان (یک درخت می‌تواند چند درخت را بیاندازد) بیش‌تر از ۴۹ شود که به ازای x = ۱۷ چنین اتفاقی می‌افتد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
