المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۸:سوال ۱

تقسیم پول

مقداری پول را بین $n$ نفر تقسیم کرده‌ایم. عدد طبیعی $k$ را در نظر بگیرید؛ می‌خواهیم کاری کنیم که اختلاف مقدار پولی که این افراد دارند از $k$ تومان بیشتر نباشد. برای این کار عمل زیر را انجام می‌دهیم:

  • دو نفر مانند $a$ و $b$ پیدا می‌کنیم که $a$ حداقل $k+1$ تومان بیشتر از $b$ پول داشته باشد. سپس $a$ را مجبور می‌کنیم که $k$ تومان به $b$ بدهد.

این کار را تا وقتی که چنین دو نفری وجود داشته باشند٬ تکرار می‌کنیم. ثابت کنید به هر ترتیبی که این کار را انجام دهیم٬ بالاخره به حالتی خواهیم رسید که هیچ دو نفری وجود نداشته باشند که اختلاف مقدار پول‌شان از $k$ تومان بیشتر باشد.


ابزار صفحه