Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

ثابت کنید : |A|n2|P|3


ابزار صفحه