سوال ۹
نقشه‌ی خیابان‌های شهری به شکل مقابل است. (خیابان‌های عمودی
رو به بالا یک‌طرفه‌اند.)
می‌خواهیم اتومبیل‌های ۱ تا ۴ را به گاراژهایی که در شکل نشان داده شده است ببریم به طوری که از هر خیابان حداکثر یک اتومبیل عبور کند.
کدام یک از دنباله‌های زیر (از چپ به راست) می‌تواند شماره‌های اتومبیل‌ها در گاراژهای ۱ تا ۴ باشد؟
- $1, 3, 4, 2$
- $3, 1, 4, 2$
- $2, 1, 4, 3$
- $2, 3, 1, 4$
- هیچکدام
پاسخ
گزینه (؟) درست است.
نقشه‌ی خیابان‌ها شامل ۱۲ خیابان عمودی و ۱۲ خیابان افقی است. بدیهی است که برای رسیدن به گاراژها هر کدام از اتومبیل‌ها سه خیابان عمودی و در مجموع ۱۲ خیابان عمودی را طی می‌کنند. پس تمام ۱۲ خیابان عمودی توسط اتومبیل‌ها طی می‌شود. دو ستون اول را در نظر می‌گیریم. فرض می‌کنیم اتومبیل شماره ۱ از خیابان افقی شماره $(1 \leq i \leq4)i$ به سمت راست رفته و یکی از اتومبیل‌های دیگر از خیابان افقی شماره $(1 \leq j \leq4)j$ به سمت چپ برود. بدیهی است که $i\neq j$. 
زیرا در غیر این صورت از این خیابان یک ماشین به سمت چپ و یک ماشین به سمت راست رفته است که مخالف فرض است.
اگر $j>i$٬ آن‌گاه در ستون اول خیابان عمودی بین سطر $i$ و $j$ توسط هیچ اتومبیلی طی نمی‌شود و اگر $i>j$٬ آن‌گاه در ستون اول خیابان عمودی بین سسطر $i$ و $j$ توسط دو اتومبیل طی می‌شود که مخالف فرض است. بدین ترتیب ثابت می‌شود که اتومبیل $i$ فقط به گاراژ $i$ می‌تواند برود.