توجه!!: شاید خواندن این اثبات کمی سخت باشد.من اکیدا توصیه میکنم خودتان سعی کنید این موضوع را اثبات کنید که اگر چینشی دلخواه را در نظر بگیریم و بخواهیم کارمندان را یکی یکی منتقل کنیم تا به حالت مطلوب برسیم و در یک مرحله کارمندی از A به B برود، در حرکت بعدی ممکن نیست کارمندی از B به A برود. بقیه مسئله خود به خود حل میشود.

دو شرکت را A و B مینامیم.

[A[i برابر است با حقوقی که در شرکت A با i کارمند به هر کارمند تعلق میگیرد.[B[i نیز برابر است با حقوقی که در شرکتB با i کارمند به هر کارمند تعلق میگیرد.

کارمند ها را به طور اتفاقی تقسیم میکنیم فرض میکنیم شرکت A تعداد k کارمند و شرکت B تعداد l کارمند داشته باشد.

با الگوریتم زیر پیش میرویم که در آن کارمندان یکی یکی منتقل میشوند(چند کارمند با هم تغییر شرکت نمیدهند):

الف) [A[k+1]>B[l : پس کارمندی از شرکت B به A میرود.

ب) [B[l+1]>A[k : پس کارمندی از شرکت A به B میرود.

ج) [A[k+1]=B[l و [1+A[k]=B[l : به حالت مطلوب رسیده ایم.

از طرفی اگر در ابتدا حالت الف پیش بیاید دیگر تا انتها ممکن نیست حالت ب پیش بیابد.

اثبات:

اگر این طور نباشد اولین باری که حالت ب پیش آمده را در نظر میگیریم اگرپس از انتقال کارمند از A به B، شرکت A دارای k کارمند و شرکت B دارای l کارمند بوده باشد.پس داشته ایم: [B[l]>A[k+1 .میدانیم حالت قبل از این حالت ، الف بوده است.یعنی داشته ایم: [B[l]< A[k+1 که یک تناقض است.

پس الگوریتم همواره پایان می یابد.

موفق باشید!!

اثبات با بیان ساده تر :

فرض کنید شرکت اول A و شرکت دوم B است . و در یک چینش اولیه کاملا دلخواه ، تعداد اعضای A برابر n و تعداد اعضای B برابر m باشد .

چون در مسئله تقارن وجود دارد ، میتوانیم فرض کنیم که فردی از A میخواهد به B برود . خوب این فرد را انتقال میدهیم . حال تمام اعضای B ، حقوق m + 1 و تمام اعضای A ، حقوق n - 1 را در لیست دریافت میکنند . حال هیچ کارمندی از B نمیخواهد به A برود. چون در این مسئله افراد با هم متفاوت نیستند و اگر کسی بخواهد شرکتش را تغییر دهد ، همه میخواهند تغییر دهند . پس انگار که فردی که از A به B آوردیم ، میخواهد به A برگردد که همان حقوق قبلیش را دریافت میکند که میدانیم از حقوق الانش کمتر است. پس هیچ کس از B نمیخواهد به A برود.

حال تا جایی که همه اعضای A از حقوقشان راضی باشند ، افراد A را به B منتقل میکنیم . و چون هیچ کس در طول این حرکت از B یه A باز نمیگردد و اعضای A محدود هستند ، این کار روزی تمام میشود.

پس حالتی وجود دارد که تمام کارکنان دو شرکت راضی باشند.