المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۲:سوال ۲

بازی

به یک جدول $n \times n$‎ یک مربع لاتین می‌گوییم، هرگاه در هر یک از خانه‌های آن یکی از اعداد ‎‎۱,‎۲‎,‎⋯‎,‎$n$‎ نوشته شده باشد و در هیچ سطر و هیچ ستونی عدد تکراری نداشته باشیم. فرض کنید $‎n‎$ عددی طبیعی و بزرگتر از ۱۰۰۰‎ است. !$n$ نفر روی یک مربع لاتین $n \times n$‎‎ دلخواه شروع به بازی می‌کنند. هر کس درنوبت خود می‌تواند جای دو سطر و یا دو ستون از جدول را با هم عوض کند. اولین کسی که حرکتی انجام بدهد که یک مربع لاتین تکراری‌ ایجاد شود بازنده‌ی بازی است و بقیه افراد برنده می‌شوند. ثابت کنید ۱-!$‎n$‎ نفر اول می‌توانند با هم تبانی کنند تا نفر ‎$n$!‎ام (آخرین نفری که حرکت اولش را انجام می‌دهد) بازنده شود.


ابزار صفحه