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

[Goharshady]

[center:2a0208432c]

[/center:2a0208432c]سوال سی و سومقرار بود سوال سی و سوم ماراتن ترکیبیات باشد!)
این سوال در حقیقت 2 سوال نظریه بازیها است!!


الف) یک صفحه ی شطرنجی نامتناهی داریم. دو نفر روی این صفحه یا هم تیک تاک تو بازی می کنند. (همون X O خودمونه) کسی برنده است که 5 مهره او به صورت افقی یا عمودی پشت سر هم قرار گیرند. ثابت کنید نفر دوم استراتژی نباختن دارد. (المپیاد ریاضی رژِیم صهیونیستی - 1995)

ب) 4 نفر از یک مغازه دزدی کردند. پلیس آنها را به زندان برد. در زندان جای کافی برای آنها نبود (در حقیقت زندان کاملا پر بود). به همین دلیل زندانبان تصمیم گرفت سوالی مطرح کند و اگر یکی از این 4 نفر ، آن سوال را پاسخ داد همه ی آنها را آزاد کند. در غیر این صورت همه ی آنها را اعدام کند!! (چه قدر هم اختیارات وسیعی داشته!) ، از قضا این چهار نفر ریاضیدانان آماتور بودند! (همینه دیگه ، وقتی از شغل آدم نون در نیاد ، مجبور میشی دزدی کنی!) و اما زندانبان این کارها را انجام داد:
4 نفر را به صف کرد. بین نفر سمت راست و بقیه دیوار کشید!!! (از این دیوار نه صدا رد می شود ، نه سیما)
بعد از نفر آخر شروع کرد و به هریک کلاهی داد که یا قرمز بود یا آبی (از هر رنگ دوتا) و از آنها خواست که رنگ کلاه خود را بگویند
هر کس فقط می توانست کلاه نفرات جلوی خود را ببیند و کسی هم نمی توانست آن طرف دیوار را ببیند.
ثابت کنید این 4 نفر در هر صورت می توانند آزاد شوند.
[center:2a0208432c]

[/center:2a0208432c]

 

[Goharshady]

جواب قسمت ب

ب) 4 نفر از یک مغازه دزدی کردند. پلیس آنها را به زندان برد. در زندان جای کافی برای آنها نبود (در حقیقت زندان کاملا پر بود). به همین دلیل زندانبان تصمیم گرفت سوالی مطرح کند و اگر یکی از این 4 نفر ، آن سوال را پاسخ داد همه ی آنها را آزاد کند. در غیر این صورت همه ی آنها را اعدام کند!! (چه قدر هم اختیارات وسیعی داشته!) ، از قضا این چهار نفر ریاضیدانان آماتور بودند! (همینه دیگه ، وقتی از شغل آدم نون در نیاد ، مجبور میشی دزدی کنی!) و اما زندانبان این کارها را انجام داد:
4 نفر را به صف کرد. بین نفر سمت راست و بقیه دیوار کشید!!! (از این دیوار نه صدا رد می شود ، نه سیما)
بعد از نفر آخر شروع کرد و به هریک کلاهی داد که یا قرمز بود یا آبی (از هر رنگ دوتا) و از آنها خواست که رنگ کلاه خود را بگویند
هر کس فقط می توانست کلاه نفرات جلوی خود را ببیند و کسی هم نمی توانست آن طرف دیوار را ببیند.
ثابت کنید این 4 نفر در هر صورت می توانند آزاد شوند.
[center:d6cf01026c]

[/center:d6cf01026c]

نمی دونم چرا هیچکس جواب نمی ده!
این هم جواب قسمت ب:
C کلاه A و B را می بیند. اگر کلاه آن دو همرنگ باشد ، می تواند سریعا رنگ کلاه خود را بگوید. در غیر این صورت ساکت می ماند و B میفهمد که کلاهش با C ناهمرنگ است و رنگ کلاه خود را می گوید.
به همین سادگی ،