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

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

آمار پرسش:

  • پرسیده شده: 2022-05-10 03:26:32 -0500
  • مشاهده شده: 240 بار
  • بروز شده: 2022-05-11 10:25:44 -0500

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

رشته‌ی نزدیک - مرحله ۲ - ۱۳۹۲

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

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

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

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

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

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

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

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

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

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

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

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

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

علائم ریاضی:

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

حذف کردن مهره ها در 1402 حرکت - سوال اول مرحله دو سال 1401 - دوره 32

0

یک جدول با ۱۴۰۱ سطر و ۳ ستون داریم. به خانههای تلاقی مجموعهای از سطرهای متوالی و مجموعهای از ستونهای متوالی، یک زیرجدول میگوییم. در ابتدا ایمان به ازای هر سطر جدول، دقیقاً دو خانه از سه خانه را انتخاب میکند و داخل آنها مهره قرار میدهد. سپس اسکندر در تعدادی حرکت ، ی همه همهر های جدول را حذف میکند. او در هر حرکت، یک زیرجدول انتخاب میکند که تمام خانههای آن دارای مهره باشد و آن مهرهها را حذف میکند.

الف) ثابت کنید اسکندر همواره میتواند تمامی مهره ها را در حداکثر ۱۴۰۲ حرکت حذف کند. ( ۹ نمره)

ب) ثابت کنید ایمان میتواند در ابتدا طوری مهرهها را قرار دهد که اسکندر برای حذف همهی آنها حداقل ۱۴۰۲ حرکت لازم داشته باشد. ( ۹ نمره)

مرحله۲ ۱۴۰۱ دوره-۳۲
2022-05-10 03:26:32 -0500
حقگو 41 ● 7 ● 11 ● 14
پاک‌کردن   ویرایش سوال

1 پاسخ

0

الف)

راه 1)

در ستون اول و دوم و سوم به ترتیب x,y,z خانه ی خالی داریم . واضح است که اگر در ستونی Q تا خانه ی خالی باشد حداکثر با Q+1 حرکت کل آن ستون را حذف میکنیم . حالا پس میدانیم که x+y+z = 1401 پس با 1404 حرکت میتوان همه را حذف کرد . اما به این نکته توجه کنید که در سطر اول و دوم هر کدام یک خانه ی خالی دارند . لذا در ستون هایی که آن خانه ی خالی آمده اند یکی از زیرجدول های متوالی اش کم میشود . پس $1404-2=1402$

راه 2)

استقرا میزنیم . حکم : به ازای n سطر و 3 ستون هموراه میتوان حداکثر n+1 حرکت کل مهره ها را حذف کرد به طوری که سطر آخر دو مهره اش در یک زیرجدول حذف نشوند . پایه : n=2 که بر عهده خواننده گام استقرا : سطر آخر را در نظر بگیرید . حداقل یکی از مهره هایش با یکی مهره های سطر بالا اشتراک دارد طبق فرض استقرا هر دو مهره ی سطر یکی مانده به آخر در دو زیرجدول مجزا حذف شده اند (بیش از یک ستون در زیرجدولی که حذف شده ، نیست .) لذا میتوان آن مهره ای که اشتراک دارد را با زیرجدولی که از سطر بالایی حذف شده حذف میکند و آن یکی مهره ی سطر آخر را هم با یک زیرجدول 1در1 حذف میکنیم . پس

n-1 +1 + 1 = n+1 ب) سطر هایی که به 3 باقیمانده ی 1 دارند را

-..

باقیمانده ی 2

..-

باقیمانده ی 3

.-.

حالا واضح است که هیچ زیرکدولی با تعداد سطر بیش از 2 نمیتوان انتخاب کرد . همچنین دو مهره در سطر یک و آخر تنها هستند و با زیرجدولی نمیاند . پس

2 + 2800/2 = 1402

2022-05-10 22:15:17 -0500
محمدعرفان گونه 1 ● 2 ● 3
پاک‌کردن   ویرایش پاسخ

پاسخ شما

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

پیش‌نمایش:

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