ماراتون مرحله دوّم d:

hoco.hc · 1390/12/12

سلام.
می گما، بیایید بشینیم سوالای مرحله دوّم رو بشینیم حل کنیم و جواباش رو بزاریم اینجا. هم به نفع خودمونه ، هم نوشتنمون قوی می شه و هم بعدیا برامون دعا می کنند.:15: می شینیم از دوره 12 ام شروع می کنیم. ( واقعا نمی دونم چرا گفتم دوره 12 ام )
سوالا رو هم که از سایت کمیته بگیرید.

hoco.hc · 1390/12/12

پاسخ : ماراتون مرحله دوّم d:

دوره 12 ام
روز اوّل

مساله اوّل : جدول پریک

مسئله راحتی بود نسبتا ( نمره اش هم معلومه )
راه حل: استقرا روی k.
لم 1: حتما توی یه جدول

$2^{k}\times n$

،

$2^{k-1}$

سطر و یک ستون وجود داره که همه خانه های این سطر ها توی اون ستون 1 باشند.
اثبات : اوّل بدیهی است که تعداد یک ها بیشتر از

$2^{k}\times \left \lceil \frac{n}{2} \right \rceil$

هست ( توی هر سطر حد اقل

$\left \lceil \frac{n}{2} \right \rceil$

تا یک وجود داره ) ==> (

$m\geqslant 2^{k}\times \left \lceil \frac{n}{2} \right \rceil$

( m تعداد یک های جدول هست ) )
از طرفی اگه هیچ

$2^{k-1}$

سطری وجود نداشته باشه که توی یه ستون مشترکا 1 داشته باشند ، یعنی در هر ستون کمتر از

$2^{k-1}$

تا 1 وجود داره. یعنی

$m< 2^{k-1}\times n$

که این با جمله ی بالا تناقضه. یعنی لم 1 درسته.

اثبات استقرا: با توجه به لم 1 ،

$2^{k-1}$

سطر وجود داره که می شه یه ستون رو انتخاب کرد که همه ی این سطر ها رنگی بشند. بعد این سطرا را حذف می کنیم. و با توجه به فرض استقرا گزاره درسته.

[HR][/HR]پ.ن: سوال 3 درست تایپ شده؟ نوشته بیشتر از mn تا نیست؟

Olympiad · 1390/12/13

پاسخ : ماراتون مرحله دوّم d:

hoco.hc گفت

دوره 12 ام
روز اوّل

مساله اوّل : جدول پریک

مسئله راحتی بود نسبتا ( نمره اش هم معلومه )
راه حل: استقرا روی k.
لم 1: حتما توی یه جدول

$2^{k}\times n$

،

$2^{k-1}$

سطر و یک ستون وجود داره که همه خانه های این سطر ها توی اون ستون 1 باشند.
اثبات : اوّل بدیهی است که تعداد یک ها بیشتر از

$2^{k}\times \left \lceil \frac{n}{2} \right \rceil$

هست ( توی هر سطر حد اقل

$\left \lceil \frac{n}{2} \right \rceil$

تا یک وجود داره ) ==> (

$m\geqslant 2^{k}\times \left \lceil \frac{n}{2} \right \rceil$

( m تعداد یک های جدول هست ) )
از طرفی اگه هیچ

$2^{k-1}$

سطری وجود نداشته باشه که توی یه ستون مشترکا 1 داشته باشند ، یعنی در هر ستون کمتر از

$2^{k-1}$

تا 1 وجود داره. یعنی

$m< 2^{k-1}\times n$

که این با جمله ی بالا تناقضه. یعنی لم 1 درسته.

اثبات استقرا: با توجه به لم 1 ،

$2^{k-1}$

سطر وجود داره که می شه یه ستون رو انتخاب کرد که همه ی این سطر ها رنگی بشند. بعد این سطرا را حذف می کنیم. و با توجه به فرض استقرا گزاره درسته.

[HR][/HR]پ.ن: سوال 3 درست تایپ شده؟ نوشته بیشتر از mn تا نیست؟

به نظرم حل ها رو با رنگ سفید بنویسید !!!!!! (توی قوانین ذکر کنید !!!)

hoco.hc · 1390/12/13

پاسخ : ماراتون مرحله دوّم d:

Olympiad گفت

نه دیگه، سوالا رو که همه دارند، اگه کسی خواست حل رو بزاره یا ببینه میاد اینجا دیگه. حالا چرا با رنگ سفید بنویسیم؟

emadceh · 1390/12/18

پاسخ : ماراتون مرحله دوّم d:

به نظر من از دوره 14 شروع میکردید بهتر بود چون حل دوره1 تا 13 تو کتاب آقای فولادی وجود داره پس اگه نتونیم سوالای اون دوره ها را حل کنیم میشه حلش رو تو اون کتاب یاد گرفت ولی اگه تو دوره های 14 تا 21 مشکل داشته باشیم حل کامل درستش هیچ جا نیست البته بعضیاش به صورت راهنمایی یا یه حل خلاصه تو اینترنت هست ولی مال یکی دو دوره ست.

hoco.hc · 1390/12/18

پاسخ : ماراتون مرحله دوّم d:

emadceh گفت

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

Olympiad · 1391/1/7

پاسخ : ماراتون مرحله دوّم d:

دوره ی 14
سوال 2

emadceh · 1391/1/18

پاسخ : ماراتون مرحله دوّم d:

نمی توان .میشه ثابت کرد که اگه تو حالت اولیه k تا از یه مهره داشته باشیم در پایان هم حداقل k تا از یه مهره دیگه داریم.

emadceh · 1391/1/19

پاسخ : ماراتون مرحله دوّم d:

دوره ی 14
سوال 3

مساله 3: سیاره آلفا ......................................30 امتیاز
در سیاره آلفا اخیرا کشف شده m*n کشور وجود دراد. ...........................(سوالش طولانیه خودتون بقیشو بخونید)

حل:من که فعلا نتونستم حل کنم.اگه ایده ای دارید بگید.

ماراتون مرحله دوّم d:

hoco.hc

New Member

hoco.hc

New Member

Olympiad

New Member

hoco.hc

New Member

emadceh

New Member

hoco.hc

New Member

Olympiad

New Member

emadceh

New Member

emadceh

New Member