سوالات المپیاد:مرحله ی اول:دوره ی ۸:سوال ۵۷
سوال ۵۷
۲۰ تیم به صورت دوره‌ای با هم بازی کرده‌اند (هر دو تیمی با هم دقیقاً یک بازی انجام داده‌اند)، جایگشتی از این تیم‌ها را داریم. اگر در این جایگشت دو تیم متوالی $x$ و $y$ باشند که $x$ از $y$ باخته باشد، جای $x$ و $y$ را عوض می‌کنیم. آیا این عمل می‌تواند تا بی‌نهایت ادامه داشته باشد؟
پاسخ
در ترتیب مورد نظر تمام زوج‌هایی مانند $(x,y)$ که $x$ از $y$ باخته و در آن ترتیب $x$ قبل از $y$(نه لزوما بلافاصله) را در نظر می‌گیریم. می‌دانیم این تعداد زوج عددی محدود است. باعمل اشاره شده در صورت مسئله٬ در هر مرحله تعداد زوج‌های مورد اشاره یکی کم شده و بالاخره بعد از مدتی به صفر خواهد رسید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
