اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشتهی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنهها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهرههای گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
در این قسمت میتونی به یک پرسش پاسخ بدی. اگه میخوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخها مفید هستند حتما بهشون رای بده تا پرسشها و پاسخهای خوب مشخص بشن.
توی قسمت پیشنمایش میتونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
میتونی از تگهای معمولی و سادهی html هم استفاده کنی.
با دکمههایی که بالای ویرایشگر قرار دارند کلی کار میشه کرد. از عکسگذاشتن بگیر تا لیست شمارهدار. حتما امتحانشون کن.
برای نوشتن علائم ریاضی میتونی از Mathjax استفاده کنی.
راهنمای Mathjax رو از سایت
math.stackexchange
بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.
لیوان بازی
یک میز چرخان مربع شکل را در نظر بگیرید که در هر یک از چهارگوشهی آن یک عدد لیوان قرار دارد. هر لیوان یا رو به بالا (U) است یا رو به پایین (∩). «محمد» که چشمانش بسته است، میخواهد با توجه به قواعد زیر با حداقل تعداد «حرکت» همهی لیوانها را یا رو به بالا کند و یا همه را رو به پایین. این کار زیر نظر یک داور انجام میشود. هر حرکت شامل همهی مراحل زیر است که به ترتیب اجرا میشوند:
۱) داور میز را بهدلخواه میچرخاند تا هر لیوانی که بخواهد در گوشهی مورد نظرش قرار گیرد.
۲) محمد دو گوشهی میز را انتخاب میکند. اگر این دو گوشه دو سر یک ضلع مربع باشند آنها را گوشههای مجاور و اگر دو سر یک قطر باشند آنها را گوشههای روبهرو میگوییم.
۳) محمد دو لیوان در گوشههای انتخابی را لمس میکند و میفهمد که هر یک رو به بالاست یا رو به پایین.
۴) محمد با برعکس کردن تعدادی (شاید هیچ کدام) از این دو لیوان آن دو را به هر صورتی که لازم ببیند درمیآورد.
۵) داور به محمد میگوید که آیا همهی لیوانها همجهت هستند یا خیر. اگر همجهت باشند که محمد موفق شده است و کار تمام است، وگرنه باید حرکت بعدی را انجام دهد.
آیا محمد میتواند با تعداد محدودی حرکت این کار را انجام دهد؟ در صورتی که جواب شما منفی است آن را اثبات کنید. برای جواب مثبت، حداقل تعداد حرکتها را به دست آورید و نشان دهید که آن تعداد حرکت کمینه است.
بله میشود .
مربع را اینطور عددگذاری میکنیم بر اساس مختصات خانه ها:
(۱و۱) = 1 ، (۲و۱) = ۲ ، (۲ و ۱) = ۳ ، (۲ و ۲) = ۴
راهکار با حداکثر ۵ حرکت :
در ابتدا ۱ و ۲ را انتخاب میکنیم و هر دوی آنها را U میکنیم . حالا ۱ و ۴ را میگیریم و هر دوی آنها را U میکنیم . اگر تمام نشده باشد دقیقا یکی ∩ داریم . حالا ۱ و ۴ را باز انتخاب میکنیم . اگر یکی از آنها ∩ بود که آنرا برمیگردانیم و تمام است . در غیر اینصورت هر دوی آنها U هستند . یکی از آنها را به دلخواه ∩ میکنیم . بدون از دست دادن کلیت مساله فرض میکنیم آن خانه ی ۴ بوده . حالا ۱ و ۲ را انتخاب میکنیم .
الف)اگر هر دوی آنها به یک سمت بودند آن دورا برمیگردانیم و تمام است .
ب) در غیر این صورت هر کدام را برعکس میکنیم
در این مرحله اگر بازی تمام نشده ۱ و ۴ را انتخاب میکنیم و این دو قطعا یک سمت هستند و هر دو را برمیگردانیم و همه یکی میشوند . پس حداکثر با ۵ حرکت شد.
اثبات لازم بودن ۵ حرکت :
فرض کنید با ۴ حرکت میشود . ما جای داور بازی میرویم . اولا درست است که داور نمیداند تصمیم محمد چیست ولی محمد هم چشم هایش بسته است و میتوان فرض کرد جدول قرار گرفته روبروی آن دلخواه است پس برای بررسی تمام حالت میتوان فرض کرد داور میداند حرکت بعدی محمد چیست . اولا ما(داور) در دو انتخاب ابتدایی محمد و دو خانه ی انتخاب نشده از هر نوع جهت لیوان یکی میگذاریم و به وضوح با یک مرحله نمیشود . برای دو مرحله هم در مرحله ی دوم هم میتوانیم کاری کنیم حداقل یکی از انتخاب های قبلیش قرار بگیرد با یک خانه ی دیگر به طوری که بعد از این مرحله هنوز حداقل یک لیوان از نوع دیگر بماند . برای مرحله سوم هم میتوانیم دو خانه ی مشابه را نشانش دهیم(از حداکثر ۳ خانه از یک نوع و طبق لانه کبوتری حداقل ۲ خانه) . برای مرحله چهارم هم چون دو نوع دارد از هر کدام هست در دو انتخابش از هر دو نوع یکی نشان میدهیم تا با تغییر دادن چیزی همه یک جهت نشوند .