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

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

آمار پرسش:

  • پرسیده شده: 2016-11-23 10:34:30 -0500
  • مشاهده شده: 426 بار
  • بروز شده: 2016-11-24 09:21:31 -0500

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

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

آیا گراف قویا همبند است؟

اثبات همبند بودن مکمل گراف ناهمبند

همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1

رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ

دنباله ی درجات گراف

پیدا کردن مولفه های قویا همبند گراف جهت دار

انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز

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

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

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

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

علائم ریاضی:

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

صفحه ی شطرنجی ‎‎$‎4\times n‎$‎‏ ‏، اسب نمی تواند همه ی خانه ها را یکبار ببیند.

4

ثابت کنید که روی صفحه ی شطرنجی ‎‎$‎4\times n‎$‎‏ ‏، اسب نمی تواند طوری حرکت کند که از هر خانه دقیقا یکبار عبور کرده باشد و در اخرین حرکت به خانه ی اولیه بازگردد.

گراف
2016-11-23 10:34:30 -0500
حمید کاملی 2921 ● 30 ● 56 ● 83
پاک‌کردن   ویرایش سوال

1 پاسخ

4

image description

مطابق شکل بالا روی خانه های سطر اوّل عدد 1، خانه های سطر دوّم عدد 2، خانه های سطر سوّم عدد 3 و خانه های سطر چهارّم عدد 4 را می نویسیم.

image description

گراف حالات حرکت اسب در جدول به شکل بالاست.

در ادامه برای حالتی که خانه ی شروع یکی از خانه های {1 سیاه، 4 سیاه، 3 سفید، 2 سفید} باشد استدلال می کنیم، حالت دیگر نیز با همین استدلال و بطور مشابه اثبات می شود.

می دانیم تعداد 1 سیاه و 4 سیاه و 3 سفید و 2 سفید برابر است، بنابر این با توجّه به این که در طول حرکات هر خانه را یکبار می بینیم (خانه ای که در ابتدا در آن بوده ایم را حساب نمی کنیم.) پس این 4 خانه را هم باید تعداد مساوی بار ببینیم، اگر مدام به ترتیب همین 4 نوع خانه را ببینیم تعداد مساوی بار دیده ایم ولی 4 خانه ی دیگر {1 سفید، 4 سفید، 3 سیاه، 2 سیاه} را ندیده ایم، پس باید از یکی از خانه های 2 سفید یا 3 سفید به 3 سیاه یا 2 سیاه هم برویم تا 4 خانه ی {1 سفید، 4 سفید، 3 سیاه، 2 سیاه} هم دیده شوند. در این جا به تناقض می رسیم. (چرا؟) چون از خانه های هر عدد به تعداد برابر در جدول داریم، پس اگر مجموعه ی A را خانه های با عدد 1 و 4 در نظر بگیریم و مجموعه ی B را خانه های با عدد 2 و 3، باید بتوانیم هر عضو از B را با هر عضو از A متناظر کنیم. هر عضو را یکبار می بینیم و وقتی یک عضو از A را می بینیم، دوباره عضو دیگری از A را نمی بینیم (در گراف قابل مشاهده است) پس زمانی که از 2 سفید یا 3 سفید وارد 3 سیاه یا 2 سیاه می شویم تعداد بیشتری از خانه های B دیده ایم و از آنجایی که همانطور که گفته شد هیچ دو خانه ای از A پشت سر هم دیده نمی شوند، پس این اختلاف دیده شدن برای خانه های مجموعه ی B و A بعداً درست نمی شود، در حالی که بایستی تعداد مساوی خانه از این دو مجموعه در طول حرکات اسب دیده شود، پس امکان ندارد که بطور گفته شده مهره ی اسب خانه های جدول $4 × n$ را طی کند.

2016-11-24 09:16:38 -0500
مهدی امیری 389 ● 5 ● 9 ● 14
پاک‌کردن   ویرایش پاسخ
نظرات

افرین. درسته. +1

2016-12-02 05:34:29 -0500 حمید کاملی

پاسخ شما

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

پیش‌نمایش:

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