Processing math: 37%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

فرض کنید ‎n‎ یک عدد طبیعی فرد باشد. ‎۲‎ مربع لاتین متعامد (عمود بر هم) از مرتبه‌ی ‎n‎ مثال بزنید. ‎‎ فرض کنید ‎n‎ یک عدد طبیعی باشد. گراف ‎K_{n‎, ‎n}‎ را در نظر بگیرید. یک رنگ‌آمیزی یالی معتبر از آن را، ‎رنگارنگ‎ می‌گوییم اگر بتوان یال‌های گراف را به ‎n‎ تطابق کامل افراز کرد؛ طوری که هر تطابق از هر رنگ، دقیقن یک یال داشته باشد. ثابت کنید به ازای هر عدد طبیعی فرد ‎n‎، گراف ‎K_{n‎, ‎n}‎ یک رنگ‌آمیزی یالی معتبر با ‎n‎ رنگ دارد که رنگارنگ باشد.


ابزار صفحه