ماراتن ترکیبیات

AHZolfaghari · 1393/6/7

به درخواست یکی از دوستان ماراتن ترکیبیات رو هم راه اندازی می کنم . به امید خدا این تاپیک هم رونق داشته باشه ! و خوب بره جلو
قوانینش هم مشخصه دیگه تا یه سوال حل نشده سوال جدید نذاره . اگر هم میشه شماره سوال رو بذارید تا معلوم باشه
و اینکه تا حد امکان لینک از جایی ندید دیگه اگه یه سوال حل نشد مجبور شدید لینک بدید . باتشکر !! و یکی اینکه اگه سوالی رو میدونید سوال کدوم کشوره بعد از حلش بگید

1

یک جدول 4 در 4 در اختیار داریم .
الف ) هفت ستاره در این جدول قرار داده ایم . نشان دهید می توان این هفت تا را طوری چید که هرگاه دو سطر و دو ستون را حذف کنیم دست کم یک ستاره درجدول باقی بماند .
ب) نشان دهید برای کم تر از 7 تا امکان پذیر نیست .

math1998 · 1393/6/7

پاسخ : ماراتن ترکیبیات

AHZolfaghari گفت

الف)اگر فرض کنیم

$a_{i,j}$

بیانگر سطر

$i$

ستون

$j$

باشد ما باید خانه های

$a_{1,2},a_{1,3},a_{2,2},a_{2,4},a_{3,3},a_{3,4},a_{4,1},$

را بپوشانیم .

ب)اگر حداکثر 6 ستاره داشته باشیم

$i$

) دو سطر وجود دارند که حداقل دو ستاره دارند .

$ii$

) یک سطر وجود دارد که حداقل 3 ستاره دارد .

هرکدام از حالات را در نظر بگیریم مسئله به سادگی حل میشه .

2
در هرخانه از جدول 10*10 یکی از اعداد 1 تا 10 نوشته شده میگوییم 2 خانه مجاور هستند اگر حداقل یک راس مشترک داشته باشند . هر دو عددی که در 2 خانه مجاور قرار دارند نسبت به هم اولند ثابت کنید عددی وجود دارد که حداقل 17 بار نوشته شده است .

darya.f · 1393/6/7

پاسخ : ماراتن ترکیبیات

math1998 گفت

جدول رو به خانه هاى 2×2 افراز مىکنىم,در هر مربع 2×2 باىد ىکى از اعداد 2،4،6،8،10 و از اعداد 3،9 هم همىنطور .پس در کل 25 تا از دسته 1 و 25 تا از دسته دوم دارىم .پس 50 عدد دارىم با 3نوع 1،5،7 که نتىجه مىشه از ىکىشون حداقل 50/3=~17 تا دارىم

2
در هرخانه از جدول 10*10 یکی از اعداد 1 تا 10 نوشته شده میگوییم 2 خانه مجاور هستند اگر حداقل یک راس مشترک داشته باشند . هر دو عددی که در 2 خانه مجاور قرار دارند نسبت به هم اولند ثابت کنید عددی وجود دارد که حداقل 17 بار نوشته شده است .[/quote]

math1998 · 1393/6/7

پاسخ : ماراتن ترکیبیات

darya.f گفت

[/quote]

درسته این ایده ی حیاطی توی سوالات لانه کبوتریه برای اینکه بالفرض عدد 100 بزرگه و شما نمیتونید باهاش خوب کار کنید پس باید به چیزای کوچکتر بشکنیدش حالا یه سوال دیگه باهمین ایده
3
فرض کنید شبکه ای 100*100 از نقاط 10000 سیاه با فاصله یکسان داریم حداکثر چند نقطه را میتوان سفید کرد طوری که در فاصله ی هر دو نقطه ی سفید نقطه ی سفید دیگری نباشد این سوال دارای ایده های مهمی برای حل سوالات ترکیبیات دارد .

math1998 · 1393/6/8

پاسخ : ماراتن ترکیبیات

سوال خیلی خوبیه روش فکر کنید

Dadgarnia · 1393/6/8

پاسخ : ماراتن ترکیبیات

200 تا نميشه؟

math1998 · 1393/6/8

پاسخ : ماراتن ترکیبیات

Dadgarnia گفت

نه از همون ایده ی افراز استفاده کنید یه کران بدست بیارید و اثباتش کنید

Dadgarnia · 1393/6/8

پاسخ : ماراتن ترکیبیات

math1998 گفت

فكر كنم سوالو اشتباه نوشتين. احتمالا درستش اينجوريه كه توي خط واصل هر دو نقطه ي سفيد حداقل يه نقطه ي سياه باشه اگه اينجوري باشه جوابش 2500 ميشه.

math1998 · 1393/6/8

پاسخ : ماراتن ترکیبیات

Dadgarnia گفت

نه سوال درسته جواب هم درسته اما اگر بین هر دو نقطه ی سفید حداقل یه نقطه سیاه باشه کمتر از 2500 میشه حالا چطور ؟

Dadgarnia · 1393/6/8

پاسخ : ماراتن ترکیبیات

math1998 گفت

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200

math1998 · 1393/6/8

پاسخ : ماراتن ترکیبیات

Dadgarnia گفت

اصل سوال سوال 2 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

---- دو نوشته به هم متصل شده است ----

Dadgarnia گفت

اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

---- دو نوشته به هم متصل شده است ----

Dadgarnia گفت

اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

---- دو نوشته به هم متصل شده است ----

Dadgarnia گفت

اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

---- دو نوشته به هم متصل شده است ----

Dadgarnia گفت

اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

Dadgarnia · 1393/6/8

پاسخ : ماراتن ترکیبیات

راه حل:
شبكه رو به 2500 مربع دو در دو افراز مي كنيم. واضحه كه در هر مربع حداكثر يك نقطه رو مي توانيم سفيد كنيم. پس حداكثر 2500 تا نقطه ي سفيد خواهيم داشت. ثابت مي كنيم اين كار امكانپذير است. دستگاه مختصات رو به گونه اي مي گيريم كه طول و عرض هر نقطه از اعداد يك تا صد باشه. نقاطي رو در نظر مي گيريم كه كه طول و عرض آن ها زوج باشه. تعداد اين نقاط 2500 تاست. فرض كنيد جفت نقاطي موجود باشه كه روي خط واصلشون فقط نقاط سفيد باشه. جفت نقطه اي رو در نظر بگيريد كه كمترين فاصله رو داشته باشند واضحه كه نقطه ي وسط پاره خط واصلشون عدد صحيحه و رنگش هم سفيده پس ما دو تا نقطه با فاصله ي كمتر رو پيدا كرديم و به تناقض مي رسيم. پس 2500 نقطه ي ذكر شده خاصيت مورد نظر رو دارند.
4
اعداد حقيقي

$y_1,y_2,\cdots,y_n,x_1,x_2,\cdots,x_m$

داده شده است. فرض كنيد

$A=[a_{ij}]$

ماتريسي

$m\times n$

باشد كه در آن

$a_{ij}$

برابر 1 است اگر

$x_i+y_j\geq 0$

و در غير اين صورت برابر صفر است و فرض كنيد B ماتريسي

$m\times n$

با درايه هاي 0 و 1 باشد به طوري كه مجموع درايه هاي هر سطر B با مجموع درايه هاي سطر متناظر در A و مجموع درايه هاي هر ستون B با مجموع درايه هاي هر ستون متناظر در A برابر است. ثابت كنيد

$A=B$

sa1378 · 1393/6/9

پاسخ : ماراتن ترکیبیات

Dadgarnia گفت

راه حل:
شبكه رو به 2500 مربع دو در دو افراز مي كنيم. واضحه كه در هر مربع حداكثر يك نقطه رو مي توانيم سفيد كنيم. پس حداكثر 2500 تا نقطه ي سفيد خواهيم داشت. ثابت مي كنيم اين كار امكانپذير است. دستگاه مختصات رو به گونه اي مي گيريم كه طول و عرض هر نقطه از اعداد يك تا صد باشه. نقاطي رو در نظر مي گيريم كه كه طول و عرض آن ها زوج باشه. تعداد اين نقاط 2500 تاست. فرض كنيد جفت نقاطي موجود باشه كه روي خط واصلشون فقط نقاط سفيد باشه. جفت نقطه اي رو در نظر بگيريد كه كمترين فاصله رو داشته باشند واضحه كه نقطه ي وسط پاره خط واصلشون عدد صحيحه و رنگش هم سفيده پس ما دو تا نقطه با فاصله ي كمتر رو پيدا كرديم و به تناقض مي رسيم. پس 2500 نقطه ي ذكر شده خاصيت مورد نظر رو دارند.
4
اعداد حقيقي

$y_1,y_2,\cdots,y_n,x_1,x_2,\cdots,x_m$

داده شده است. فرض كنيد

$A=[a_{ij}]$

ماتريسي

$m\times n$

باشد كه در آن

$a_{ij}$

برابر 1 است اگر

$x_i+y_j\geq 0$

و در غير اين صورت برابر صفر است و فرض كنيد B ماتريسي

$m\times n$

با درايه هاي 0 و 1 باشد به طوري كه مجموع درايه هاي هر سطر B با مجموع درايه هاي سطر متناظر در A و مجموع درايه هاي هر ستون B با مجموع درايه هاي هر ستون متناظر در A برابر است. ثابت كنيد

$A=B$

چرا نمیشه توی مربع 2x2 دو تا نقطه سفید باشن؟یا حتی 4 نقطه؟
سوال گفته بین هر دو نقطه سفید نقطه دیگری نباشه
الان مثلا اینجوری:

math1998 · 1393/6/9

پاسخ : ماراتن ترکیبیات

sa1378 گفت

ببخشید منظورم این بود که نتونیم از هر نقطه سفید نقطه ی سفید دیگه ای رو ببینیم اصل سوال هم گفتم چی بود .

mahmoud20ni · 1393/6/9

پاسخ : ماراتن ترکیبیات

بر روی m+n استقرا بزنید و عددی که ماکسیمم قدر مطلق را دارد در نظر بگیرید (اگر یکتا نبود ان که مثبت است را در نظر بگیرید ) حال سطر یا ستون مربوط به این عدد یا تماما 1 و یا تماما 0 میباشد ان را حذف کرده و از فرض استقرا استفاده کنید.

Dadgarnia · 1393/6/9

پاسخ : ماراتن ترکیبیات

mahmoud20ni گفت

$x_i$

ها به همه ي ستون ها مربوط مي شن و

$y_i$

ها هم به همه ي سطر ها. اينجوري كه شما مي گيد بايد كل ماتريس رو حذف كرد.

mahmoud20ni · 1393/6/9

پاسخ : ماراتن ترکیبیات

منظورتون رو نمیفهمم که میگید کل جدول باید حذف بشه مثلا اگر عدد انتخابی x_1 باشد سطر اول که همگی درایه های ان 1 و یا همگی صفر میباشد حذف میشود . (x_1 در تعیین درایه ی دیگری مگر تاثیری دارد ؟؟؟)

sa1378 · 1393/6/10

پاسخ : ماراتن ترکیبیات

Dadgarnia گفت

نه حرفشون کاملا درسته
برای m+n=k
اگه بزرگترین عدد مثبت باشه توی اون سطر یا ستون(بستگی داره از x ها باشه یا y ها) همه یک میشن
و برای منفی هم همه صفر میشن
حالا اگه این سطر یا ستون رو حذف کنیم (که این بزرگترین عددمون توی جای دیگه ماتریس هم تاثیری نمیذاره) میرسیم به m+n=k-1 که طبق فرض استقرا درسته

Dadgarnia · 1393/6/10

پاسخ : ماراتن ترکیبیات

mahmoud20ni گفت

بله اثبات شما درسته. اشتباه از من بود. راه ديگه هم مي تونه استفاده از اين باشه كه:

$\sum_{i=1}^{m}\sum_{j=1}^{n}(x_i+y_j)(a_{ij}-b_{ij})=0$

5
در هر خانه از يك جدول

$n \times n$

علامت + يا - نوشته شده است. در هر مرحله مي توانيم يك سطر يا يك ستون را انتخاب و همه ي علامت هاي آن را عوض كنيم. فرض كنيد وضعيت اوليه به گونه اي باشد كه بتوان در چند مرحله به جدولي رسيد كه همه ي علامت هاي آن مثبت باشند. ثابت كنيد اين كار را حداكثر در n مرحله مي توان انجام داد.

mahmoud20ni · 1393/6/10

پاسخ : ماراتن ترکیبیات

برای سوال 5 فرض کنید که k ستون و m سطر تحت عملیات گفته شده تا رسیدن به جدول با درایه های تماما مثبت قرار بگیرند (مشخصا دو بار انتخاب شدن یک سطر با انتخاب نشدن ان تفاوتی ندارد.)حالا میتوان بررسی کرد که با انجام عملیات برروی سطر و ستون های که درروش اول تحت عملیات قرار نگرفته اند نیز میتوان از جدول ابتدایی به جدول با درایه های تماما مثبت رسید.(کافی است یک درایه رو در نظر بگیرید و تعداد بار هایی که تحت تغییر عملیات قرار میگیرد را در دو روش با هم مقایسه کنید.) اکنون چون 2n سطر و ستون وجود دارد در یکی از روش های 1 و 2 حداکثر n مرحله عملیات تا رسیدن به جدول تماما مثبت انجام میگیرد .

ماراتن ترکیبیات

Well-Known Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member