المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

کرکس‎‎ که از بازی‌های کامپیوتری خسته شده بود، به برادرش شی‌کرکس ‎‎ پیشنهاد داد که بازی‌ای شبیه فکربکر انجام دهند. کرکس ‎$n$‎ مهره با ‎$n$‎ رنگ مختلف را روی زمین می‌ریزد. و به شی‌کرکس می‌گوید که من ترتیبی از این مهره‌ها در ذهن خود دارم. اگر بتوانی به من ترتیبی بدهی که در آن، حداقل یکی از رنگ‌ها سرجای خودش باشد تو برنده می‌شوی و اما اگر ترتیب تو شرایط لازم را نداشت، باید ترتیب جدیدی ارائه دهی.

شی‌کرکس می‌خواهد تمام تلاش خود را انجام دهد و در کمترین حدس، ترتیب مناسبی را بدست بیاورد تا هوشش را به رخ کرکس بکشد. شما به او کمک کنید و کمترین ‎$t$‎ را بیابید که شی‌کرکس بتواند در بدترین حالت با ‎$t$‎ حدس، برنده شود. ادعای خود را باید اثبات کنید.


ابزار صفحه