المپدیا

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

ابزار کاربر

ابزار سایت


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

گوی‌های باردار

$n$ گوی باردار داریم که $n$ عددی فرد است. همچنین زوجیت تعداد بارهای مثبت را هم می‌دانیم. در هر عمل می‌توانیم دو عدد از گوی‌ها را انتخاب و به هم نزدیک کنیم و هم‌نوع بودن بار آن‌ها رادریابیم. ثابت کنید برای آن‌که بار همه‌ی گوی‌ها را بدانیم همواره $n-1$ عمل از نوع بالا لازم و کافی است.


ابزار صفحه