المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۸:سوال ۳

مسیر فراگیر

یک شبکه‌ی $m \times n$ شامل $mn$ نقطه است که مطابق شکل زیر در $m$ ردیف و $n$ ستون قرار گرفته‌اند.

یک مسیر فراگیر در این شبکه٬ مسیری است که از نقطه‌ی گوشه‌ی بالا و سمت چپ آغاز شده٬ از هر نقطه‌ی شبکه دقیقاً یک بار عبور کند٬ و به نقطه‌ی گوشه‌ی پایین و سمت راست شبکه برسد. در طی این مسیر تنها مجازیم که از هر نقطه به یکی از نقاط سمت راست٬ چپ٬ بالا یا پایین آن (در صورت وجود) برویم.

ثابت کنید که مسیر فراگیر تنها در صورتی وجود دارد که دست‌کم یکی از $m$ و $n$ فرد باشد.


ابزار صفحه