کشوری با $n$ شهر را «صرفه‌جو» گوییم اگر دقیقاً $n-۱$ جاده بین شهر‌های آن به گونه‌ای کشیده شده باشد که بتوان با شروع از هریک از شهرهای آن با استفاده از جاده‌ها به هر شهر دیگری از آن رسید. توجه کنید که هر جاده بین دو شهر کشیده می‌شود. می‌توان ثابت کرد که اگر هر یک از جاده‌های یک کشور صرفه‌جو از بین برود٬ کشور به دو زیر کشور صرفه‌جو٬ تقسیم می‌شود. مثلاً اگر یک کشور صرفه‌جو با ۲ شهر داشته باشیم و تنها جاده‌ی موجود در آن را حذف کنیم دو کشور صرفه‌جو که هرکدام ۱ شهر دارند به دست می‌آید. کشور ناریا یک کشور صرفه‌جو با $n$ شهر است. در ضمن می‌دانیم که به هرکدام از شهرهای این کشور حداکثر ۳ جاده متصل شده است. ثابت کنید در این کشور جاده‌ای وجود دارد که با حذف آن دو کشوری که به دست‌ می‌آیند هرکدام حداقل $\lfloor \frac n۳ \rfloor$ و حداکثر $\lceil \frac {۲n}۳ \rceil$ شهر داشته باشند. ($\lceil r \rceil$ کوچک‌ترین عدد صحیح بزرگ‌تر یا مساوی $ r $ و $\lfloor r \rfloor$ بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی $ r $ است. )

• سوال بعد
• سوال قبل