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

المپدیا

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

ابزار کاربر

ابزار سایت


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

ابهت

فرض کنید n و k دو عدد طبیعی باشند. به یک دنباله‌ی n تایی مانند A=a1,a2,,an با ابهت گوییم، اگر به ازای هر 1in داشته باشیم: ai{1,2,,k} دو دنباله‌ی با ابهت مانند A=a1,a2,,an و B=b1,b2,,bn را دوست گوییم، اگر به ازای دست کم یک 1in داشته باشیم ai=bi.

فرض کنید G یک گراف ساده باشد که هر رأس آن متناظر با یک دنباله‌ی با ابهت باشد و دو رأس در آن به هم وصل هستند، اگر دنباله‌های متناظرشان دوست باشند. بزرگ‌ترین خوشه‌ی G چند رأس (بر حسب n و k) دارد؟


ابزار صفحه