در یک شهر کوچک دو شرکت تازه‌تاسیس برای جذب کارمند آگهی استخدام داده‌اند. آن‌ها می‌دانند دقیقاً $n$ نفر متقاضی کار در این شهر وجود دارد که همه‌ی آن‌ها ناگزیرند در یکی از این دو شرکت به کار مشغول شوند. هر یک از دو شرکت در آگهی استخدام خود٬ یک لیست با $n$ خانه درج کرده‌اند که مشخص می‌کند اگر آن شرکت $i$ کارمند ($1 \le i \le n$) داشته باشد٬ به هریک از آن‌ها چه حقوقی تعلق خواهد گرفت (حقوق همه‌ی کارمندان در یک شرکت مساوی و فقط به تعداد کارمندان آن وابسته است). توجه کنید که اعداد نوشته شده در هر یک از این دو جدول مثبت ولی دل‌خواه هستند و لزوماً هیچ ترتیب خاصی ندارند.

ثابت کنید که $n$ کارمند همواره می‌توانند طوری در این دو شرکت استخدام شوند که هیچ یک از کارمندان تمایلی به تغییر شرکت نداشته باشد. زمانی یک شرکت مایل به تغییر شرکت خود خواهد بود که در صورت این تغییر٬ میزان حقوقش افزایش یابد.

• سوال بعد