سوال ۵۷

۲۰‎ تیم به صورت دوره‌ای با هم بازی کرده‌اند (هر دو تیمی با هم دقیقاً یک بازی انجام داده‌اند)، جایگشتی از این تیم‌ها را داریم. اگر در این جایگشت دو تیم متوالی ‎$x$‎ و ‎$y$‎ باشند که ‎$x$‎ از ‎$y$‎ باخته باشد، جای ‎$x$‎ و ‎$y$‎ را عوض می‌کنیم. آیا این عمل می‌تواند تا بی‌نهایت ادامه داشته باشد؟

پاسخ

در ترتیب مورد نظر تمام زوج‌هایی مانند $(x,y)$ که ‎$x$‎ از ‎$y$‎ باخته و در آن ترتیب ‎$x$‎ قبل از ‎$y$‎(نه لزوما بلافاصله) را در نظر می‌گیریم. می‌دانیم این تعداد زوج عددی محدود است. باعمل اشاره شده در صورت مسئله٬ در هر مرحله تعداد زوج‌های مورد اشاره یکی کم شده و بالاخره بعد از مدتی به صفر خواهد رسید.