يك مدرسه، سه تالار اجتماع B ، A و C دارد. يك روز همه دانش‌آموزان در تالار A جمع شدند و معلوم شد هر دانش‌آموز حداقل s+t نفر را مي‌شناسد. بعد از اين تعدادي از دانش‌آموزان به تالار B و تعدادي به تالار C رفتند. مي‌دانيم كه در تالار B هر نفر حداقل s نفر را در همان تالار مي‌شناسد و در تالار C نيز هر نفر حداقل t نفر را در همان تالار مي‌شناسد. ثابت كنيد افرادي كه در تالار A مانده‌اند را مي‌توان به‌گونه‌اي بين دو تالار B و C تقسيم كرد، به طوريكه بعد از تقسيم باز هم هر نفر در تالار B لااقل s نفر را در همان تالار و هر نفر در تالار C لااقل t نفر را در همان تالار بشناسد. (فرض كنيد آشنايي يك رابطه دوطرفه است)
سوالي از مرحله دوم كامپيوتر (دوره نهم)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
همه ی افراد داخل A را به B منتقل می کنیم.پس از انتقال آنهایی که در B بیش از s نفر را بشناسند که مشکلی ندارند ، اما آنهایی که کمتر از s نفر را می شناسند چون حداقل s+t نفر از کل را می شناسند پس حداقل t نفر در C را می شناسند. این افراد را به C منتقل می کنیم. بدیهی است که حالا در C هیچکسی مشکلی ندارد ولی ممکن است در B برای عده ی دیگری مشکل پیش آمده باشد (تعداد آشنایانشان کمتر از s شده باشد) در این صورت آنها را هم به C منتقل می کنیم. این عمل نمی تواند تا بینهایت ادامه یابد.
من این سوال رو دیروز حل کرده بودم!
ضمنا اصلا نیازی به دوطرفه بودن آشنایی ها نیست!
من این سوال رو دیروز حل کرده بودم!
ضمنا اصلا نیازی به دوطرفه بودن آشنایی ها نیست!
