Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

به ازای هر عدد طبیعی ‎i‎ یک جعبه با شماره‌ی ‎i‎ در نظر بگیرید. در ابتدا فرض کنید در جعبه‌ی ‎i‎ام، ‎ai‎ توپ قرار دارد که برای حداکثر ‎n‎ جعبه تعداد توپ‌ها بزرگ‌تر از صفر است. در هر گام می‌توانیم یک جعبه‌ی دلخواه را انتخاب کنیم و اگر تعداد توپ‌های این جعبه برابر با k (k>0)‎ بود، آن‌ ‎k‎ توپ را به جعبه‌ی شماره‌ی ‎k‎ منتقل کنیم. ثابت کنید حداکثر بعد از ‎2n1‎ بار تکرار این عمل به جایی می‌رسیم که تعداد توپ‌های هر جعبه برابر با صفر و یا شماره‌ی آن جعبه است.


ابزار صفحه