سوال ۳۹
یک کشور دارای چند شهر و چند جاده‌ی بین شهری است. در برنامه‌ی توسعه،
دولت تصمیم می‌گیرد بین هر دو شهری که قبلاً با استفاده از دقیقاً دو
جاده می‌شد از یکی به دیگری رفت، یک جاده تأسیس کند. مثلاً اگر یک کشور
شامل سه شهر $B$، $A$ و $C$ و دو جاده‌ی $A-B$ و $B-C$ باشد، بعد از
برنامه‌ی توسعه، بین شهرهای $A$ و $C$ هم جاده تأسیس می‌شود.
فرض کنید کشوری دارای ۵ شهر باشد. آیا ممکن است بعد از برنامه‌ی توسعه، شکل شهرها و جاده‌های این کشور مطابق شکل مقابل باشد؟ (دایره‌های توپر نشان‌گر شهرها و خط‌های بین آن‌ها نشان‌گر جاده‌ها هستند.)
پاسخ
از دو جاده‌ی $AB$ و $AC$ حداقل یکی (مانند $AB$) و از دو جاده‌ی $AE$ و $AD$ نیز حداقل یکی (مانند $AE$ ) قبل از طرح توسعه موجود بوده‌اند. بنابراین باید بعد از طرح توسعه جاده‌ای مانند $BE$ تاسیس می‌شد که نشده است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
