متن زیر را با دقت بخوانید.

در نقشهٔ زیر، $10$ «شهر» با دایره‌های کوچک و $15$ «جاده» بین آنها با پاره‌خط نشان داده شده‌اند. منظور از یک «جاده»، پاره‌خطی مانند $AB$ است که دو رأس آن، روی دو شهر باشد. می‌دانیم که فقط در شهرها می‌توان از یک جاده به جادهٔ دیگر رفت.

با توجه‌به متن بالا، به پرسش‌ زیر پاسخ دهید.


دربارهٔ درستی جملات زیر چه می‌توان گفت؟
الف: می‌توانیم از یک شهر شروع به حرکت کنیم و بدون اینکه از شهر تکراری عبور کنیم، همهٔ $9$ شهر دیگر را ببینیم.
ب: می‌توانیم از یک شهر شروع به حرکت کنیم و بدون اینکه از شهر تکراری عبور کنیم، $9$ شهر دیگر را ببینیم و دوباره به همان شهر اول برگردیم.
۱) هر دو جمله درست است.
۲) تنها جملهٔ «الف» درست است.
۳) تنها جملهٔ «ب» درست است.
۴) هیچ‌یک درست نیستند.


راهنمای حل

جملهٔ «الف» درست است. (چرا؟)

توجه کنید با اینکه با اندکی آزمون و خطا می‌توان تقریباً مطمئن شد که جملهٔ «ب» نادرست است، اما در اینجا می‌خواهیم اثبات دقیق و کاملی برای نادرستی جملهٔ «ب» بیاوریم.

فرض کنیم مسیری به نام «مسیر \(X\)» وجود داشته باشد که از یک شهر شروع شود و بدون اینکه از شهری تکراری عبور کند، $9$ شهر دیگر را بپیماید و دوباره به همان شهر اول برگردد؛ یعنی جملهٔ «ب» درست باشد. در ادامه، با بررسی حالت‌های مختلف نشان می‌دهیم که چنین چیزی امکان‌پذیر نیست؛ یعنی مسیر \(X\) نمی‌تواند وجود داشته باشد.

مسیر \(X\) می‌تواند از هر شهری شروع شود. (چرا؟)

فرض کنیم مسیر \(X\) با جادهٔ \(IA\) شروع شود. بنابراین، از شهر \(A\) یا باید شهر \(B\) برویم یا به شهر \(E\). به‌دلیل تقارن موجود در شکل، فرقی نمی‌کند که مسیر ما با \(IAB\) شروع شود یا با \(IAE\). فرض می‌کنیم که مسیر \(X\) با \(IAB\) شروع شده باشد.

حال، از شهر \(B\) یا باید به شهر \(C\) برویم یا به شهر \(G\). واضح است که در مسیر \(X\) باید راهی وجود داشته باشد که با استفاده از آن بتوان از \(C\) به \(G\)، یا از \(G\) به \(C\) رفت به‌طوری‌که شهرهای \(I\)، \(A\)، و \(B\) را ندید. (چرا؟)

در نتیجه، برای بررسی همهٔ راه‌هایی که می‌توان از \(G\) به \(C\)، یا از \(C\) به \(G\) رفت، نیازی به شهرهای \(I\)، \(A\)، و \(B\)، و جاده‌های متصل به آنها نداریم.

حالت اول: \(GFJC\).

در این حالت، مسیر \(X\) نمی‌تواند وجود داشته باشد. (چرا؟)

حالت دوم: \(GFEDC\)

در این حالت، مسیر \(X\) نمی‌تواند وجود داشته باشد. (چرا؟)

حالت سوم: \(GHDC\)

در این حالت، مسیر \(X\) نمی‌تواند وجود داشته باشد. (چرا؟)

حالت چهارم: \(GHDEFJC\)

در این حالت، مسیر \(X\) نمی‌تواند وجود داشته باشد. (چرا؟)

در نتیجه، جملهٔ «ب» نادرست است.

بنابراین، گزینهٔ ۲ درست است.


نوشته‌های قبلی و بعدی


اشتراک
اطلاع از
شماره موبایل شما نمایش داده نمی‌‌شود.

0 پرسش‌ها و نظرات
Inline Feedbacks
مشاهده همه نظرات