المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۲:تئوری:سوال ۴

شبه مربع لاتین

یک شبه مربع لاتین عبارت است از یک جدول $n\times n$ که در تعدادی از خانه‌های آن اعدادی از مجموعه‌ی $\{1,2,…,n\}$ نوشته شده است و شرط لاتین بودن نیز حفظ شده است٬ یعنی هیچ دو عدد یکسانی در یک سطر و ستون ظاهر نشده است.

فرض کنید $P$ یک شبه مربع لاتین باشد که می‌توان آن را به یک مربع لاتین کامل گسترش داد. $A$ یک شبه مربع لاتین است که هیچ خانه‌ی مشترکی با $P$ ندارد و ضمنا $A\cup P$ هم یک شبه مربع لاتین است. همچنین می‌دانیم که هیچ خانه‌ی دیگری را نمی‌توان به $A\cup P$ اضافه کرد تا یک شبه مربع لاتین بزرگ‌تر به‌دست آورد.

ثابت کنید : $|A| \geq \frac{n^2-|P|}{3}$


ابزار صفحه