آمار پرسش:

  • پرسیده شده: 2016-04-08 05:23:27 -0500
  • مشاهده شده: 366 بار
  • بروز شده: 2016-04-08 05:27:08 -0500

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

علائم ریاضی:

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

دوره ۱۲ - روز اول - مسأله‌ی یک - جدول پر یک

2

متن سوال دوره ۱۲- روز نخست - سوال یک - جدول پر یک‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌

2016-04-08 05:23:27 -0500
توفیقی 1621 ● 17 ● 21 ● 42
پاک‌کردن   ویرایش سوال
نظرات

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 08:49:17 -0500 امیر شکری

1 پاسخ

2

لم۱: در این جدول حداقل یک ستون وجود دارد که تعداد یک‌های آن بیشتر یا مساوی با تعداد صفر‌های آن باشد:با برهان خلف لم را ثابت می‌کنیم، فرض کنید چنین نباشد، پس تعداد ۱های هر ستون کمتر از 2^(k-1) است پس تعداد‌یک‌های جدول از n×2^(k-1) کمتر است، از طرفی تعداد یک‌های هر سطر حداقل n/2 است پس تعداد یک‌های جدول از (2^k n)/2=n×2^(k-1) بیشتر یا مساوی است، که این دو با هم تناقض دارند! پس فرض خلف باطل و حکم ثابت است.مسئله‌ی اصلی:حکم مسئله را با استقرا بر روی k حل می‌کنیم. حکم برای k=1 غلط است! مثال: ۰ ۱۱ ۰برای k=2 حکم درست است:طبق لم۱، تعداد یک‌های یکی از ستون‌ها حداقل ۲ است، اگر ستونی با تعداد یک‌های ۳ یا ۴ وجود داشته باشد حکم بدیهی است، اگر ۴ باشد که این ستون را رنگ کرده و مسئله حل می‌شود و اگر ۳ باشد، این ستون را رنگ می‌کنیم، ردیف دیگر حداقل در یکی از ستون‌ها یک دارد، آن ستون را نیز رنگ می‌کنیم و برنده می‌شویم.اگر تعداد ۱‌ها برابر با ۲ باشد. باید تعداد یک‌های هر ستون برابر با ۲ باشد، (در غیر اینصورت مجموع کل ۱ ها کمتر از (2^k n)/2=n×2^(k-1) می‌شود) یکی از ستون‌ها را انتخاب می‌کنیم و دو ردیف حل شدند، n-1 ستون و ۲ سطر باقی مانده است که در هر سطر حداقل n/2 تا یک قرار گرفته، پس در مجموع توی این دو سطر حداقل nتا یک قرار دارد و چون n>n-1 پس حداقل این دو سطر در یک ستون اشتراک دارند (ستونی وجود دارد که هردو سطر در آن یک باشند)، این ستون را نیز رنگ می‌کنیم و مسئله برای پایه‌ی استقرا حل می‌شود.همچنین اگر تعداد ردیف‌ها کمتر از ۴ بود، فرض می‌کنیم تعدادی ردیف تمام یک داریم تا تعداد ردیف‌ها ۴ تا شود.فرض می‌کنیم اگر k=l باشد، به ازای هر جدول با کمتر یا مساوی با 2^l سطر و n ستون از صفر و یک که تعداد یک‌های هر سطر از صفر‌هایش بزرگتر یا مساوی باشد، می‌توانیم l خانه را رنگ کرده که هر سطری حداقل یک خانه‌ی یک‌ِ رنگ‌شده داشته باشد.آنگاه نتیجه می‌گیریم حکم برای k=l+1 نیز برقرار است.طبق لم۱، حداقل یکی از ستون‌ها دارای 2^l تا یک است. این ستون را رنگ می‌کنیم و مستطیل جدیدی می‌سازیم که این ستون و تمام سطر‌هایی که این ستون در آن یک بوده است حذف شده‌اند.جدول جدید حداکثر 2^(l+1)-2^l=2^l ردیف و دقیقا n-1 ستون دارد، همچنین تعداد یک‌های هر ردیف از تعداد صفر‌های آن بیشتر یا مساوی است. (زیرا تعداد صفر‌ها یک واحد کم شده و تعداد یک‌ها تغییری نکرده است) پس طبق فرض استقرا می‌توان با رنگ کردن l ستون از جدول جدید، از هر سطر در جدول جدید حداقل یک خانه‌ی یک رنگی داشته باشد، اگر متناظر این ستون‌ها را در جدول اصلی رنگ کنیم، ردیف‌های متناظر با آن نیز رنگ می‌شوند و بقیه‌ی ردیف‌ها نیز توسط اولین رنگ که طبق لم۱ انجام دادیم درست شدند. پس با رنگ‌کردن l+1 به هدف رسیدیم. پس فرض استقرا ثابت و حکم برای همه‌ی kهای طبیعی بزرگتر از ۱ ثابت شد.

2016-04-08 05:27:08 -0500
توفیقی 1621 ● 17 ● 21 ● 42
پاک‌کردن   ویرایش پاسخ
نظرات

این پاسخ واسه کجاست ؟؟

2016-04-09 06:20:28 -0500 سلام

@سلام واسه خودم :-)

2016-04-09 09:47:18 -0500 توفیقی

پاسخ شما

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

پیش‌نمایش:

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