پس از یکسری مسابقهی الگوریتمی محض و با توجه به استقبال شما و جوابهای بیوقفهی دوستان!تصمیم گرفتيم بهسراغ چند مسألهی تحلیلی برويم از آن دسته مطالبی که در المپیاد کامپیوتر به آنها نیاز دارید! .. سؤال همراه با جواب
سؤال
این مسابقه باز هم در دنیای توپ گرد است! بیست و سه نفر که وزن هرکدام از آنها «اعداد طبیعی» است میخواهند فوتبال بازی کنند. این عده یکی را بهعنوان «داور» انتخاب كرده و سپس به دو تیم 11 نفره طوری تقسیم میشوند که «وزن کل» دو تیم برابر باشد. معلوم شده که «داور» هر که باشد میتوان این کار را کرد.
حال شما چه كار بايد بكنيد!؟
با این اطلاعات بايد به ما ثابت کنید که وزن این بیست و سه نفر با هم برابر است! راهنمایی
بهنظر من در مرحلهي اول بیایید و فرض کنید که حکم مسأله درست نباشد و این بیست و سه نفر با هم «هموزن» نباشند.
جواب
فرض کنید که حکم مسأله درست نباشد و 23 نفر وجود داشته باشند که وزناشان برابر نباشد و شرطهای مسأله در مورد آنها برقرار باشد.در این صورت، در میان چنین مجموعههایی از افراد، مجموعهای مانند:
وجود دارد که مجموع وزن افرادش یعنی ، کمترین مقدار ممکن است.
اگر داور باشد آنوقت ، که در آن وزن کل هریک از تیمهاست.
با توجه به آنچه گفته شد، ، یعنی زوجیت ها یکسان است.
اگر ها همگی زوج باشند میتوان A را با:
جایگزین کرد که مجموعهای است که وزن کلش کمتر است و شرطهای مسأله در مورد آن برقرار است و چون ها همگی برابر نیستند، ها هم همگی برابر نیستند.
اینهم با فرض اینکه A مجموعهای است که وزن کلش کمترین مقدار ممکن است تناقض دارد.
اگر ها همگی فرد باشند میتوانیم از مجموعهی ذيل استفاده کنیم و مانند حالت قبل بهتناقض برسیم:
بنابراین فرضامان غلط است و وزن هر 23 نفر با هم برابر است!