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

المپدیا

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

ابزار کاربر

ابزار سایت


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

توپ‌ها

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

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

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

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

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


ابزار صفحه