شاززز

مساله اول: مهره ها......................................................................................................... 30 نمره

دو مساله زیر را در نظر بگیرید:

مسالهA: گرافGو تعدادی مهره روی بعضی رأس های آن داده شده است. می خواهیم مهره ها را روی یال ها طوری حرکت دهیم که زیر گراف القایی رأس های که شامل حداقل یک مهره اند همبند شده و مجموع حرکات مهره ها نیز کمینه شود.

مسألهB :
گراف2بخشىHکهمجموعه ی دو بخش آنXوYمى باشند دادهشده است. میخواهیم کوچیکترین زیر مجموعۀXمانندSرا پیدا کنیم بهطورى کهN(S)=Y
ثابت کنید اگر براى مسألهA الگوریتمچندجمله ایوجود داشته باشد براى مسألهBنیزالگوریتمچندجمله ایوجود دارد.

 

مساله دوم: رنگ کردن مربع ها........................................................................................... 35 نمره

 

nمربح به ضلح واحد طوری در صفحه قرار گرفته اند که اضلاع شان موازی محور های مختصات بوده و مختصات طولی یا عرضی هیچ دو مربعی برابر نیست. یک عددkبه شما داده شده است و به شما گفته شده که هیچk+1مربعی وجود ندارد که هر دوتایشان با هم اشتراک داشته باشند.

ثابت کنید می توان این مربح ها را با حداکثر2k-1رنگ,طوری رنگ کرد که رنگ هرمربعی که با هم اشتراک دارند متفاوت باشد.

 

مساله سوم: مجموعه........................................................................................................15 نمره

 

ثابت کنید تعداد زیرمجموعه های مجموعه ی{1,2,…n}که دارای میانگین طبیعی هستند زوج تا هستند.

 

مساله چهار : شمارش........................................................................................................ 10 نمره

 

تعداد گراف های همبند بیشتر است یا نا همبند ؟

 

مساله پنجم : باز هم مساله!؟؟؟ ............................................................................................... 0 نمره

 

سوال های 1و2و5 امتحان دوره تابستان 85 هستش !!! سوال 3 حل مساله دوره ی ما(86)سوال 4 هم تمرین گراف سال 85 !!!

اگر مرحله 2 قبول شید 100% یک امتحان با این شکل خواهید دید !

مساله ها این جوری شماره دارند و نمرشون هم جلوش نوشته شده !

براى این سوالها یه سرىلمداریم که فرض میکنیم پذیرفتیم!1-یک گراف باnراس وn یالحتما یک دور دارد- 2گرافG یک زیر گرافدو بخشى دارد که بیش از نصفیالها را دارد!-3قضیهِ هال: درگراف۲بخشى که از دو بخشِAوBتشکیل شده و هرزیرمجموعهمثلXازAداراى شرط:

|X|

  3-همواره نفر اول میبرد به غیر ازn=1 , m=1همیشه در حرکتِ اول خانهِ(0,0)خرده میشودفرض کنید نفر اول فقط خانهِ(0,0)را میخورد و در بهترین بازى می بازد
حرکتِ اولِ نفر دوم را در نظر بگیرید!!اگر زیرِ نقطه (X,Y) را خرده باشد آنگاه نفر اول میتوانند در حرکتِاول تا خانهِ(X,Y)رو بخورد و حالا تبدیل به نفر دوم شود یعنى در واقعجاى خود را با نفر دوم عوض میکند. حالا نفر اول حتما میبرد چرا که اگر نفردوم ببرد آنگاه در حالتى که نفر اول (0,0)را میخورد و نفر دوم(X,Y)را نفر اولمی توانستهبرنده شود

 

4 -جواب نه استفرض کنیدتوانستیماین کار را انجام بدهیم!!براى اینکه این کار را انجام بدهیم باید۴۰۰۴تا معادلa=bcداشته باشیم!!یکى ازbیاcباید از۲۰۰۳کمتر باشد چون اگر نباشدb*c>2002*2002میشودخوب اگرسطریوجود داشته باشد که اعداد هاى۱تا۲۰۰۲هیچ کدام رانداشته باشد وسطری وجودداشت که از۱تا۲۰۰۲را نداشت آنگاه تقاطع این سطر وستونجواب است!اما اگر یک سطر فقط وجود داشت که از۱تا۲۰۰۲را نداشت به این صورت عمل میکنیم!چون در همهستونها از عددِ۱تا۲۰۰۲داریم پس هرستوندقیقا یکى از اعداد هاى۱تا۲۰۰۲را داردستونیکه۲۰۰۲را دارد را در نظر بگیرید!خوب کوچیکترین عددِ این سطر وستون۲۰۰۲است!!پس اگرb=2002آنگاهc>2002 وb*c>2002*2002حالا اگر همهسطر هاوستونها یک عدد کوچکتر از۲۰۰۳داشتند آنگاه خانه اى که۲۰۰۲در ان قرار دارد خانه اى است که مشکل دارد

__________________________________________

سری 2:

1-اولین صحنهاى را در نظر بگیرید که یا همه سطر ها حداقل یک سفید دارند یا حداقل یکى از ستون ها یک سفید دارند (حتما هم وجود دارد(

در این زمانخاصیتمورد نظر وجود داردفرض کنید در هر سطر یک سفید داریمحالت اول:اگر در این مرحله همه ستون ها هم یک سفید داشتندفرض کنید در آخرین مرحله در خانهِ(i,j)سفید اضافه کردیم پس تا قبلاینحرکتستونjسفید نداشته و دیگرستونها همه سفید داشتند واینکه تمام سطر ها غیر ازiسفید داشتند!براى هر سطر یک خانهِ سفید را انتخاب میکنیم و به سمتِ ستونِjحرکتمیکنیم ، حتما یک خانهِ خالى پیدا میشود چون اگر از سفید به سیاه تبدیلشود که مسأله حال است و اینکه تا آخر نمى تواند سفید بمانند چون درستونjما سفید نداشتیم!!پس حداقل در همه سطر ها غیر ازiیک خانهِ خالى داریمخانهِ(i,j+1)و(i,j-1)حتما خالى هستند (حد اقل یکى از این دوخانه وجود دارد) چون با سیاه که پر نمى شوند چون در این حالت مسأله حالاست سفید هم نیستند چون اولین جایى است که سطرiخانهِ سفید دارد.پس۱۰خانهِ خالى داریم در صورتى که۹۱خانه از۱۰۰خانه پر است پس تناقص!حالت دوم:این است کهستونیوجود داشته باشد که سفید نداشته باشد!!مثلا ستونِtبگیرید!!اگر از سفیدِ هر سطر به سمتِستونtحرکتکنیم حتما یک خالى خواهیم دید (اثبات مانندِ بالا)

 

2- ابتدا ثابت میکنیم براىnهاى فرد نمى توانفرض کنید در مرحله ى اىامXiتا واحد حرکتداده ایم
 n-1مرحله داریم و بایدXiها متفاوت باشند

 n*(n-1)/2=سیگما(Xi) است و باید به هنگn مخالف 0 باشد(چرا که اگر0شودیعنى روى صندلىِ تکرارى خواهیم نشست) که این در حالتى رخ میدهد که nبه2 بخش پذیرباشد !! پسnباید زوج باشدبراىnهاى زوج همالگوریتموجود دارد:به ترتیب حرکت هاى زیر را انجام مى دهیم(تعداد چرخش ها)
n-1,2,n-3,4,n-5,6,....,1,n-2اگر رسم کنید میبیند که اینالگوریتمصحیح است و اثبات هم میشود!یعنى در واقع اگر از صندلىِ۱شروع کنیم به ترتیب روى1,n,2,n-1,3,n-2 ,… مى شنیم!

3-همیشه آرمین میبرد و در حق من ستم میشود

خوب فرض کنید در مرحله اول رامتین سکهXتومنى را انتخاب میکند وآرمین خودش این سکه را بر میدارد الان آرمینXتومان پول دارد و رامتین0تومان پول دارد پس نوبتِآرمین است که انتخاب کند!!اگر آرمین در ادامه ببرد که برده!!فرض کنید در ادامه ارمین هیچ راه بردى نداشته باشد!!ارمینسکه یX تومنى را به رامتین میدهد و حالا رامتینXتومانپول دارد وآرمین0تومان و نوبتِ رامتین است که بر دارد ،یعنى در واقعشرایط بده خودش را به رامتین میدهد!!!چون در این حالت کسى کهXتومان داشت می باختپس الانآرمین میبرد چونXتومان دست رامتین است

4-

فرض کنید درGمتغیر هاى زیر را تعریف میکنیم!!
x=تعداد۳راسى هایى که هیچیالیبین آنها نیست
y=تعداد۳راسى هایى که یک یال بین آنها وجود دارد
z=تعداد۳راسى هایى که دویال بین آنها قرار دارد
t=تعدادمثلثها(گرافK3)

معادله های زیر بر قرار است

x+y+z+t=(3 az n)

z+t=sigma(2 az di)

y+2*z+3*t=m*(n-2)

اگر 2 تا معادله اول را جمع کنیم و آخری را کم کنیمx+t به دست می آید که همان چیزی است که می خواهیم

5-تعدادمثلثهاى جهت در راxبگیریدومثلثهایى که یکیال در خلاف جهت دارد تاyبگیرید

y=sigma(2 az di)

x+y=(3 az n)

=>

x=(3 az n)- sigma(2 az di)

 

6-فرض کنید هیچ کس سر جاى خود نیستیکگرافجهت دار مى سازیم که به ازاى هر صندلى یک راس میگذاریماگر کسى که در خانهِ(x,y)نشسته وبلیطِ صندلىِ (z,t)را دارد (یاz=x یا y=t)از رأس(x,y)به رأس       (z,t)یال میکشیمحالا یک گراف داریم که درجه خروجیهر راس۱است.در این گراف حتما یک دوره جهت دار وجود دارد چون فرض کنید از رأس xشروع میکنیم و حرکت میکنیم ازیال خروجى این راس جلو میرویم بهyسپس ازyخارج میشویم تا به رأس تکرارى برسیم تا به رأس تکرارى نرسیدیم میتوانیمبه وسیلهیال خروجى از این راس خارج شویم!خوب حالا کافیست وقتى دوره جهت دار را پیدا کردیم اگر در دور از رأس (x,y)به(z,t)یال بود فردى که در  (x,y)نشسته را به مکان(z,t)ببریم و(z,t)را به سر جاى خودش و...

قسمت دو:حداکثر یک نفر!!مثال:فرض کنید به m+n-1نفر بلیطِ صندلىِ (۱،۱(رافروختیم
خوب سطر اول و ستون اول پر میشوندحالا به n-1نفر (2و1(رامی فروشیمو به n-1نفر (3و1(رامی فروشیم

...و به n-1نفر(1,m)رامی فروشیمولى هیچ کدام از این آدم هایى که بلیطِ(1,x)را دارندنمی توانندسر جاى خودبشینندچون سطر اول پر شده است!!فقط کسى که در(1و1)نشسته سر جاى خود است

 

 

گفتم نزدیکِ مرحله ۲ هستیم و یه کم سوالهاى کامپیوترى آپ کنم بد نیست !!

۹۱-۱ مهره ی سیاه در یک جدول ۱۰*۱۰ قرار دارد
در هر مرحله ۱  مهره ی سیاه را بر میداریم و در یک خانهِ خالى  مهره ی سفید می گذاریم
این کار را تا زمانى انجام مى دهیم که ۹۱ مهره ی سفید داشته باشیم
ثابت کنید لحظه ای وجود دارد که در ۲ خانهِ مجاور مهره ی سیاه و سفید قرار بگیرد. (85/3/12)

۲ -یک پسر بچه n بار سوار یک چرخ و فلک با n صندلى میشود بعد از هر مرحله او چرخ و فلک را در جهتِ عقربه هاى ساعت کمتر از یک دور کامل می چرخاند و روى یک صندلىِ دیگر می نشیند
تعداد صندلی هایی که در هر بار میگذرد را طول چرخش می نامیم !!
براى چه nهایى او میتوانند سواره هر nصندلى شود به شرطى که طول همه ى n-۱ چرخش متفاوت باشد(85/3/12)

۳ - رامتین و آرمین می خواهند ۲۵ سکه به ارزشِ ۱ تا ۲۵ را بین خود تقسیم کنند در هر حرکت یکى از آنها سکه را انتخاب میکند و دیگرى تصمیم میگیرد که این سکه به چه کسى تعلق بگیرد
در ابتدا رامتین سکه را انتخاب می کند و در هر مرحله کسى سکه را انتخاب می کند که در آن لحظه پول بیشترى داشته باشد !!
اگر پولشان برابر باشد کسى که مرحله ى قبل سکه را انتخاب کرده این مرحله هم او انتخاب میکند
در پایان کسى که پول بیشترى داشته باشد برنده است !!
چه کسى استراتژی برد دارد ؟(85/12/10)

۴ - مجموع تعداد مثلث هاى G و مکمل G را بر حسب m ( تعداد یال ها) و n (تعداد راس ها) و دنباله درجات  بیابید. (85/12/17)

۵ -تعداد دور های جهت دار به طول ۳ را در یک تورنمنت بر حسب n(تعداد راس ها) و دنباله درجات ورودى پیدا کنید.
تورنمنت گراف کاملى است که یال هاى آن را جهت دار کرده ایم (85/12/17)

۶ - صندلى هاى یک سینما به صورت یک مستطیل m*n چیده شده است

m*n بلیط فروخته شده است ولى اشتباهاً براى بعضى صندلى ها بیش از یک بلیط فروخته شده است
مسئول سالن افراد را طورى روى صندلی ها نشانده است که هر کس در سطر یا ستون درستى نشسته است

ثابت کنید میتوان افراد را طورى نشاند که هر کس یا در سطر خود باشد یا در ستون خود و حداقل یک نفر سر جاى خود نشسته باشد!!

مسئول سینما در بدترین حالت حداکثر چند نفر را میتوانند سر جاى خود بیاورد!!!(85/12/25)

این گلچینى از سوال هایى بود که من تو ماه اسفند سالى که مرحله ۲ داشتم حل کردم !
سؤالات ۱،۲،۳،۵ و ۶ رو خودم حل کردم
و ۴ را با راهنمایی

سلام !! عیدِ همه مبارک
گفتم یه پست بزنم تو سال جدید (خیلى وقت بود پستى نزده بودم)
اول از همه به طلا هاى امسال تبریک میگم که عبارتند از:
1-على بابایى چشمه احمد رضایى(حلی-تهران)
2-افروز(پسر) جبل عاملى(طباطبایی-تهران)
3-علیرضا ذاکرى(اژه ای-اصفهان)
4-مهرداد طهماسبی(حلی-تهران)
5-امیر بهشاد شهراسبی- بهروز ربیعی - جواد عابدى(حلی-تهران)
8-حسام باقرنژاد(سلطانى-کرج)
تیم هم که شد : من و سهیل احسانی و فرهاد شاه محمدی و فرشته خانى و پویا وحیدی و على بابایى ...

در مورد مرحله دوم !!
امسال هر چیزى از کمیته بر میاد پس شما باید واسه هر سوالى آماده باشید سخت ،آسون،خر کارى،و ریاضوی ...
فکر کنم این کار و کنید بد نباشه(برا اونایى که سعى میکنن راه حل نخونن)
نگاه کنید این یه ماه که مونده تا مرحله ۲ رو سعى نکنید که خیلى سر مسأله ها فکر کنید یعنى نیم ساعت دیگه بیشتر نباشه (مگه اینکه مسأله مرحله ۲ باشه)
چون تو این یه ماه فرصت یاد گرفتن ایده هستش نه ایده زدن یعنى راه حل بخونید و سعى کنید که راه حل ها رو بفهمید تا اگه سوالى مشابه اومد بتوانید حل کنید

من خودم این کار و هم براى مرحله ۲ کردم هم براى طلا هم براى تیم
مثلا نمونش همین ۲ هفته پیش واسه انتخاب تیم میرفتم BOI(المپیاد بالتیک) حل می کردم و اگه حل نمى شد راه حل میخوندم و جواب هم گرفتم

___________________________________________________________

سوال ها

1-یک گراف جهت دار با n راس و 4n یال داریم
ثابت کنید دورى وجود دارد که یال هایش یکى در میان جهتدار هستن
یعنى فرض کنید اگر داریم روى دور حرکت میکنیم اگر الان در جهتِ یال حرکت کردیم یال بعد در خلاف جهت حرکت کنیم و در مرحله ى بعد دوباره در جهتِ یال حرکت کنیم و ...

2-یک ماتریس . ماتریس جایگشت است که در هر سطر و هر ستونش دقیقا یک ۱ وجود داشته باشد
ثابت کنید میتوان یک ماتریس را به صورتِ جمعِ k تا ماتریس جایگشت نوشت اگر و فقط اگر جمعِ هر سطر و ستون آن ماتریس k باشد !!!

3-یه قطعه شکلات داریم که به صورتِ جدول n*m است
خانهِ پائین سمتِ چپ (۰،۰) است و بالا راست (n,m)
خانهِ (n,m) سمى است !!!
بازى به این صورت است که در هر مرحله یکى از ۲ بازیکن یک نقطه (x,y)(دقت کنید نقطه) را انتخاب میکند و قسمت پائین سمتِ چپِ Iن را میخورد !!!
در هر مرحله نقطه (x,y) باید وجود داشته باشد و در هر مرحله باید حداقل 1 خانه خورده شود !!!
هر کس خانهِ (n,m) را بخورد میمیرد پس هدف نخوردن خانهِ سمى است !!
برنده ى این بازی را در حالت هاى مختلف n و m بگوئید

4- آیا خانه هاى یک جدول ۲۰۰۲*۲۰۰۲ میتوانند به صورتى با اعداد هاى ۱ تا ۲۰۰۲*۲۰۰۲ (هر کدام یک بر در جدول ظاهر شود ) پر شود که شرط زیر را داشته باشد !!
براى هر خانه اى که در نظر میگیریم در سطر و ستونِ ان ۳ عددِ متمایز مانندِ a,b,c وجود داشته باشد که a=bc !!!

کد 1:

1)  ه

۲)  ج

۳)  ا

۴)  ه

۵)  ج

۶)  ج

۷)  د

۸)  د

۹)  ا

۱۰) د

۱۱) ا

۱۲) ه

۱۳) ب

۱۴) د

۱۵) ه

۱۶) د

۱۷) ا

۱۸) ه

۱۹) ا

۲۰) د

۲۱) د

۲۲) ج

۲۳) ب

۲۴) ج

۲۵) ه

۲۶) حذف (۱۶ می‌شه جواب)

۲۷) ا

۲۸) ج

۲۹) ب

۳۰) ب

کد 2:

1- ه
۲- ه
۳- ج
۴- الف
۵- ج
۶- الف
۷- ج
۸- د
۹- د
۱۰- ب
۱۱- د
۱۲- الف
۱۳- ه
۱۴- د
۱۵- د
۱۶- ه
۱۷- الف
۱۸- د
۱۹- ه
۲۰- الف
۲۱- ج
۲۲- د
۲۳- ج
۲۴- ب
۲۵- ه
۲۶- الف
۲۷- ج
۲۸- ب
۲۹- ب
۳۰- حذف

با تشکر از حسام و رکسانا !!!!

حالا copyright رو بیخیال بشم ملت من و سرویس می کنن !!!!!

البته اگه سوال ها رو داشتم به اینا اطمینان نمى کردم و خودم حل می کردم ولى چى کار کنم دیگه باید به بچه ها اعتماد کرد !!!

;)

این پست از طرفمصطفی مهدیه هستش.

با عرض سلام به همگی!

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

اگر شهرستانی هستید و می‌توانید محل اقامت‌تان در تهران را تامین کنند با ما تماس بگیرید. در صورت امکان تیم شما را در مسابقه ثبت نام می‌کنیم. شماره تلفن ما در صفحه «تماس با ما» در سایت مسابقه هست (آدرس زیر)
http://ispc.schoolnet.ir/contact.html

موفق باشید

دومین مسابقه‌ی دانش‌آموزی ایران۱۶-۱۷بهمن برگزار میشه.
شرکت‌کنندگان در رده‌ی سنی اول تا سوم دبیرستان هستند
این آدرسِ سایتش هست:http://ispc.schoolnet.ir. 

برای ثبت نام به بعضی مدارس بخشنامه امده. اگر نیومده زنگ بزنید به شماره‌ای که توی بخش «تماس با ما» توی سایت گذاشته شده.

ما رو که راه ندادن بقیه بران از المپیاد کامپیوتر دفاع کنن و نذارن ربوکاپی ها چیزى بشن !!!
سال پیش که زیرِ دست و پاى المپیادی ها خورد شدن.
حتى پائین تر از المپیادی هاى سال دومى.

یه لینکِ جدید به لینک ها اضافه کردم که وبلاگ بچه هاى نقره طلاى اصفهان هستش
کلا بد نیست به اونجا هم سر بزنید

 olampiyad dar esfehan!!!!!

۱------------------->

ابتدا به خانه ها وزن مى دهیم وزن خانهِ اى برابر (F(i است(که (F(i تابع فیبوناچی هست) 
متغیر W را مجموع وزن ها تعریف میکنم !
ثابت میکنم که W همواره ثابت است و برابرِ سیگما F(i) i=0 تا i=n
در حرکتِ نوع اول که بدیهى است که ثابت میماند چون تعریف فیبوناچی است

F(i)=F(i-1)+F(i-2)l

در حرکتِ دوم کافیست ثابت کنیم که

2F(i)=F(i-2)+F(i+1)l
از طرف چپ شروع میکنیم !

2F(i)=F(i)+F(i)=[F(i+1)-F(i-1)]+[F(i-1)+F(i-2)]=F(i+1)+F(i-2) :D
خوب پس W همواره ثابت است !

حالا که ثابت کردیم W ثابت است کافیست ثابت کنیم که

sigma F(i)i=0 ta i=n

استقرا میزنیم روى n براى n=۰ که بدیهى است !
حالا از t=>t+1
میدانیم 

 sigma F(i) i=0 ta i=t

به طرفین معادله (F(t+۱ اضافه میکنیم و اثبات می شود! 
پس هیچ وقت مهره ای در خانهِ n+۲ قرار نمیگیرد چون مجموع تغییر خواهد کرد !

۲-------------------->

اگر گراف لوپ (یالی که دو سر آن یک راس باشد ، یا دوری به طول یک) یا یالهای موازی(دو یال که دو راس های مجاور مشترک دارند یا دوری به طول 2) داشته باشد که دوری که طول آن بر 3 بخشپذیر نباشد را یافته ایم ، پس فرض کنیم گراف ساده است.مسیر ماکسیمالی در گراف که راسaیک انتهای آن است را در نظر می گیریم.aباید حداقل با دو راس دیگر به جز راس مجاورش در مسیر ماکسیمال همسایه باشد زیرا مسیر ماکسیمال است و مسیر نمی تواند از طرفaبزرگ شود ، این دو راس را به ترتیب از طرفaبه انتهای دیگر گراف ،xوyمی نامیم . سه دور را در نظر می گیریم، دوری که شامل مسیرaxویالaxمی باشد ، دوری که شامل مسیرxy و دو یالay وaxاست .و دوری که شامل مسیرayو یالayاست. فرض کنیم که طول دور اولی بر 3 بخشپذیر باشد پس طول مسیرaxبرابر3k-1است.همچنین فرض کنیم طول دور سوم نیز برابر3k*است ، پس طول مسیرxy برابر3k*-2است . طول مسیرayبرابر است با مجموع طول این دو مسیر ، پس بر 3 بخشپذیر است ، پس طول دوری که شامل مسیر و یالayاست بر 3 بخشپذیر نیست (برابر3i+1است )پس چنین دوری در گراف وجود دارد.

۳----------------->
به صورتِ دلخواه یال ها را جهت دار می کنیم چون زوج یال داریم میتوانیم بگوییم که زوج راس داریم که درجهِ خروجی آنها فرد است چون سیگما درجه خروجی انها برابرِ تعداد یال هاست
حالا ۲ راس را در نظر میگیریم که درجهِ خروجی ان ها فرد است چون گراف همبند است پس مسیرى بین این ۲ راس وجود دارد (نه لزوما جهت دار)
تمام جهت هاى یال های این مسیر را بر عکس میکنیم ! 
راس هایی که در وسط مسیر هستند که زوجیت درجه خروجی شان تغییر نمى کند(بدیهى است خود تون اثبات کنین)
۲ رأس انتهایی هم تغییر می کند یعنى از فرد تبدیل به زوج میشوند !
پس هر مرحله ۲ تا از راس هاى بد تبدیل به خوب می شوند و چون تعداد آنها زوج تا است زمانى تعداد راس های بد ۰ میشود.
۴--------------------->

ثابت میکنم که یک بازه سفید وجود درِ که همه سیاه ها را در بر می گیرد و براى سیاه ها هم به طورِ مشابه است (فقط جاى سیاه و سفید عوض میشود)
اولین بازه ی سیاه که بسته میشود و آخرین بازه ی سیاهى که شروع میشود را در نظر بگیرین!
چون این ۲ تا بازه هر کدام با k تا بازه ی سفید اشتراک دارند پس یک بازه هست که با جفت بازه هاى در نظر گرفته شده اشتراک دارد(این را انتخاب میکنیم). اگر همچین بازه ای نباشه باید حداقل 2*k بازه سفید داشته باشیم !
ثابت میکنیم بازه ای که انتخاب کردیم با همه بازه هاى سیاه اشتراک دارد!
بدیهى است که همه بازه ها یک نقطه بین اولین پایان و آخرین شروع را دارد اگر نداشته باشد این ۲ نقطه تغییر میکند !(اثباتش به عهدۀ خود تون دیگه خیلى بدیهیه)

۵------------------>

الف)
جعبه با بزرگترین سیب را بر میداریم و سپس بر اساسِ تعداد سیب ها جعبه ها را مرتب میکنیم !
حالا فرض کنید جعبه ی شماره ۱ کمترین سیب را دارد و به ترتیب تا ۹۸   تعداد سیب ها افزایش مى یابد !
جعبه ها را دست بندى میکنیم و جعبه ی 2*i و1+ ( 2*i)  را در یک بسته میگذریم !
حالا ۴۹ بسته داریم و میخواهیم ۴۹ جعبه انتخاب کنیم!
از هر بسته جعبه ای را انتخاب میکنم که بیشترین پرتقال را دارد!
این یک جعبه بر داشتن خوب هستش چون بدیهى است بیشتر از نصف پرتقال ها را dadad و در بد ترین حالت جعبه ۱،۳،۵،۹۷ انتخاب شده به همراه 99!
که چون ۹۹ بیشتر از ۹۸ ، سیب دارد و ۹۷>۹۶ ،۹۵>۹۴ ،….. ۳>۲ و ۱>=1
پس نصف سیب ها برداشتِ شده’اند!
ب) به شکل بالا بر میداریم اما این بر بعد از بر داشتن جعبه با بیشترین سیب دست ها را ۳ تایى در نظر میگیریم و در هسته جعبه با بیشترین پرتقال را بر میداریم !
باز هم درست میشود!

J)ابتدا جعبه با بیشترین سیب را بر میدارم و سپس جعبه با بیشترین پرتقال !
حالا ۹۸ جعبه دارم و میخواهم ۴۹ جعبه بر دارم!
A=بیش ترین سیب B=بیش ترین  پرتقال !
خوب میام میگم اگه من بتونم جعبه ها رو ۲ دسته بکنم که اختلافِ سیب هاى ۲ طرف کوچیک تر مساوىِAباشد و اختلافِ پرتقال این دست کم تر مساوىِ Bباشد مسأله حل است!
چون اون دسته با بیشترین موز رو بر میداریم و با اون ۲ تا جعبه !
موز ها که بیشترن و سیب ها هم بیشترن چون در بد ترین حالت  ما کمترین سیب رو بر میداریم که چون اختلافشون از A کمترِه با اون آمدنِ جعبه با بیشترین سیب جبران میشه و براى پرتقال ها هم همین طور!
از این به بعد a_i میشه سیب جعبه i و b_i میشه پرتقال  جعبه i.
پس کافیه ثابت کنیم اگر 2x جعبه داشته باشیم و میخواهیم x جعبه انتخاب کنیم که همه a_i ها ازA  کوچیکترند وb_i ها از B کوچیکترند میتوان دستi ها را به ۲ قسمت تقسیم کرد که اختلافِ سیب ها حد اکثر A باشد و پرتقال ها B باشد !
این حکم را با استقرا ثابت میکنیم
استقرا میزنیم روى که. از که به k+۲ میرسیم!
همین !
استقرا به عهدۀ خودتون( خیلى هم بدیهى نیست پس یه کم فکر کنید ،نگید چون نگفته خیلى بدیهیه )

۶----------------------------->

مسأله را با استقرا روى تعداد یال ها حل میکنیم

پایه استقرا( m=2 تعداد یالها)
چون گراف همبند است پس میتوانیم بگوییم که خود گراف حداکثر ۳ راس دارد و کمتر هم ندارد! خود گراف P-۳ است
فرض استقرا :گرافی با زوج یال و همبند را میتوان به P-۳ افراز کرد!
گام استقرا:m==>m+2
مسیرِ ماکسیمم را در نظر میگیریم !
فرض کنید که راس ها به ترتیب در مسیر a1,a2،….،ax باشد (به بدیهیت x>=۳ است زیرا اگر کمتر باشد آنگاه بزرگترین مسیر به طول ۱ است و چون گراف همبند است پس گراف حداکثر ۲ راس دارد و گراف میتوانند حداکثر ۱ یال داشته باشد !)

1)اگر a2 همسایه به غیر از a1 و a3 داشته باشد آنگاه اون راس را u مینامیم
ثابت میکنم اگر ما یال (a1-a2) و (a2- u) را بر داریم گراف هنوز همبند خواهد ماند!( در اینجا تعریف از همبندی بدون در نظر گرفتن راس های درجه ۰ است)
اگر درجهِ a1 صفر شود که مشکلى نیست و با تعریف همبندى تناقص ندارد!
اما اگر درجه یه a1 بیشتر از صفر باشد آنگاه میدانیم تمام همسایه هاى a1 در مسیر هستند چون اگر همسایه ای بیرون از مسیر داشته باشد میتوانیم طول مسیر را افزایش بدیم که با ماکسیمم بودنش تناقص دارد!
پس هنوز a1 به a2 مسیر دارد چون اگر a1 به یک راسى مثل at برود و سپس به a_t-1 سپس به a_t-2 ...
به a2 میرسد.
براى رأس u هم همین اثبات کافیست چون رأس u اگر ۰ شود که با تعریف همبندی تناقص ندارد اگر هم همسایه داشته باشد باز هم همسایه هایش در مسیر هستند چون اگر نباشند آنگاه مسیر ماکسیمم نبوده !

2)اگر a2 همسایه ای به غیر از a1 و a3 نداشته باشد مسیر a1-a2-a3 را حذف میکنیم. a2 که درجه ۰ میگیرد ،a3 هم که به مسیر وصل است.
فقط مى ماند a1:
اگر درجهِ a1 صفر شود که حله
اگر هم ۰ نشود آنگاه همسایه در مسیر دارد که باز هم گراف همبند مى ماند!

پس گراف هم چنان همبند است و m یال دارد ! (طبق فرض استقرا مسأله حل است)

 

دوباره سلام!

ببینید من یه سرى سوال در اوردم که به درد مرحله ۲ میخوره. فکر کنم هر کدومش ایده هاى خوبى داره.

هر کس که مى خواهد میتونه به من میل بزنه و این سؤالات رو بگیره بعد هر کدوم رو که حل کرد به من میل کنه تا واسش صحیح کنم !!

میل:

 rahmtin.rotabi@gmail.com