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

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

آمار پرسش:

  • پرسیده شده: 2014-06-29 01:53:55 -0500
  • مشاهده شده: 574 بار
  • بروز شده: 2015-01-05 03:11:15 -0500

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

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

تعداد مثلث های پوشاننده

تعداد جواب های معادله ${1\over x}+{1\over y}={1\over n}$ در دستگاه اعداد صحیح

Flip Sort

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

یکی کردن علامت خانه‌های یک جدول $4\times 4$ از + و - ها

تبدیل جدول با چرخش‌های ساعتگرد مربع $2\times 2$

دو زیرمجموعه فرد و زوج از مجموعه {۱، 2، 3، ...64}

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

جدولی $2010\times 2010$ امکان رسیدن به جدولی که همه مهره ها در یک خانه جمع شوند

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

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

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

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

علائم ریاضی:

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

حداکثر رنگهای ممکن برای رنگ آمیزی جدول 10*10 با داشتن حداکثر 5 رنگ در هرسطر و هر ستون

6

یک جدول 10 در 10 داریم به طوری که هر خانه ی ان را با رنگی رنگ امیزی میکنیم حداکثر تعداد رنگ های ممکن رابیابید که بتوان خانه های جدول را به گونه ای با ان رنگ کرد که در هر سطر و ستون حداکثر 5 رنگ قرار گیرد ؟

ترکیبیات شمارشی
2014-06-29 01:53:55 -0500
چشمک 2291 ● 29 ● 67 ● 119
پاک‌کردن   ویرایش سوال
نظرات

مطمئنین حداکثر ؟؟؟؟؟؟

فک کنم سوال این بوده :

حداقل تعداد رنگ های ممکن رابیابید که بتوان خانه های جدول را به گونه ای با ان رنگ کرد که در هر سطر و ستون حداکثر 5 مختلف رنگ قرار گیرد

2014-06-29 02:54:00 -0500 هه هه هه

@هه هه هه جان حداقلش که معلومه یک هست

2014-06-29 04:37:04 -0500 کلاه قرمزی

با ۳۷ رنگ میشه:‌ مربع ۴ در ۴ که تقاطع ۴ سطر و ۴ ستون اول هست رو با اعداد ۱ تا ۱۶ پر میکنیم، مربع ۴ در ۴ بعدی که در تقاطع سطر و ستونهای ۵ تا ۸ هست رو با اعداد ۱۷ تا ۳۲ پر میکنیم، مربع ۲ در ۲ که در تقاطع سطروستونهای ۹و۱۰ هست رو با اعداد ۳۳ تا ۳۶، بقیه خانه ها هم عدد ۳۷ رو میگذاریم. بیشترش رو نمیدونم

2014-06-29 23:47:35 -0500 کلاه قرمزی

من با 38 رنگ تونستم فقط اثبات کمینه بودنش سخت است مثه آقای کلاه قرمزی فقط اون آخرش که می که بقیه خونه ها بهتره که خونه های سمت راست پایین رو 37 و خونه های بالا سمت چپ رو 38 و انطوری هم حکم برقراره و هم 38 رنگ

2014-06-30 00:34:25 -0500 طوفان

@طوفان جان راه حل ۳۸ شما درسته؟ فکر کنم سطرها یا ستونهای وسط جدول ۶ رنگی میشن این طوری

2014-06-30 01:13:43 -0500 کلاه قرمزی

1 پاسخ

5

پاسخ مسئله برابر 41 می باشد image description

به راحتی می توان دید که مثال بالا بی نقض می باشد .

قطر اصلی به رنگ 41 باشد و پنج در پنج گوشه سمت راست تمام خانه هایش جز قطر اصلی که رنگ 41 ام میباشد رنگهای متفاوت 1 تا 20 را به خود گیرند .پنج در پنج در چهار گوشه پایین چپ هم همانند قبلی رنگهای 21 تا 40 را به خود گیرند بقیه ی جدول هم رنگ 41 به راحتی می توان دید که شرایط مسئله برقرار است.

حال اثبات کمینه بودن :

فرض کنید 42 رنگ متمایز استفاده کردیم . پس طبق اصل لانه کبوتر دو سطر هستند که 5 رنگ متمایز در هر یک استفاده شده است . بدون از دست دادن کلیت فرض کنید سطر های یک و دو میباشند . پس سطر یک اعداد 1 تا 5 و سطر 2 اعداد 6 تا 10 فرض کنید .

حال برای 8 در 10 باقیمانده (بدون دو سطر اول) حداقل 32 رنگ مانده که باز هم طبق اصل لانه کبوتری ستونی در 8 در 10 هست که چهار رنگ استفاده کرده حال به آن ستونی که چهار رنگ دارد توجه کنید چهار رنگ در آن 8 در 10 دارد(از اعداد 11 تا 32) و رنگ متمایز هم مال آن دو سطر یک(x متعلق به 1 تا 5) و دو (y متعلق به 6 تا 10) پس شش رنگ در این ستون وجود دارد تناقض حاصل 41 را به اثبات می رساند .

19017470652948523690.png مشکلات راه حل برطرف شد :|

اگر بازهم مشکلی می بینید بفرمایید و گرنه امتیاز فراموش نشود P;

2014-07-10 05:52:22 -0500
طوفان 1480 ● 11 ● 21 ● 43
پاک‌کردن   ویرایش پاسخ
نظرات

ممنون +1 آفرین طوفان

2014-07-10 06:07:29 -0500 چشمک

دمت گرم با این سوال یه هفته علافش بوودم :)

2014-07-10 06:20:08 -0500 طوفان

دمت گرم با این سوال یه هفته علافش بوودم :)

2014-07-10 06:20:08 -0500 طوفان

اصلا متوجه جواب نمیشم. هر مربع ۴ در ۴ حاوی ۱۶ خانه هست، چطور براش ۲۰ رنگ استفاده کردیم؟ ضمنا چطور با لانه کبوتری فهمیدیم دو سطر هستند که ۵ رنگ استفاده شده در هریک کاملا متمایز هستند؟ مثلا اگر همه ستون اول به رنگ ۱ در اومده باشه در اون حالت هیچ دو سطری با این خاصیت وجود نخواهند داشت، چه تناقضی هست؟

2014-07-10 13:20:39 -0500 کلاه قرمزی

اصلا متوجه جواب نمیشم. هر مربع ۴ در ۴ حاوی ۱۶ خانه هست، چطور براش ۲۰ رنگ استفاده کردیم؟

2014-07-10 13:20:40 -0500 کلاه قرمزی

پاسخ شما

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

پیش‌نمایش:

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