بزرگراهها
بین $n$شهر در یک کشور ($2 \lt n$)٬ $n-۱$ بزرگ‌راه به گونه‌ای احداث شده‌اند که از هر شهر به شهر دیگر می‌توان سفر کرد. هر بزرگ‌راه دقیقاً دو شهر را به یکدیگر وصل می‌کند که این زوج‌شهرها را «مجاور» هم می‌نامیم. قرار است به هر بزرگ‌راه یک عدد به عنوان عوارض اختصاص یابد به گونه‌ای که هر خودرویی که از آن بزرگ‌راه می‌گذرد مجبور باشد آن مقدار عوارض را به هریک از دو شهر در دو سر آن بزرگ‌راه بپردازد. درآمد هر شهر برابر مجموع عوارض اختصاص یافته به بزرگ‌راه‌هایی است که یک سرشان به آن شهر متصل است.
یک تیم کارشناسی به ازای هر بزرگ‌راه دو عدد مختلف پیشنهاد کرده است و ما میتوانیم یکی از این دو عدد را به عنوان عوارض آن بزرگ‌راه تعیین کنیم. ولی به دلیل افزایش رقابت بین شهرها٬ عوارض تعیین شده بین بزرگراهها باید طوری باشد که درآمد هر شهر با هیچ یک از شهرهای مجاورش یک‌سان نباشد.
الف) ثابت کنید اگر تمامی عددهای پیشنهادی حقیقی و بزرگ‌تر از صفر باشند٬ همواره می‌توان عوارض بزرگراهها را طوری تعیین کرد که شرط رقابت شهرها برقرار بماند.
ب) فرض کنید امکان پیشنهاد عدد صفر هم باشد (یعنی امکان دریافت نکردن عوارض در بعضی بزرگراهها). مثالی ارائه کنید که در آن نتوان عوارض هر بزرگ‌راه را از بین اعداد پیشنهادی به گونه‌ای انتخاب کرد که شرط رقابت شهرها برقرار بماند. دقت کنید که در مثال خود باید برای هر بزرگ‌راه دو عدد متفاوت پیشنهاد کنید که دست کم یکی از آن دو عدد بزرگ‌تر از صفر باشد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
