الگوریتم ریاضی دانان و ربایندگان

[nasim984]

سوال ACM آمریکا
شما چه الگوریتمی پیشنهاد می کنید.
چهار ریاضی دان توسط 2 آدم ربا دزدیده شده اند .
ریاضی دان ها به ترتیبی زیر نشسته اند :
1 2 3 || 4 هیچ یک از ریاضی دان ها نمی تواند سر خود را بر گرداند و با یکدیگر صحبت کنند.
فقط ریاض دان 3 می تواند 1و2 را ببیند و 2 می تواند 1 را ببیند.
آدم رباها به صورت تصادفی 4 کلاه که 2تا سفید و 2 تا سیاه هستند را به ریاضی دانان میدهند به صورتی که هیچ کدام نمی توانند کلاه خود را ببینند.و در صورتی ریاضی دان ها آزاد می شوند که رنگ کلاه خود را ببینند. تمام حالات ممکن برای حل این مسئله را نشان دهید.

[nasim984]

که کلاه ها به چه صورتی بر سر ریاضی دان ها قرار میگیرد
در ضمن || به معنی دیوار بین( 1و2و3) و 4 هست

[nasim984]

در ضمن صورت سوال را من تغییر ندادم دیگه باید تمام نقاط مبهم را با تفکر شفاف کنید

[saeedIRHA]

حالا من ازت يک سؤال دارم، چطوری ميتونی برای سؤالت جواب بگيری؟
جواب: اون رو در قسمت مناسب مطرح کنی!!!
اين سؤال شما ربطی به ++C نداره و بايد در قسمت الگوريتم مطرح بشه
وقتی جواب گرفتی و خواستی پياده سازيش کنی در ++C بيا اينجا مطرح کن.

[حامد مصافی]

دو حالت برای حل این مسئله وجود دارد.
1- رنگ کلاه نفرات اول و دوم یکسان است.
2- رنگ کلاه نفرات اول و دوم یکسان نیست.

در حالت اول :
شماره 3 می داند که رنگ کلاهش متفاوت با رنگ 1 و 2 است پس رنگ متضاد کلاه آن دو را می گوید و آزاد می شود. نفر 2 می داند رنگ کلاهش با شماره 1 همسان است؛ این رنگ را گفته آزاد می شود. نفر 1 رنگی را که نفر 2 گفته تکرار می کند و آزاد می شود. نفر 4 رنگ یکسانی با شماره 3 دارد، آن را گفته آزاد می شود.

در حالت دوم:
شماره 3 چون نمی داند حرفی نمیزند، شماره 2 با استفاده از این سکوت در می یابد رنگ کلاهش با شماره 3 یکسان نیست، پس رنگ مخالف را گفته و آزاد می شود. . شماره های 3 و 4 نمی توانند آزاد شوند.

[xxxxx_xxxxx]

مرسي بابت پاسختون.
اين پاسخ مربوط به پست اول هست (چون اعداد با تصوير پست 6 فرق ميكنه)
اما اون قسمتي كه آبي كردم فكر مي كنم بايد همون 1 باشه نه 3 !!!

دو حالت برای حل این مسئله وجود دارد.
1- رنگ کلاه نفرات اول و دوم یکسان است.
2- رنگ کلاه نفرات اول و دوم یکسان نیست.

در حالت اول :
شماره 3 می داند که رنگ کلاهش متفاوت با رنگ 1 و 2 است پس رنگ متضاد کلاه آن دو را می گوید و آزاد می شود. نفر 2 می داند رنگ کلاهش با شماره 1 همسان است؛ این رنگ را گفته آزاد می شود. نفر 1 رنگی را که نفر 2 گفته تکرار می کند و آزاد می شود. نفر 4 رنگ یکسانی با شماره 3 دارد، آن را گفته آزاد می شود.

در حالت دوم:
شماره 3 چون نمی داند حرفی نمیزند، شماره 2 با استفاده از این سکوت در می یابد رنگ کلاهش با شماره 1 یکسان نیست، پس رنگ مخالف را گفته و آزاد می شود. . شماره های 3 و 4 نمی توانند آزاد شوند.

و براي پست ششم به اين صورت ميشه:
----------------------------
1- رنگ کلاه نفرات دوم و سوم یکسان است.
2- رنگ کلاه نفرات دوم و سوم یکسان نیست.

در حالت اول :
شماره 1 می داند که رنگ کلاهش متفاوت با رنگ 2 و 3 است پس رنگ متضاد کلاه آن دو را می گوید و آزاد می شود. نفر 2 می داند رنگ کلاهش با شماره 3 همسان است؛ این رنگ را گفته آزاد می شود. نفر 3 رنگی را که نفر 2 گفته تکرار می کند و آزاد می شود. نفر 4 رنگ یکسانی با شماره 1 دارد، آن را گفته آزاد می شود.

در حالت دوم:
شماره 1 چون نمی داند حرفی نمیزند، شماره 2 با استفاده از این سکوت در می یابد رنگ کلاهش با شماره 3 یکسان نیست، پس رنگ مخالف را گفته و آزاد می شود. و شماره 3 رنگي مخالف شماره 2 گفته و آزاد ميشود. شماره 1 و 4 نمي توانند آزاد شوند.
-----------------------------
سؤال: يعني شماره هاي 1 و 4 در حالت دوم واقعاً نمي توانند آزاد شوند؟ راهي نيست؟

[SamaPic]

با سلام خدمت دوست عزیز.
اگر سال مطرح شدن سوال را هم بگویی بد نیست.
این سوال ها را باید بصورت انگلیسی مطرح کرد و ترجمه ی آن هیچ ارزشی ندارد.
از کدام سایت گرفتی.من دنبال سوالای ACM می گردم.
با تشکر.
خدانگهدار.