جدول 2nدر2n

[fereidoon]

تعدادي مهره سفيد و تعدادي مهره سياه در برخي از خانه هاي يك جدول2nدر2nداريم,كه در هر خانه هاي ان حداكثر يكي از مهره هاي سفبد و مشكي قرار دارد.ابتدا هر مهره سياهي را كه حداقل با يك مهره سفيد در ستون قرار دارد از جدول حذف مي كنيم.سپس هر مهره سفيدي را كه حداقل با يك مهره سياه در يك سطر قرار دارد حذف مي كنيم,ثابت كنيد رنگي وجود دارد كه تعداد مهره هاي از ان رنگ از n^2 بيشتر نيست.
:53:

 

[hh1546]

پاسخ : جدول 2nدر2n

فکر کنم سوال غلطه
مثلا اگه کل خانه های جدول مهره سیاه باشد چی میشه:4:

 

[Aref]

پاسخ : جدول 2nدر2n

فکر کنم سوال غلطه
مثلا اگه کل خانه های جدول مهره سیاه باشد چی میشه:4:

در اون صورت تعداد خانه های سفید از n^2 کمتر است.:5:

 

[mimilad]

پاسخ : جدول 2nدر2n

فرض خلف میکنیم اگه حکم برقرار نباشه با توجه به این که مجموع مساحت خانه های سیاه و مجموع مساحت خانه های سفید هرکدام بیشتر از یا مساوی N^2+ 1 میشود ÷س هر کدام از خانه های سیاه و سفید حداقل در n+1 تا از سطر ها و یا n+1 تا از ستون ها قرار دارند اگر هر کدام از رنگ ها در n+1 تا از سطر ها , یا هر کدام از رنگ ها در n+1 تا از ستون ها مهره داشته باشند تناقض است ÷س از یکی از رنگ ها حداقل در n+1 تا از ستون ها (مثلا سیاه ) و از یکی از رنگ ها حداقل در n+1 تا از سطر ها مهره وجود دارد .
حا ل مهره های سیاه و سفید اگر هر کدام دقیقا n+1 سطر و دیگری n+1 ستون را مهره ای داشته باشند حداکثر هر کدام n^2 -1 مهره خواهند داشت که این تناقض است و اگر خانه های سفید بیشتر از n+1 سطر یا سیاه ها بیشتر از n+1 ستون را ب÷وشانند تناقض است ÷س اگر این n+1 بخواهد افزایش ÷یدا کند برای مهرهای سیاه و سفید هر دو باید افزایش ÷یدا کند که در این صورت تعداد خانه هایی که میتوانند ب÷وشانند کاهش ÷یدا میکند که باز هم تناقض است ÷س فرض اولیه غلط و حداقل تعداد یکی از مهره ها بیشتر از n^2 نخواهد بود .

 

[mojtabaaa1373]

پاسخ : جدول 2nدر2n

با گراف دوبخشی جهت دار و یه حسابی هندسی بدیهی میشه.

 

[fereidoon]

پاسخ : جدول 2nدر2n

راه حل منم مثل اقا مجتبي ست,اين سوال امتحانمون بود همه اونايي كه حل كردن راه حشون همين بود!