المپدیا

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

ابزار کاربر

ابزار سایت


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

توپ‌ها

یک دنباله‌ی نامتناهی از جعبه‌ها با شماره‌های $\ldots, -2, -1, 0, 1, 2, \ldots$ داریم. دقیقن $n$ تا از جعبه‌ها توپ سیاه و $n-1$ تا از آن‌ها توپ سفید دارند و بقیه‌ی جعبه‌ها خالی هستند. شکل زیر، مثالی برای $n=3$ است:

هر گاه تمام توپ‌ها در جعبه‌های متوالی قرار بگیرند؛ گوییم یک پیکره تشکیل شده است؛ برای مثال شکل زیر، پیکره‌ای برای $n=3$ است:

توجه کنید در یک پیکره، تنها نحوه‌ی قرار گرفتن توپ‌ها در کنار هم مهم است و شماره‌ی جعبه‌هایی که شامل توپ هستند، مهم نیست. برای مثال، پیکره‌ی بالا با پیکره‌ی زیر یک‌سان در نظر گرفته می‌شود:

در هر مرحله می‌توانیم دو توپ مجاور ناهم‌رنگ در نظر بگیریم و آن دو را به همان ترتیبی که دارند، به دو جعبه‌ی خالی متوالی ببریم. شکل زیر، مثالی برای انجام یک گام است:

دو پیکره‌ی $A, B$ را در نظر بگیرید. ثابت کنید می‌توان با متناهی گام از پیکره‌ی $A$ به پیکره‌ی $B$ رسید.


ابزار صفحه