صندلی های سینما

از shaazzz
پرش به ناوبری پرش به جستجو

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

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

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

مسئول سینما در بدترین حالت حداکثر چند نفر را میتوانند سر جاى خود بیاورد!!!

پاسخ

فرض کنید هیچ کس سر جاى خود نیستیکگرافجهت دار مى سازیم که به ازاى هر صندلى یک راس میگذاریماگر کسى که در خانهِ(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)نشسته سر جاى خود است