یک محله شامل $nm$ خانه که به شکل یک شبکه‌ی $n\times m$ آرایش یافته‌اند، است. بدین ترتیب در این محله هر خانه در تقاطع یک خیابان افقی و یک خیابان عمودی قرار گرفته است. برای هر خانه یک پلاک شامل شماره‌ی خیابان عمودی و شماره‌ی خیابان افقی آن ساخته شده است. یک مامور شهرداری مسئولیت نصب پلاک‌ها را برعهده گرفته است. اما مشکل کار اینجا است که مامور حواس جمع ما به‌جز تعداد مجهولی، همه‌ی پلاک‌ها را جابه‌جا نصب کرده است. مردم محله وقتی متوجه عمل مامور خوش‌فکر می‌شوند، تصمیم می‌گیرند که مشکل خود را به‌دست خود حل کنند. از آن‌جایی‌که مبادله‌ی پلاک تنها بین خانه‌های یک خیابان عمودی یا افقی ممکن است، آن‌ها تصمیم می‌گیرند از روش سه مرحله‌ای زیر استفاده کنند.

1. مرحله‌ی اول: خانه‌های هر خیابان عمودی طوری پلاک‌های خود را جابه‌جا کنند که در هر خیابان افقی، از هر خیابان عمودی دقیقا یک پلاک آمده باشد.
2. مرحله‌ی دوم: خانه‌های هر خیابان افقی طوری پلاک‌های خود را جابه‌جا کنند که هر پلاک در خیابان عمودی مربوط به خود قرار گیرد.
3. مرحله‌ی سوم: خانه‌های هر خیابان عمودی طوری پلاک‌های خود را جابه‌جا کنند که هر پلاک به خانه‌ی مربوط به خود برسد.

ثابت کنید همواره اجرای سه مرحله‌ای روش فوق، یکی پس از دیگری ممکن است.

• سوال بعد
• سوال قبل