مسابقه‌ی تصادفی

 
 
 مسابقه‌ی فوتبال! (مسابقه‌ي شماره‌ي 31)
مسابقه‌ی فوتبال! (مسابقه‌ي شماره‌ي 31)مسابقه كامپيوتر
پس از یک‌سری مسابقه‌ی الگوریتمی محض و با توجه به استقبال شما و جواب‌های بی‌وقفه‌ی دوستان!تصمیم گرفتيم به‌سراغ چند مسأله‌ی تحلیلی برويم از آن دسته مطالبی که در المپیاد کامپیوتر به آن‌ها نیاز دارید! .. سؤال همراه با جواب

مسابقه‌ي فوتبال




  سؤال
این مسابقه باز هم در دنیای توپ گرد است! بیست و سه نفر که وزن هرکدام از آن‌ها «اعداد طبیعی» است می‌خواهند فوتبال بازی کنند. این عده یکی را به‌عنوان «داور» انتخاب كرده و سپس به دو تیم 11 نفره طوری تقسیم می‌شوند که «وزن کل» دو تیم برابر باشد. معلوم شده که «داور» هر که باشد می‌توان این کار را کرد.

حال شما چه كار بايد بكنيد!؟
با این اطلاعات بايد به ما ثابت کنید که وزن این بیست و سه نفر با هم برابر است!

راهنمایی
به‌نظر من در مرحله‌ي اول بیایید و فرض کنید که حکم مسأله درست نباشد و این بیست و سه نفر با هم «هم‌وزن» نباشند.

 
جواب
فرض کنید که حکم مسأله درست نباشد و 23 نفر وجود داشته باشند که وزن‌اشان برابر نباشد و شرط‌های مسأله در مورد آن‌ها برقرار باشد.

در این صورت، در میان چنین مجموعه‌هایی از افراد، مجموعه‌ای مانند:


وجود دارد که مجموع وزن افرادش یعنی ، کم‌ترین مقدار ممکن است.

اگر  داور باشد آن‌وقت ، که در آن  وزن کل هریک از تیم‌هاست.

با توجه به آن‌چه گفته شد، ، یعنی زوجیت ها یکسان است.

اگر ها همگی زوج باشند می‌توان A را با:


جایگزین کرد که مجموعه‌ای است که وزن کلش کم‌تر است و شرط‌های مسأله در مورد آن برقرار است و چون ها همگی برابر نیستند، ها هم همگی برابر نیستند.

این‌هم با فرض این‌که A مجموعه‌ای است که وزن کلش کم‌ترین مقدار ممکن است تناقض دارد.

اگر ها همگی فرد باشند می‌توانیم از مجموعه‌ی ذيل استفاده کنیم و مانند حالت قبل به‌تناقض برسیم:


بنابراین فرض‌امان غلط است و وزن هر 23 نفر با هم برابر است!

1386/2/16لينک مستقيم

فرستنده :
مولی HyperLink HyperLink 1386/4/26
مـتـن : فرض کنید حکم نادرست باشد و 23 نفر وجود داشته باشند که وزنشان برابر نباشد و شرطهای مساله در مورد آنها برقرار باشد. در این صورت در میان چنین مجموعه هایی از افراد مجموعه ای مانند {A={a1,a2,a3,...,a23 وجود دارد که وزن کل افرادش یعنیw=a1+a2+a3+...+a23 کم ترین مقدار ممکن است. اگر ai داور باشد، آن وقت w-ai=2si که در آن si وزن کل هریک از تیم هاست . بنابراین (به پیمانه 2)ai=w یعنی زوجیت ai ها یکسان است. اگر ai ها همگی زوج باشند می توان A را با{ A'={a1/2,a2/2,...,a23/2 جایگزین کرد، که مجموعه ای است که وزن کلش کمتر است و شرط های مساله در مورد آن برقرار است و چون ai ها همگی برابر نیستند، پس ai/2 ها هم همگی برابر نیستند. این هم با این که A مجموعه ای است که وزن کلش کمترین مقدار ممکن است تناقض دارد. اگر ai ها همگی فرد باشند، می توانیم از مجموعه {A''={(a1+1)/2,(a2+1)/2,...,(a23+1)/2 استفاده کنیم و مانند قبل به تناقض می رسیم. بنابراین فرضمان غلط است و وزن هر 23 نفر برابر است. متشکرم.
پاسـخ :آفرین آقا مولی !
واقعا خیلی خوبه !
باز هم جواب کامل و درست دادی !
همینجوری ادامه بده !
خیلی خوبه !
باریکلااااااااا !!!!

فرستنده :
مهسا HyperLink HyperLink 1386/4/26
مـتـن : سلام
به نظر من مسابقه هاتون یکمی سخت شده ولی از قبل خیلی بهتره ، خیلی جالبه !
در مورد جواب مسابقتنوم باید بگم که منم با نظر مولی موافقم !
وزن هر 23 نفر برابر است .
ممنون !
پاسـخ :سلام مهسا خانوم ، شما قرار نبود از رو دست اقا مولی ببینی !
بله آقا مولی کاملا درست جواب داده و برای دومین بار پیاپی برنده ی مسابقه ی ما میشه !
باریکلا آقا مولی !
شما هم می تونی به زودی جواب درست مسابقه رو در این قسمت ببینی !
موفق باشی !

فرستنده :
سمیرا HyperLink HyperLink 1386/4/26
مـتـن : سلام
من حقیقتا اندر شگفتم با این سوال هایی که شما میدین اصلا چه نیازی به درس خوندنه !
چون در هر دو صورت به 1 نتیجه می رسیم !
خدافز !
پاسـخ :انتقاد شما تا حدودی به جاست واقعا از شما متشکریم که انقدر با دقت مسئله رو پی گیری کردید. در این مورد اگر هر گونه پیشنهادی برای بهتر شدن این قسمت دارید می تونید با در میان بذارین .
ممنون از توجهتون.

فرستنده :
آناهیتا HyperLink HyperLink 1386/4/26
مـتـن : به نظر من وزن همه با هم برابر است فرض میکنیم آقای Aوزن مینیموم و Bوزن ماکزیمم را دارد و آقای داور مسابقه میشود به طوری که وزن هر دو گروه برابر است .حال اگر جای AوB که میدانیم وزن آنها متفاوت است) را عوض کنیم تعادل به هم می خورد.پس به خلاف حکم می رسیم و وزن همه ی آن ها مساوی است.
پاسـخ : سلام آناهیتا جان ، ممنون که وقت گذاشتی و سعی کردی که جواب مسابقه را بدست بیاری ولی متاسفانه اشتباه کردی !
می تونی به زودی جواب درست مسابقه رو در این قسمت ببینی !
موفق باشی !

فرستنده :
حمیدرضا HyperLink HyperLink 1386/4/26
مـتـن : سوالات خیلی ساده ای دارید.
درصورتی که وزن مثلا 2 نفر برابر نباشد و این 2 نفر در 2 تیم باشند دراین
حال مساله اشتباه در می آید.
حااااااااااااااااااااااااااااااااااااااال کردی؟؟؟؟؟؟؟؟؟
پاسـخ : سلام حمید رضا جان !
حال کردم ولی جوابت غلط بود !!
می تونی به زودی جواب درست مسابقه رو در این قسمت ببینی !
موفق باشی !

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2429
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2429