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

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

آمار پرسش:

  • پرسیده شده: 2021-06-06 03:38:29 -0500
  • مشاهده شده: 494 بار
  • بروز شده: 2024-03-10 05:41:07 -0500

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

علائم ریاضی:

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

فاصله‌گذاری اجتماعی - سوال دو مرحله دو سال 1399

2

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

مرحله۲ ۱۳۹۹
2021-06-06 03:38:29 -0500
حقگو 51 ● 12 ● 12 ● 15
پاک‌کردن   ویرایش سوال
نظرات

من برای n های زوج اثبات کردم که نمی‌تونه ببره بعد برام یه سوال پیش اومد اگه اینو اثبات کردم چند نمره از سوال رو میگیرم ؟ نصف ؟ ربع ؟ هیچ ؟

2024-03-02 04:42:27 -0500 الفبا

دقیقا منم، فقط یادم نیس زوج رو اثبات کرده بودم یا فرد رو. اثباتشم با رنگ آمیزی بود. حالا باید دوباره بررسی کنم

2024-03-02 05:47:09 -0500 سیده زینب متولی

یادمه یه جا خونده بودم که نمره دهی مرحله دو صفر و یکی هس. ینی اگه راه محلمون کامل باشه نمره کامل می گیریم، و اگه ناقص باشه نمره نمی گیریم...

2024-03-02 05:49:07 -0500 سیده زینب متولی

خب اگه این طور باشه قطعا خبر بدیه ولی خب اسم رنگ امیزی رو که آوردی راهم کامل شد

2024-03-02 06:08:17 -0500 الفبا

آره اصن اثبات منم برا n های فرد بوده و رنگ آمیزیم هم شطرنجی (در حالت n های فرد زاریچ استراتژی برد داره)

2024-03-02 08:23:33 -0500 سیده زینب متولی

1 پاسخ

1

قرارداد: خانه‌های یک جدول $n\times n$ را با زوج‌های $(1,1)$ تا $(n,n)$ نشان می‌دهیم.

نخست : زاریچ برای $n$ های فرد استراتژی برد دارد. زاریچ جدول را با دو رنگ سیاه و سفید به صورت شطرنجی رنگ می‌کند طوریکه چهار گوشهٔ جدول سیاه باشند. کرونا مجبور است در هر مرحلهٔ از بازی حداقل یک خانهٔ سیاه را انتخاب کند ( چرا؟ ) و زاریچ در هر نوبت همیشه یک خانهٔ سیاه انتخاب می‌کند. این جوری زاریچ برنده می‌شود. (زاریچ نیاز نیست استراتژی پیچیده‌ای به کار گیرد. او یک خانهٔ سیاه تصادفی انتخاب می‌کند.)

پاسخ چرا: مجموع مولفه‌های همهٔ خانه‌های یک قطر پراکنده همیشه برابر است با $n(n+1)$ که یک عدد زوج است.

اما مجموع مولفه‌های هر خانه سفید یک عدد فرد است. که مجموع فرد تا عدد فرد همیشه یک عدد فرد است.

پس هیچ وقت $n$ خانهٔ سفید نمی‌توانند یک قطر پراکنده بسازند.

دوم: برای $n$ های زوج کرونا استراتژی برد. فرض کنید $n=2k$

کرونا مطابق شکل $k$ مربع $2\times 2$ در نظر می‌گیرد. image description کرونا در هر مرحله باید دو خانه همرنگ از هر مربع را انتخاب کند. واضح است که این $n$ خانه همیشه یک قطر پراکنده می‌سازند.

کرونا پس از هر انتخاب زاریچ، در مرحله بعد همان خانه‌های مرحلهٔ قبل را با یک تغییر کوچک انتخاب می‌کند. او در عوض آن دو خانهٔ همرنگی که زاریچ یکی از آنها را انتخاب کرده بود، دو خانهٔ دیگر مربعی که در آن واقع شده بودند را انتخاب می‌کند. این جوری زاریچ همیشه در انتخاب $k+1$ ام دیگر نمی‌تواند هیچ انتخابی کند و بازی را می‌بازد.

2024-03-10 05:41:07 -0500
کنکوری 1683 ● 13 ● 27 ● 40
پاک‌کردن   ویرایش پاسخ

پاسخ شما

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

پیش‌نمایش:

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