سوال ۶
نقشه‌ی خیابان‌های شهری به صورت شکل مقابل است.(هر یک از دایره‌ها نشان‌دهنده‌ی یکی از میدان‌های شهر و هر خط نشان‌دهنده‌ی یک خیابان است.) می‌خواهیم همه‌ی خیابان‌های این شهر را یک‌طرفه کنیم٬ به طوری که از هر یک از میدان‌های شهر با استفاده از این خیابان‌ها بتوان به هر میدان دیگری رفت.
به چند طریق می‌توان این کار را انجام داد؟
- ۳
- ۶
- ۸
- ۶۴
- ۱۲۸
پاسخ
گزینه (۲) درست است.
با توجه به شکل بدیهی است که جهت مسیرهای $AF،AB$ و $FE$ وابسته به هم‌دیگر و نیز جهت مسیرهای $CD،BC$ و $ED$ وابسته به هم می‌باشند؛ یعنی اگر جهت مسیر $AB$ از $A$ به سمت $B$ باشد٬ آن‌گاه مسیر $FA$ از $F$ به سمت $A$ و مسیر $EF$ از $E$ به سمت $F$ خواهند بود فلذا کافی است جهت مسیرهای منتهی به $B$ را تعیین کنیم در آن صورت جهت مسیرهای دیگر خودبه‌خود تعیین خواهند شد. پس تعداد حالات ممکن برابر با تعداد حالاتی است که می‌توان جهت مسیرهای منتهی به $B$ را تعیین کرد. جهت مسیرهای منتهی به $B$ یکی از حالات زیر است:
پس تعداد حالات ممکن برابر با ۶ می‌باشد.