المپدیا

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

ابزار کاربر

ابزار سایت


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

مسیر فراگیر

شکل زیر شامل $2n$ دایره است که به وسیله‌ی $3n-2$ پاره‌خط به یک‌دیگر متصل شده‌اند.

می‌خواهیم یکی از دایره‌ها را انتخاب کنیم و با شروع از آن و حرکت روی پاره‌خط‌ها، از همه‌ی دایره‌ها بگذریم و در یک دایره (غیر از دایره‌ی اول) کار خود را خاتمه دهیم، به طوری که در طول حرکت هر دایره را دقیقا یک بار ملاقات کنیم. به عنوان نمونه اگر $n$ برابر ۶ باشد، شکل زیر یکی از مسیرهای ممکن را نشان می‌دهد. ثابت کنید تعداد مسیرهایی که در شرط‌های گفته شده صدق می‌کنند برابر $n^2-n+2$ است.


ابزار صفحه