اکسترمال 4

جزوه اکسترمال از سایت المپیاد رشد که ترجمه فصل سوم کتاب استراتژی های حل مسئله است. به همراه اصل کتاب در زیر آمده است:

جزوه اکسترمال المپیاد رشد

کتاب استراتژی های حل مسئه

جاده های خاکی

در یک استان 1000 شهر وجود دارد که بین هر دو شهری دقیقا یک مسیر خاکی وجود دارد. ثابت کنید دولت می تواند بعضی از جاده ها را آسفالت کند به طوری که به هر شهر فرد تا جاده آسفالت وصل باشد.

راه حل: 

اکسترمال 3

مثال 5 : رخ هایی روی صفحه شطرنج  قرار دارند. واضح است که  رخ کمترین تعداد رخی می باشد که تمام خانه های شطرنج  را تهدید می نماید. اما درباره  چه می توان گفت که بتوانند خانه های شطرنج   را تهدید کند. 

مثال 6 : در چهاروجهی با سه یال همرس می توان یک مثلث ساخت. 

مثال 7 :   مجموعه نقاطی از صفحه است. هر نقطه وسط دو نقطه دیگر است. ثابت کنید مجموعه ای نامحدود است.   

مثال 8 : هفت کوتوله دور یک میز دایره ای نشسته اند.در برابر هر یک از آنها، فنجانی قرار دارد.در برخی از فنجان ها شیر هست،روی هم 3 لیتر. یکی از کوتوله ها شیرش رابه طور یکسان میان دیگر فنجان ها قسمت می کند.در فرآیندی پاد ساعتگرد،هر یک از کوتوله ها به نوبت همان کار را انجام می دهند. بعد از آن که کوتوله ی هفتم شیرش را قسمت کرد،محتویات آغازین هر فنجان بازگردانده می شود.میزان آغازین شیر را در هر یک از فنجان ها بیابید.

مثال 9 : در یک پنج ضلعی محدب می توان سه قطر انتخاب کرد که اضلاع یک مثلث باشند 

مثال 10 : عدد های طبیعی را از 1 تا 64 روی خانه های یک صفحه شطرنج به ترتیب نوشته ایم.  (از 1 تا 8 را از چپ به راست در سطر اول و به همین ترتیب تا سطر هشتم.) قبل از تعداد از عدد ها علامت بعلاوه و قبل از بعضی علامت منها را طوری نوشته ایم که در هر سطر و هر ستون 2 تا بعلاوه و 4 تا منها وجود دارد. ثابت کنید مجموع عددهای نوشته شده برابر صفر است.

مثال 11 :  ثابت کنید تعداد رشته های باینری n تایی به طوری که هر دوتا حداقل در سه مکان متفاوت باشند حداکثر (1+2ⁿ) / (n) است .

مثال 12 :  سه مدرسه مفروض است که در هر یک از سه مدرسه n دانش آموز وجود دارد . هر دانش آموز جمعن n+1 دوست از دو مدرسه دیگر دارد . ثابت کنید می توانیم یک نفر از هر مدرسه انتخاب کنیم به طوری که این سه نفر دو به دو با هم دوست باشند .

مثال 13 :  9 شکل مسطحه داریم که مساحت هر کدام 1 است. آنها را طوری در صفحه قرار داده ایم که مساحت شکل حاصل 5 شده است.ثابت کنید 2 شکل وجود دارد که اشتراک مساحتشان بزرگتر یا مساوی 1/2 است.

مثال 14 : ماشینی در مسیر دایره ای قرار دارد.مقداری بنزین به طور ناهمگن در مسیر ریخته شده است.(ممکن است در نقطه هایی از مسیر اصلا بنزینی وجود نداشته باشد.)باک ماشین در ابتدا خالی است.ماشین از هر نقطه ای از مسیر عبور کند تمام بنزین آن نقطه را در باک خود جمع می کند.اگر کل بنزین ها را جمع کنیم دقیقا به اندازه ی یک دور ماشین است.ثابت کنید نقطه ای در مسیر وجود دارد که اگر از آن نقطه شروع به حرکت کند می تواند دقیقا 1 دور مسیر را بپیماید.

مثال 15:  ثابت کنید برای اعداد صحیح مثبت معادله زیر جواب ندارد. 

چالش بین P و NP

کسانی که با الگوریتم ها در گیر هستند می دانند که تحلیل یک الگوریتم (به لحاظ زمانی) در پیاده سازی و پیچیدگی آن الگوریتم اهمیت دارد در این رابطه مقاله زیر که به قلم دکتر رمضانیان (از اساتید دانشگاه شریف) است پیشنهاد می کنم.

مقاله

انشاالله در آینده در این مورد مطالب بیشتری را منتشر خواهم کرد.

موسیقی یا پیام جاسوسی

یک شبکه بزرگ جاسوسی از روش خاصی برای فرستادن پیام به ماموران و جاسوسان خود در فاصله های دور استفاده می کند؛ به این ترتیب که پیام های مورد نظر خود را به صورت دنباله هایی از ارقام صفر و یک رمزگذاری می کند و این دنباله ها را در قالب نت های موسیقی که صدای آن ها کم و زیاد می شود از طریق امواج معمولی رادیویی ارسال می کند. ماموران می دانند که کاهش طنین در موسیقی حاوی پیام به معنی صفر و افزایش آن نشانه ی یک است. در این جا حالت خاصی را در نظر می گیریم که در آن هر پیام یک دنباله ی چهارتایی از صفر و یک هاست (یک دنباله چهاربیتی).

این شبکه می خواهد برای 9 نفر از مامورانش پیام بفرستد، ولی از آنجا که زیاد شدن طول پیام احتمال شناسایی و کشف آن را زیاد می کند سعی می کند طول کل پیام ارسالی تا حد ممکن کوتاه باشد. به این دلیل، در صورت امکان پیام های مورد نظر خود را با هم ترکیب و یک جا ارسال می کند. مثلا هر گام بخواهد پیام 0110 را به یکی از ماموران و پیام 1011 را مامور دیگر بفرستد، می تواند آن ها را به صورت 011011 ترکیب و یک جا ارسال کند. البته در این حالت باید قبل از ارسال این پیام ترکیبی، به مامور اول اطلاع دهد که از رقم اول شروع به خواندن کند و به مامور دوم بگوید که از رقم سوم شروع به خواندن کند. برای اطلاع دادن محل شروع پیام هر مامور (شماره رقم آن) هم از نت موسیقی خاصی برای آن مامور استفاده می شود.

1- این شبکه می خواهد پیام های 0000 ، 0011 ، 0100 ، 0110 ، 0111 ، 1011 ، 1100 ، 1101 و 1110را به مامورانش بفرستد. متخصصی کد گذاری شبکه موفق به یافتن دنباله ای به طول 15 بیت برای ترکیب این 9 پیام شده اند. آیا شما می توانید دنباله ای به طول 14 یا کمتر بیابید که شامل همه این 9 پیام باشد؟

2- فرض کنید تعداد ماموران این شبکه از 9 نفر به 14 نفر افزایش پیدا کرده است. آیا می توانید دنباله ای 19 بیتی پیدا کنید که شامل هر مجموعه 14 تایی دلخواه از پیام های 4 بیتی باشد؟

3- آیا می توان یک دنباله 18 بیتی که 14 دنباله 4 بیتی مشخص که از قبل به شما داده شده اند، زیر دنباله های آن باشند؟ (به تفاوت این سوال و سوال قبل دقت کنید. در سوال قبل دنباله 19 بیتی باید شامل هر مجموعه دلخواه از مجموعه 4 بیتی باشد، ولی در این سوال 14 دنباله داده شده است که دنباله 18 بیتی باید شامل هر یک از آن ها باشد. نشان دهید که بدون توجه به این که 14 دنباله انتخاب شده، چه دنباله هایی هستند؛ می توانید دنباله 18 بیتی مورد نظر را تشکیل دهید.)

4- نشان دهید مجموعه هایی از 14 دنباله 4 بیتی وجود دارند که هیچ دنباله ای به طول 18 بیت یا کمتر شامل همه آن ها نیست.

منبع: معماهای الگوریتمی، دکتر قدسی و یاشار گنجعلی، انتشارات فاطمی