نکته: در این پاسخ سعی شده کلیت رسیدن به اثبات توضیح داده شود و نه اثبات دقیق.

الف) یکی از روش‌های خوب حل مسئله، بررسی مثال‌های کوچک است.

• $n=3$: شهر مبدا و مقصد را با یک واسطه بهم متصل می‌کنیم. هزینه برابر $1+2+1$ است.
• $n=4$: شهر مبدا و مقصد را به دو شهر دیگر متصل می‌کنیم و آن دو شهر را هم به یکدیگر متصل می‌کنیم: $2+3+2$
• $n=5$: شهر مبدا و مقصد را به سه شهر دیگر متصل می‌کنیم و آن سه شهر را هم دو به دو به یکدیگر متصل می‌کنیم: $3+4+3$

بنابراین برای حالت کلی باید همه‌ی شهرها به جز شهر مبدا و مقصد دو به دو متصل باشند. در این صورت در شهر مبدا و مقصد $n-2$ هزینه می‌دهیم و برای رسیدن از مبدا به مقصد باید از حداقل یک شهر با هزینه‌ی $n-1$ عبور کنیم. یعنی در مجموع $3n-5$

ب) برای این قسمت هم اگر چند مثال کوچک را بررسی کنیم متوجه می‌شویم اگر گاوی بین هر دو شهر دلخواهی کوتاه‌ترین مسیر را طی کند، هزینه‌اش از $3n-5$ بیشتر نمی‌شود.

در مسئله‌هایی که به کوتاه‌ترین مسیر مربوط می‌شوند، یکی از روش‌های خوب فکرکردن تقسیم کردن راس‌ها در طبقه‌هایی برحسب فاصله آنها از راس مبدا است. مثلا در شکل زیر رئوس به ترتیب فاصله‌شان از راس مبدا چیده شده‌اند و آنهایی که در یک ردیف هستند، فاصله‌شان از مبدا مساوی است.

در این تقسیم‌بندی، ویژگی مهم این است که یال‌ها (یا همان جاده‌ها) فقط بین دو راس از یک طبقه یا دو راس از دو طبقه‌ی متوالی وجود دارد. زیرا اگر قرار باشد دو راس که فاصله‌شان بیشتر از یک طبقه هست به هم یال داشته باشند، آنگاه شرط مرتب بودن طبقات برحسب فاصله نقض می‌شود. بنابراین اگر تعداد رئوس طبقه‌ی $i$ام را با $A_i$ نشان دهیم، درجه (یا همان تعداد شهرهای مجاور) یک راس در طبقه‌ی $i$ حداکثر $A_{i-1} + A_i + A_{i+1} - 1$ است (منهای یک به خاطر اینکه خود راس را نشماریم).

حال اگر گاوی از شهر مبدا به شهر مقصد کوتاه‌ترین مسیر را طی کند، از هر طبقه حداکثر یک‌بار رد می‌شود. بنابراین هزینه‌ای که باید بپردازد حداکثر این است:

• در طبقه‌ی مبدا: $A_1$
• در طبقه‌ی اول: $A_1 + A_2$
• در طبقه‌ی دوم: $A_1 + A_2 + A_3 - 1$
• در طبقه‌ی سوم: $A_2 + A_3 + A_4 - 1$
• ...
• در طبقه‌ی $k$ام: $A_{k - 1} + A_k + A_{k + 1} - 1$

اگر این مقادیر را باهم جمع بزنیم، باتوجه به اینکه هریک از $A_i$ها حداکثر در مجموع ۳ طبقه محاسبه می‌شوند، مجموع کل این عبارت حداکثر $3n-5$ می‌شود. البته برای اثبات دقیق باید نشان دهیم چرا $5$ واحد کمتر از $3n$‌ می‌شود و باید مواردی مثل اینکه در هر طبقه یک واحد کم می‌کنیم و همچنین طبقه‌ی اول و آخر دوبار محاسبه می‌شوند را بررسی کنیم.

سلام

کلیت مساله همانطور که واضحه خوب گرافه !

الف ) قسمت الف این سوال ساده ترین بخش مرحله دو امسال و خوب کم امتیاز ترینشون هم بود چون نیاز به هیچ اثباتی نداره و فقط باید یک روش خاص رو مطرح کنی

روش این است :

ما میتونیم 3n-5 رو به 3 راس اختصاص بدیم یعنی دو راس n-2 درجه ای و یک راس n-1 درجه ای

اگر فرض کنیم گاوی و ببعی در دو شهر a و b باشند قطعا باید درجه راس این دو شهر باید n-2 باشد چون اگر بیشتر باشد مسیری کوتاه تر از 3 راس پیدا خواهیم کرد

پس a را به غیر از b به تمام راس های دیگروصل میکنیم و برای b نیز به همین صورت عمل میکنیم و راس های دیگر ( همه ی راس ها به غیر از a و b ) را به یک گراف کامل تبدیل خواهیم کرد و به این صورت برای رسیدن از a به b در روش مد نظر 3n-5 تومان باید هزینه کنیم !

ب)فرض میکنیم مسیر رسیدن از a به b دقیقا k راس داشته باشد آنگاه این مسیر دقیقا k-1 یال دارد که هر کدام به مجموع درجه راس های مسیر دقیقا 2 واحد اضافه میکنند و از راس های بیرون مسیر هم 3 یال بیشتر به داخل مسیر نمیتواند بیاید و این 3 یال هم دقیقا باید به 3 راس مجاور درون مسیر وصل باشند چون اگر حداقل یک شرط از دو شرط برقرار نباشد ( بیشتر از 3 یال یا 3 یال غیر مجاور ) آنگاه مسیری پیدا خواهد شد که طول آن کم تر از k راس است ( اثبات بصورت شکلی است ) و برای این که درجه راس مسیر ماکزیمم شود باید حتما از هر راس بیرون مسیر دقیقا 3 یال با شروط بالا به داخل مسیر وارد شود پس مجموع کل درجات مسیر برابر است با:

2k−2)+3×(n−k)=3n−k−2)

اگر مسیر ما متشکل از دو راس باشد هر کدام حداکثر n-1 میتواند درجه راسشان باشد که مجموعا میشود 2n-2 و با حل نامعادله 2n-2 > 3n-5, جواب فقط برای n های کوچکتر از 2 درست که خود مساله به ازای n>2 طراحی شده و به ازای آن بیشترین درجه راس برابر با کمترین مقدار k است که برابر 3 و مجموع درجه راس مسیر 3n-5 میشود

ممنون

سلام

پاسخ رسمی کمیته ی المپیاد کامپیوتر(با اندکی ویرایش):

کشور مورد نظر را به گراف مدل کنید. به جای هر شهر یک رأس و به جای هر جاده یک یال در نظر بگیرید. ارزش یک شهر برابر با درجه ی رأس متناظر با آن است. هزینه ی یک مسیر نیز برابر است با مجموع درجات راس های داخل مسیر.

الف)

یک گراف کامل را در نظر بگیرید. یال بین دو راس $a$ و $b$ را از این گراف جدا کنید. حال ببعی را در راس $a$ و گاوی را در راس $b$ قرار دهید. اکنون هزینه سفر برابر است با:

$$n-2+n-2+n-1=3n-5$$

ب)

فرض کنید ببعی در راس $a$ و گاوی در راس $b$ است. کوتاه ترین مسیر را از $a$ به $b$ در نظر بگیرید. به جز یال های خود مسیر بین هیچ دو راسی داخل مسیر یال نخواهیم داشت چون اگر یال باشد مسیر کوتاه تر می شود. هر راس خارج از مسیر نیز حداکثر سه یال به راس های داخل مسیر دارد، چون در غیر این صورت دوباره مسیر کوتاه تری می توانستیم پیدا کنیم. حال مجموع درجات راس های داخل مسیر را می شماریم. به ازای هر یال داخل مسیر به مجموع درجات دو واحد اضافه می شود. به ازای هر یال از یک راس خارج از مسیر به یک راس داخل مسیر هم یک واحد به مجموع درجات اضافه می شود. اگر تعداد راس های درون مسیر $k$ باشد، هزینه کل ما حداکثر برابر است با:

$$2×(k-1) +3×(n-k)=3n-k-2$$

اگر $k>2$ باشد که سوال حل است. در غیر این صورت، مسیر ما فقط متشکل از دو راس بوده است که هر کدام حداکثر می توانستند درجه ای حداکثر برابر با $n-1$ داشته باشند. پس در آن صورت هزینه کل ما برابر با $2n-2$ می شد که با توجه به اینکه $n>2$ است، $2n-2 \ge 3n-5$ است.