دوشنبه ۳۱ ارديبهشت ۱۴۰۳   |  كاربر مهمان  |    
 علوم و فنون جدید

 نظرسنجي شماره 1
در مورد كدام‌يك از موضوعات مطرح شده مايل به كسب اطلاعات بيشتر هستيد؟


ارائه نظر 
 انتخاب سلطان در جنگل! (مسابقه‌ي شماره‌ي 32)
انتخاب سلطان در جنگل! (مسابقه‌ي شماره‌ي 32)مسابقه كامپيوتر
در این مسابقه، سری به جنگل متمدنی زده‌ایم که برای انتخاب سلطان در آن انتخابات برگزار می‌شود! باز هم در جهت هدفمند شدن مسابقات، سعی کنید این مسابقه را با عنایت به گراف‌ها حل كنيد! ... سؤال همراه با جواب

انتخاب سلطان جنگل




 سؤال
در جنگلی 9 حیوان در لانه‌های‌اشان زندگی می‌کنند و دقیقاً یک راه جداگانه بین هر دو تا از این لانه‌ها وجود دارد.

پیش از مراسم انتخاب «سلطان جنگل»، برخی از حیوانات در مبارزه‌ی انتخاباتی شرکت مي‌کنند. هر نامزدي به هریک از لانه‌های دیگر دقیقاً یک‌بار سر می‌زند؛ فقط از راه‌های میان لانه‌ها برای رفت و آمد استفاده می‌کند.

هیچ‌گاه در مسیر بین دو لانه از هیچ راهی به راهی دیگر نمی‌پیچد و در پایان مبارزه‌ي انتخاباتی به لانه‌ی خودش باز می‌گردد.
هم‌چنین می‌دانیم که هیچ راهی بین دو لانه را بیش از یک نفر از نامزدها طی نکرده است.

تازه همه‌ی این‌ مطالبي كه گفته شد صورت مسابقه بود!

اما سؤال ما چیست!؟
باید بیش‌ترین تعداد نامزدها را پیدا کنید؟


 راهنمایی
مسأله را به‌زبان«گراف» بر گردانید و فرض کنید که هر لانه یک رأس باشد و هر راه میان دو لانه،«یالی» بوده که این دو رأس را به‌هم وصل می‌کند.

 جواب
مسأله را به‌زبان گراف برمی‌گردانیم. فرض کنید که هر لانه یک راس باشد و هر راه میان دولانه (دو رأس) یالی باشد که این دو رأس را به‌هم وصل می‌کند.

به این ترتیب گراف کامل  را به‌دست می‌آوریم. بیش‌ترین تعداد دورهای همیلتونی در این گراف کامل را می‌خواهیم که یال مشترک نداشته باشند (هیچ راهی بین دو لانه را بیش از یک‌نفر نامزد طی نکرده است).

به‌سادگی می‌توان تحقیق کرد که تعداد دورهای همیلتونی در این گراف، از تعداد رأس‌ها کم‌تر است. بنابر این همواره می‌توانیم برای هر دور همیلتونی، یک نامزد انتخاب کنیم.

نتیجه‌ی کلی این است که در گراف کامل ،  دور همیلتونی جدا از هم وجود دارد:

در مسأله n=9 است. بنابراین تعداد دورهای همیلتونی از رابطه‌ی ، 4 تا می‌شود. در نتیجه بیش‌ترین تعداد نامزدها 4تاست.

برای اثبات رابطه‌ي  به‌شکل ذيل عمل می‌کنیم:

چون در گراف کامل ،  یال وجود دارد و هر دور همیلتونی n یال دارد حداکثر  دور همیلتونی در  وجود دارد.

حالت‌های ذيل را در نظر می‌گیریم:


حالت 1 - n فرد است
فرض کنید به‌ازای عدد طبیعی مانند: k ،n=2k+1 (چون حالت n=1 بی‌معنی است). رأس‌های  را به‌ترتیب در جهت ساعتگرد روی دایره‌ای به فاصله‌های برابر می‌چینیم و رأس  را در مرکز دایره قرار می‌دهیم.

اولین دور همیلتونی

است.

می‌توانیم این دور را با زاویه‌های  در جهت ساعتگرد بچرخانیم و k-1 دور دیگر به‌دست بیاوریم که در مجموع تعداد دورها برابر می‌شود با:


 




حالت 2 - n زوج است
فرض می‌کنیم که به‌ازای اعداد طبیعی مانند: k ،n=2k+2. رأس‌های  را به‌ترتیب در جهت ساعتگرد روی دایره‌ای به فاصله‌های برابر می‌چینیم و رأس  را در مرکز دایره قرار می‌دهیم.

می‌توانیم رأس  را جایی درون دایره قرار دهیم. در هر دور همیلتونی که در حالت 1 تعریف کردیم،  را سمت راست وسط این دور قرار می‌دهیم و به این ترتیب  را به‌دست می‌آوریم.

 

1386/2/24لينک مستقيم
فرستنده :
دبیر سرویس المپیاد کامپیوتر HyperLink HyperLink 1386/6/10
مـتـن : man nemidonam in soalha chian ke shoma tarh mikonid avaze inke zehne ensan tagviat beshe kami ham sot mikeshe va khengtar mishe!!!!
پاسـخ : تاريخ پاسخ: 09/06/1386
فرستنده :
HyperLink HyperLink 1386/5/19
مـتـن : سلام
من ازشما یه سوال داشتم و اون اینکه چرا اونهای که رشته شون انسانی رو آدم حساب نمی کنید؟
پاسـخ : با سلام به شما برادر بزرگوار
اگر منظور اين سؤال‌اتان اين است كه چرا به «»المپياد ادبي» نمي‌پردازيم مي‌توانيد از مسؤولين محترم سايت رشد اين تقاضا را داشته باشيد.
قطعاً در صورت صلاحديد و بالا رفتن تقاضاها، به آن به‌شكل مناسب و برنامه‌ريزي شده‌اي، جواب مساعد خواهند داد.
فرستنده :
hamed HyperLink HyperLink 1386/4/26
مـتـن : 8
پاسـخ : سلام حامد جان !
چقدر مختصر !!!
متاسفانه جواب شما نادرست است و تازه اگر درست هم بود شما هم مثل آقا محمود هیچ راه حلی ارائه نداده بودید و فقط یه عدد گفته بودید.
شما می تونید جواب صحیح را در این قسمت مشاهده کنید.
موفق باشید.
فرستنده :
مولی HyperLink HyperLink 1386/4/26
مـتـن : سلام . من یه اشتباه کوچک در قسمت دوم جوابم کرده ام. در آنجا گفتم که به هر راس 2 یال متناظر می کنیم. اما درست این است که به هر راس 2 درجه متناظر خمی کنیم. این طوری 72 درجه داریم که اگر بر 18 یعنی تعداد درجه مورد نیاز برای هر دور همیلتونی مجزا تقسیم کنیم، تعداد دورهای همیلتونی مجزا از هم می شود 4. پس حداکثر 4 نامزد می توانیم داشته باشیم. متشکرم.
پاسـخ : به به آقا مولی !
آدم لذت می بره این جوونا رو می بینه !
بله جواب شما کاملا درسته شما برنده این مسابقه شدید.
آفرین.
فرستنده :
محمد محمودی HyperLink HyperLink 1386/4/26
مـتـن : بیشترین تعداد نامزد باید 4 تا باشه .
پاسـخ :سلام محمد جان ، جوابی که دادی درست است ولی کامل نیست . چون هیچ دلیل و بر هانی واسه جوابت نیاوردی و اصلا نگفتی که از کجا به این جواب رسیدی.
الان می تونی جاب را بخونی.
موفق باشی !
فرستنده :
ناشناس HyperLink HyperLink 1386/4/26
مـتـن : يکي بگه اين جا دقيقا دست کياست؟ يعني مي شه بگين سوالا و زنگ تفريحا و اينا رو دقيقا کي مي نويسه؟
پاسـخ :سلام دوست عزیز !
چی شده !؟
چرا انقدر عصبانی !؟
ما می تونیم این مسئله رو دوستانه حل کنیم !
مشکل کجای کاره ؟
اگه بگی ممنون میشم !
فرستنده :
ناشناس HyperLink HyperLink 1386/4/26
مـتـن : مسئله ها را جوری قرا دهید که کسی که می خواهد مسئله را بخواندبفهمد داره چه چیزی را دارد می خواند من که به همه مسئله ها رجوع کردم اصلاً معلوم نیست چی به چی ((( بعداً مسئله ها در حد دانش اموزان باشند نه در حد لیسانس ها که تجربه های زیادی رو کسب کرده اند
پاسـخ : سلام دوست عزیز ،
انتقاد شما تا حدودی به جاست واقعا از شما متشکریم که انقدر با دقت مسئله رو پی گیری کردید. در این مورد اگر هر گونه پیشنهادی برای بهتر شدن این قسمت دارید می تونید با در میان بذارین .
ممنون از توجهتون.
فرستنده :
مولی HyperLink HyperLink 1386/4/26
مـتـن : همانطور که از صورت سوال بر می آید، از آنجا که بین هر دو راس راهی جداگانه وجود دارد، پس اگر همانطور که شما گفتید گرافی با شرایط شما بسازیم، آن گراف گرافی کامل خواهد بود. و از آنجا که هر نامزد باید از خانه خود شروع و از همه راس ها بگذرد و به خانه خود برگردد، پس باید از خانه هر نامزد یک دور همیلتونی وجود داشته باشد. گفته شد که گراف کامل است، پس تعداد یال ها برابر است با تعداد اضلاع 9 ضلعی + تعداد اقطار 9 ضلعی که به راحتی بدست می آید و آن را x می نامیم. در واقع سوال از ما تعداد دورهای همیلتونی مجزا از هم را میخواهد. من الان وقت کافی ندارم. شاید بعدا ادامه جواب را برایتان فرستادم.

ادامه‌ی جواب: گقتم که برای پیدا کردن جواب سوال، باید تعداد دورهای همیلتونی مجزا از هم را در یک گراف کامل 9 راسی پیدا کرد. می دانیم که تعداد اضلاع و قطر ها در یک n ضلعی برابر ترکیب 2 شی از n شی است و چون در اینجا n=9 پس تعداد اضلاع و اقطار برابر ترکیب 2 شی از 9 شی است که می شود 36. اما برای اینکه یک دور همیلتونی بسازیم، باید از تمام راس های این 9 ضلعی بگذریم و برای این کار، باید 1 بار به هر راس وارد و 1 بار از هر راس خارج شویم. پس به هر راس 2 یال متناظر می کنیم یکی برای ورود و دیگری برای خروج. چون 9 راس داریم پس برای به وجود آمدن هر دور همیلتونی باید 18=2*9 یال داشته باشیم و چون کلا 36 یال داریم، پس با این تعداد یال می توانیم حداکثر 2 دور همیلتونی مجزا داشته باشیم پس بیشترین تعداد نامزدها برابر است با 2.
متشکرم.
پاسـخ :سلام آقا مولی !!
مثل اینکه اخورده هل شدی آ !!
جوابی که بعدا دادی جواب درسته !!
باریکلااااا !!
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف

 فعاليت هاي علمي
 تماس با ما
 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)