المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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


ابزار صفحه