شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

بایگانی

۲ مطلب در فروردين ۱۳۸۸ ثبت شده است

۲۵
فروردين

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

|X|

 آنگاه تطابقیوجود دارد کهAرا بپوشاند!

سری 1:

1 -طبقلم۲داریم که این گراف زیرگرافیبا بیش از نصفیالها دارد!!ما  2*nتایالرا در نظر میگیریم!!!فرض کنید بخش هاىگراف۲بخشى بالا و پائینبنامیم
حالا یک سرى ازیالها جهت دار به سمتِ پائین هستند و یک سرى به سمتِ بالا!یکى از این۲دستهیال,بیشتر ازnتا است!اینnتا را در نظر بگیرید!
n
تا راس داریم وnتایالپس طبقلم۱یک دور وجود دارد کهیالهایشهمه به طرف یکبخشاست پسخاصیت مورد نظر را دارد

2-ماتریسی که در هر سطر وستونش kتا۱داریم راAبنامید

از روىAیک گراف 2بخشیمى سازیمبه ازاى هر سطر وستونش یک راس می گذاریم یعنى براىماتریس2*n, n*nتا راس داریم!حالا اگر A[i][j]=1آنگاه از رأس iبخشِسطربهjبخشِ ستون ها وصل میکنیم!حالا یکگراف۲بخشى داریم که درجهِ همه راس هاkاستبا استفاده ازلم۳میتوان اثبات کرد که هرگرافkَ منتظم۲بخشى داراىتطابق کامل استحالا هر بار یک تطابق بر میداریمو تبدیل به یک گراف می کنیمو اگریالiبهjرا بر داشتیم آنگاه درماتریسی که داریم مى سازیمدرایه یiو jرا۱میکنیم!!حالا یکگرافk-1 منتظم داریم و دوباره میتوانیم یک تطابق کم کنیمبه این ترتیب ماkتا جدول خواهیم داشت که جمعِ این جدول ها میشود A

  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)نشسته سر جاى خود است

 

 

نوشته شده توسط رامتین رطبی(سابق) در چهارشنبه ۲۶ فروردین۱۳۸۸ و ساعت 23:9 |
  • شااززز منگولیا
۱۸
فروردين
گفتم نزدیکِ مرحله ۲ هستیم و یه کم سوالهاى کامپیوترى آپ کنم بد نیست !!

۹۱-۱ مهره ی سیاه در یک جدول ۱۰*۱۰ قرار دارد
در هر مرحله ۱  مهره ی سیاه را بر میداریم و در یک خانهِ خالى  مهره ی سفید می گذاریم
این کار را تا زمانى انجام مى دهیم که ۹۱ مهره ی سفید داشته باشیم
ثابت کنید لحظه ای وجود دارد که در ۲ خانهِ مجاور مهره ی سیاه و سفید قرار بگیرد. (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)

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

  • شااززز منگولیا