اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2022-04-25 20:46:40 -0500
  • مشاهده شده: 146 بار
  • بروز شده: 2022-04-26 12:45:28 -0500

پرسش‌های مشابه:

سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک

بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳

وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳

گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳

انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳

یافتن کوچکترین پیچ و مهره با مقایسه آنها

دنباله و جادوگر - دوره ی 24 - مرحله ی 2

دوربین های عکاسی

مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23

بازی خاموش کردن چراغ ها

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

لیوان بازی - سوال ۱ - دوره ۱۴ م۲ تشریحی

0

لیوان بازی

یک میز چرخان مربع شکل را در نظر بگیرید که در هر یک از چهارگوشه‌ی آن‌ یک عدد لیوان قرار دارد. هر لیوان یا رو به بالا (U) است یا رو به پایین (∩). «محمد» که چشمانش بسته است، می‌خواهد با توجه به قواعد زیر با حداقل تعداد «حرکت» همه‌ی لیوان‌ها را یا رو به بالا کند و یا همه را رو به پایین. این کار زیر نظر یک داور انجام می‌شود. هر حرکت شامل همه‌ی مراحل زیر است که به ترتیب اجرا می‌شوند:

۱) داور میز را به‌دلخواه می‌چرخاند تا هر لیوانی که بخواهد در گوشه‌ی مورد نظرش قرار گیرد.

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

۳) محمد دو لیوان در گوشه‌های انتخابی را لمس می‌کند و می‌فهمد که هر یک رو به بالاست یا رو به پایین.

۴) محمد با برعکس کردن تعدادی (شاید هیچ کدام) از این دو لیوان آن دو را به هر صورتی که لازم ببیند درمی‌آورد.

۵) داور به محمد می‌گوید که آیا همه‌ی لیوان‌ها هم‌جهت هستند یا خیر. اگر هم‌جهت باشند که محمد موفق شده است و کار تمام است، وگرنه باید حرکت بعدی را انجام دهد.

آیا محمد می‌تواند با تعداد محدودی حرکت این کار را انجام دهد؟ در صورتی‌ که جواب شما منفی است آن را اثبات کنید. برای جواب مثبت، حداقل تعداد حرکت‌ها را به دست آورید و نشان دهید که آن تعداد حرکت کمینه است.

مرحله۲ ۱۳۸۳
2022-04-25 20:46:40 -0500
محمدعرفان گونه 21 ● 1 ● 3 ● 5
پاک‌کردن   ویرایش سوال

1 پاسخ

0

بله میشود .

مربع را اینطور عددگذاری میکنیم بر اساس مختصات خانه ها:

(۱و۱) = 1 ، (۲و۱) = ۲ ، (۲ و ۱) = ۳ ، (۲ و ۲) = ۴

راهکار با حداکثر ۵ حرکت :

در ابتدا ۱ و ۲ را انتخاب میکنیم و هر دوی آنها را U میکنیم . حالا ۱ و ۴ را میگیریم و هر دوی آنها را U میکنیم . اگر تمام نشده باشد دقیقا یکی ∩ داریم . حالا ۱ و ۴ را باز انتخاب میکنیم . اگر یکی از آنها ∩ بود که آنرا برمیگردانیم و تمام است . در غیر اینصورت هر دوی آنها U هستند . یکی از آنها را به دلخواه ∩ میکنیم . بدون از دست دادن کلیت مساله فرض میکنیم آن خانه ی ۴ بوده . حالا ۱ و ۲ را انتخاب میکنیم .

الف)اگر هر دوی آنها به یک سمت بودند آن دورا برمیگردانیم و تمام است .

ب) در غیر این صورت هر کدام را برعکس میکنیم

در این مرحله اگر بازی تمام نشده ۱ و ۴ را انتخاب میکنیم و این دو قطعا یک سمت هستند و هر دو را برمیگردانیم و همه یکی میشوند . پس حداکثر با ۵ حرکت شد.

اثبات لازم بودن ۵ حرکت :

فرض کنید با ۴ حرکت میشود . ما جای داور بازی میرویم . اولا درست است که داور نمیداند تصمیم محمد چیست ولی محمد هم چشم هایش بسته است و میتوان فرض کرد جدول قرار گرفته روبروی آن دلخواه است پس برای بررسی تمام حالت میتوان فرض کرد داور میداند حرکت بعدی محمد چیست . اولا ما(داور) در دو انتخاب ابتدایی محمد و دو خانه ی انتخاب نشده از هر نوع جهت لیوان یکی میگذاریم و به وضوح با یک مرحله نمیشود . برای دو مرحله هم در مرحله ی دوم هم میتوانیم کاری کنیم حداقل یکی از انتخاب های قبلیش قرار بگیرد با یک خانه ی دیگر به طوری که بعد از این مرحله هنوز حداقل یک لیوان از نوع دیگر بماند . برای مرحله سوم هم میتوانیم دو خانه ی مشابه را نشانش دهیم(از حداکثر ۳ خانه از یک نوع و طبق لانه کبوتری حداقل ۲ خانه) . برای مرحله چهارم هم چون دو نوع دارد از هر کدام هست در دو انتخابش از هر دو نوع یکی نشان میدهیم تا با تغییر دادن چیزی همه یک جهت نشوند .

2022-04-26 12:45:28 -0500
محمدعرفان گونه 21 ● 1 ● 3 ● 5
پاک‌کردن   ویرایش پاسخ

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.