المپیاد سوالات ترکیبیات و مباحث ویژه !

[ROZHIN kocholoo]

پاسخ : سوالات ترکیبیات

اونجوری هم امتحان کردم ولی مستقیم به جواب 2 رسیدم بدون اینکه به جواب یک برسم.
اگر سورتشون هم کنیم همون حالتی که توضیح دادم درمیاد.(همون حالت قطریه)

 

[عمو ژپتو]

پاسخ : سوالات ترکیبیات

اونجوری هم امتحان کردم ولی مستقیم به جواب 2 رسیدم بدون اینکه به جواب یک برسم.
اگر سورتشون هم کنیم همون حالتی که توضیح دادم درمیاد.(همون حالت قطریه)

خوب یک در مورد راه حل تون توضیح بدید که ما هم بفهمیم و کامل کنیم باهم

 

[parand]

پاسخ : سوالات ترکیبیات

ميشه اينطوري بگيم؟
قسمت يكش:
كوكترين و بزرگترين اعداد اين جدول رو در نظر ميگيريم، اين دو تا حداكثر 2n-2 تا ميتونن با هم اختلاف داشته باشن(يعني تو دورترين حد از هم باشند يعني روي دو تا راس غير مجاور باشند)
كه يعني حداكثر1-2n عدد هست تو جدول
و چون n*n=n^2 عدد هست تو جدول طبق لانه كبوتري(تعميمش البته!)حداقل يك عدد هست كه حداقل (n^2/(2n-1 بار تكرار شده تو جدول كه اين عدد از

يه ذره بيشتره حتي!

 

[ROZHIN kocholoo]

پاسخ : سوالات ترکیبیات

من اینجوری گفتم که اول اون 2nعدد (n-....n)رو بدون در نظر گرفتن قوانین تو جدول می ذاریم که دو سطر رو می گیرند .اگر همین روند رو ادامه بدیم هر عددn/2بار دیده می شه.حالا اعداد رو بر اساس اون قانونا می ذاریم که علاوه بر این که نوع چینش اعدادمون تغییر می کنه بعضی از اعداد تعداد تکرارشون کم می شه بنابراین طبق اصل ل.ک گروهی تعدادشون کمتر از n/2و گروهی بیش تر از n/2می شه بنابراین عدد یا اعدادی وجود دارند که تعدادشون از n/2یش تره.
برای بخش 2از همون اول اعداد رو با رعایت قوانین می چینیم یک عدد (ترجیحا بزرگترین)رو یه گوشه ی جدول می ذاریم و بقیه اعداد بدون تکرار عمدی به صورت یکتا قرار می گیرن
1- 2- 3- 4- 5-
0 1- 2- 3- 4-
1 0 1- 2- 3-
2 1 0 1- 2-
3 2 1 0 1-
خب تو اون مثال می بینید که تکرار ها به صورت اریبه و رو قطر اصلی هم فقط یک عدد تکرار شده که تعدادش همون nمی شه
اگر هم سعی کنیم مثلا به جای 3- 4- بذاریم(تکرار عمدی)تو خونه سمت راست و ژایینش 3- قرار می گیره پس با هر تکرار عمدی عددی که حذف شد تعدادش یکی بیشتر می شه
که باز هم تعدادn پایداره.

 

[عمو ژپتو]

پاسخ : سوالات ترکیبیات

راستی یه سوال
نمیتونیم بگیم که مثلا اگه کوچیکترین عدد جدول 5 باشه بزرگترینش حداکثر 10
ببخشید راه حل دوتا بالایی رو ندیدم
خوب من میگم نمیشه قوی ترش کرد؟

 

[ROZHIN kocholoo]

پاسخ : سوالات ترکیبیات

در حالت عادی تو اون مثاله اگه کوچکترین عدد 5 باشه بزرگترین 13 می شه ولی اگه تکرار عمدی داشته باشه چرا که نشه.

 

[عمو ژپتو]

پاسخ : سوالات ترکیبیات

من این دوتا راه حلتون رو که خوندم به نظرم هیچکدوم درست نمیاد
کسی حل نکرده اینو
من دوسه تا ایده به زهنم رسید اما خوب هیچکدوم جواب ندادن
مثلا ببینید میایم میگیم تمام اعداد رو ازشون کم میکنیم جوری که کوچیکترن عدد 0 باشه
خوب این مشکلی نیست به طبع
حالا اگه بزرگترین عدد n باشه که مسئله حله
حالا اگه بزرگترین عدد kباشه که k>n اونوقت اگه یکم روش کار شه به نظرم به نتیجه میرسه
مثلا اگه یدونه k باشه پس حتما 2 تا k-1حداقل هست و چون گفتیم 1 دونه باشه پس حداقل 3 تاk-2 هست....
و خوبیش اینه که چون k>n و این روند یکی یکی میره پس به عددی میرسیم که تعدادش بیشتر از n ولی خوب یکم مشکل داره
یه نکته دیگه هم که هست چون تو جدول 0 داریم پس k فاصلش تا 0 هم یه چیزیه که میشه روش کار کرد و k نمیتونه همه جا باشه....
خوب همه بیاید یکم باهم روش فکر کنیم حل شه دیگه

 

[ROZHIN kocholoo]

پاسخ : سوالات ترکیبیات

1- دقت داشتید که تو سئوال گفته اعداد صحیح هستند ؟
منم تقریا همون کار شما رو کردم ولی اعدادم محدوده از n-تا n بنابراین kمن هیچ وقت از n بیش تر نمی شد .

برای بخش 2از همون اول اعداد رو با رعایت قوانین می چینیم یک عدد (ترجیحا بزرگترین)رو یه گوشه ی جدول می ذاریم و بقیه اعداد بدون تکرار عمدی به صورت یکتا قرار می گیرن
1- 2- 3- 4- 5-
0 1- 2- 3- 4-
1 0 1- 2- 3-
2 1 0 1- 2-
3 2 1 0 1-

منظور از تکرار قطری اینه که به قول شما kیکی باشه.

حالا اگه بزرگترین عدد kباشه که k>n اونوقت اگه یکم روش کار شه به نظرم به نتیجه میرسه
مثلا اگه یدونه k باشه پس حتما 2 تا k-1حداقل هست و چون گفتیم 1 دونه باشه پس حداقل 3 تاk-2 هست....
و خوبیش اینه که چون k>n و این روند یکی یکی میره پس به عددی میرسیم که تعدادش بیشتر از n ولی خوب یکم مشکل داره

تا این جا راه مشابه راه من بود فقط با اون تفاوتی که گفتم.

یه نکته دیگه هم که هست چون تو جدول 0 داریم پس k فاصلش تا 0 هم یه چیزیه که میشه روش کار کرد و k نمیتونه همه جا باشه....
خوب همه بیاید یکم باهم روش فکر کنیم حل شه دیگه

از این تیکه هیچی نفهمیدم واضح تر توضیح بدین

 

[ROZHIN kocholoo]

پاسخ : سوالات ترکیبیات

دوستان دیگر تمنا دارم شما هم شرکت کنید
مگه قرار نبود گروهی بحلیم پس چی شد

 

[sayna]

پاسخ : استقرا

چرا سوال نمیذارید ؟ قرار نیست حتما ِ حتما هم حل بشه ، خوبیه این جور تاپیکا اینه که راجع به یه سوال می‌شه کلی بحث کرد ، ایده جدید برای حلش داد و اینا ! در کل خواستم بگم تاپیک نخوابه :د