AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#1
به درخواست یکی از دوستان ماراتن ترکیبیات رو هم راه اندازی می کنم . به امید خدا این تاپیک هم رونق داشته باشه ! و خوب بره جلو
قوانینش هم مشخصه دیگه تا یه سوال حل نشده سوال جدید نذاره . اگر هم میشه شماره سوال رو بذارید تا معلوم باشه
و اینکه تا حد امکان لینک از جایی ندید دیگه اگه یه سوال حل نشد مجبور شدید لینک بدید . باتشکر !! و یکی اینکه اگه سوالی رو میدونید سوال کدوم کشوره بعد از حلش بگید

1

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

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#2
پاسخ : ماراتن ترکیبیات

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

1

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

ب)اگر حداکثر 6 ستاره داشته باشیم
) دو سطر وجود دارند که حداقل دو ستاره دارند .
) یک سطر وجود دارد که حداقل 3 ستاره دارد .

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


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

darya.f

New Member
ارسال ها
182
لایک ها
114
امتیاز
0
#3
پاسخ : ماراتن ترکیبیات

الف)اگر فرض کنیم بیانگر سطر ستون باشد ما باید خانه های را بپوشانیم .ب)اگر حداکثر 6 ستاره داشته باشیم ) دو سطر وجود دارند که حداقل دو ستاره دارند .) یک سطر وجود دارد که حداقل 3 ستاره دارد .هرکدام از حالات را در نظر بگیریم مسئله به سادگی حل میشه .2در هرخانه از جدول 10*10 یکی از اعداد 1 تا 10 نوشته شده میگوییم 2 خانه مجاور هستند اگر حداقل یک راس مشترک داشته باشند . هر دو عددی که در 2 خانه مجاور قرار دارند نسبت به هم اولند ثابت کنید عددی وجود دارد که حداقل 17 بار نوشته شده است .
جدول رو به خانه هاى 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

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#4
پاسخ : ماراتن ترکیبیات

جدول رو به خانه هاى 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]

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

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#5
پاسخ : ماراتن ترکیبیات

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

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#6
پاسخ : ماراتن ترکیبیات

200 تا نميشه؟
 

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#7

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#8
پاسخ : ماراتن ترکیبیات

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

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#9
پاسخ : ماراتن ترکیبیات

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

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#10
پاسخ : ماراتن ترکیبیات

نه سوال درسته جواب هم درسته اما اگر بین هر دو نقطه ی سفید حداقل یه نقطه سیاه باشه کمتر از 2500 میشه حالا چطور ؟
شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
 

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#11
پاسخ : ماراتن ترکیبیات

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
اصل سوال سوال 2 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

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

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

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

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

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

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.

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

شما منظورتون كدوم سواله؟
سوالي رو كه شما نوشتين واضحه كه توي هر رديف حداكثر دو تا نقطه رو ميشه سفيد كرد پس كران بالا ميشه 200
اصل سوال سوال 3 م2 1378 . شما برو خودت ببین فقط اونجا گفته درخت سالم و بریده شده.
 

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#12
پاسخ : ماراتن ترکیبیات

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

 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#13
پاسخ : ماراتن ترکیبیات

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

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

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#14
پاسخ : ماراتن ترکیبیات

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

mahmoud20ni

New Member
ارسال ها
18
لایک ها
13
امتیاز
3
#15
پاسخ : ماراتن ترکیبیات

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

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#16
پاسخ : ماراتن ترکیبیات

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

mahmoud20ni

New Member
ارسال ها
18
لایک ها
13
امتیاز
3
#17
پاسخ : ماراتن ترکیبیات

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

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#18
پاسخ : ماراتن ترکیبیات

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

Dadgarnia

New Member
ارسال ها
1,350
لایک ها
1,127
امتیاز
0
#19
پاسخ : ماراتن ترکیبیات

منظورتون رو نمیفهمم که میگید کل جدول باید حذف بشه مثلا اگر عدد انتخابی x_1 باشد سطر اول که همگی درایه های ان 1 و یا همگی صفر میباشد حذف میشود . (x_1 در تعیین درایه ی دیگری مگر تاثیری دارد ؟؟؟)
بله اثبات شما درسته. اشتباه از من بود. راه ديگه هم مي تونه استفاده از اين باشه كه:
5
در هر خانه از يك جدول
علامت + يا - نوشته شده است. در هر مرحله مي توانيم يك سطر يا يك ستون را انتخاب و همه ي علامت هاي آن را عوض كنيم. فرض كنيد وضعيت اوليه به گونه اي باشد كه بتوان در چند مرحله به جدولي رسيد كه همه ي علامت هاي آن مثبت باشند. ثابت كنيد اين كار را حداكثر در n مرحله مي توان انجام داد.

 

mahmoud20ni

New Member
ارسال ها
18
لایک ها
13
امتیاز
3
#20
پاسخ : ماراتن ترکیبیات

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