سوال
نقشه‌ی خیابان‌های شهری به شکل مقابل است.(خیابان‌های عمودی رو به بالا یک طرفه‌اند) می‌خواهیم اتومبیل‌های ۱ تا ۴ را به گاراژ‌هایی که در شکل نشان داده شده است ببریم , به طوری که از هر خیابان حداکثر یک اتومبیل عبور کند. کدام یک از دنباله‌های زیر ( از چپ به راست ) می‌تواند شماره‌های اتومبیل‌ها در گاراژهای ۱ تا ۴ باشد ؟

الف ) ۲ و ۴ و ۳  و ۱
ب )‌ ۲و  ۴و ۱ و۳
ج ) ۳ و ۴ و ۱ و ۲
د ) ۴ و ۱ و ۳ و ۲
ه‍ ) هیچ‌کدام

پاسخ
نقشه خیابان‌ها شامل ۱۲ خیابان عمودی و ۱۲ خیابان افقی است. بدیهی است که برای رسیدن به گاراژها هر کدام از اتومبیل‌ها سه خیابان عمودیی و در مجموع ۱۲ خیابان عمودی را طی می‌کنند. پس تمام ۱۲ خیابان عمودی توسط اتومبیل‌ها طی می‌شود. دو ستون اول را در نظر می‌گیریم. فرض می‌کنیم اتومبیل شماره ۱ از خیابان افقی از خیابان افقی شماره i (۴ ≥ i ≥ ۱) به سمت راست رفته و یکی از اتومبیل‌های دیگر از خیابان افقی شماره j (۴ ≥ j ≥ ۱) به سمت چپ برود. بدیهی است که j ≠ i. زیرا در غیر این‌صورت از این خیابان یک ماشین به سمت چپ و یک ماشین به سمت راست رفته است که مخالف فرض است.
اگر i < j , آنگاه در ستون اول خیابان عمودی بین سطر i و j توسط هیچ اتومبیلی طی نمی‌شود و اگر j < i , آنگاه در ستون اول خیابان عمودی بین سطر i و  j توسط دو اتومبیل طی می‌شود که مخالف فرض است. بدین ترتیب ثابت می‌شود که اتومبیل i فقط به گاراژ i می‌تواند برود