ترکیبیات مرحله دویی

[n_maths]

2000 سیب در چند سبد قرار دارند.میتوان سبد ها را حذف کرد یا سیب ها را از سبد ها بیرون آورد.ثابت کنید میتوان ترتیبی داد که تعداد سیب های هر دو سبد باقی مانده برابر باشد و تعداد کل سیب ها از 100 کمتر نباشد.(تورنمنت شهر ها-1988)
(لطفا تو همین تاپیک سوالای مرحله دویی ترکیبیات بذارین تا چند تا تاپیک زده نشه.)

 

[Shabab]

پاسخ : ترکیبیات مرحله دویی

فرض خلف معادل با این است که برای هر عدد k کمتر از ( 100 تقسیم بر k ) سبد وجود دارد که درهر کدام حداقل k سیب باشد. ( چون در غیر اینصورت با حذف بقیه ی سبدها و کمتر کردن سیب های این سبدها به k سیب می توان سبدهای با تعداد مساوی سیب داشت که در مجموع حداقل 100 سیب در آنها باشد )


با فرض خلف و قرار دادن مقادیر مختلف برای k ، برای کل سیب ها کران بالا بزنید...

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

ببخشید،کران بالا یعنی چی؟اکسترمال؟

 

[Shabab]

پاسخ : ترکیبیات مرحله دویی

می گوییم a کران بالایی برای b است اگر b کمتر یا مساوی a باشد.

منظورم این بود که با استفاده از فرض خلف نشان دهید تعداد سیب ها از 2000 کمتر است.
(ضمنا در نوشتن راه حل اشتباهی کردم که اصلاح شده است. )

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

6000 نقطه روی یک دایره با 10 رنگ ،رنگ شده اند به گونه ای که در بین هر 100 نقطه متوالی تمام 10 رنگ ظاهر شده اند.کوچکترین K ای را بیابید که همواره بتوان k نقطه متوالی را پیدا کرد به طوری که هر 10 رنگ را داشته باشد.(امریکا جنوبی-2009)

 

[Shabab]

پاسخ : ترکیبیات مرحله دویی

اگر یکی از رنگ ها را سفید در نظر بگیریم و بقیه ی رنگ ها را به ترتیب دوری با فاصله ی 11 تایی از هم قرار دهیم و فواصل
را با رنگ سفید پر کنیم در شرط مساله صدق می کند ( البته 6000 بر 11 بخش پذیر نیست و باقیمانده ی 5 می دهد پس 5 تا از فاصله ها
را که به اندازه ی کافی از هم فاصله دارند با 11 رنگ سفید پرکنید ) و k برای آن برابر 89 است.

فکر می کنم 89 جواب مساله باشد ( حداقل یک کران پایین برای آن هست)

 

[S.H1997]

پاسخ : ترکیبیات مرحله دویی

برای 90 پیدا کردم:ببینید درسته یا نه؟
یکی از رنگهاروازش1دونه رنگمیکنیم و بعد اینو هرکدومو11تا رنگ میکنیم و...

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

سوال سوم)در یک جمع 2000 نفره،هر فرد به 1000 فرد دیگر گل میدهد.دو نفر که به یکدیگر گل داده باشند با هم دوست میشوند.حداقل چند زوج با یکدیگر دوست میشوند؟(تورنمنت شهر ها-2009)

 

[S.H1997]

پاسخ : ترکیبیات مرحله دویی

سوال سوم)در یک جمع 2000 نفره،هر فرد به 1000 فرد دیگر گل میدهد.دو نفر که به یکدیگر گل داده باشند با هم دوست میشوند.حداقل چند زوج با یکدیگر دوست میشوند؟(تورنمنت شهر ها-2009)

اخه فعلا اثبات نشد که 90 درسته.

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

اخه فعلا اثبات نشد که 90 درسته.

عیب نداره!!بذار تند تند سوال حل کنیم،این وسطا سوالی چیزی جا موند اشکال نداره...باید زود برسیم مرحله دو..بعدش دوباره برگردیم رو سوالایی که قبلا حل نشدن.:166:

 

[inaderi]

پاسخ : ترکیبیات مرحله دویی

ایول چه سوالای خوبی
از کجا اینارو گیرمیارید؟
برای سوال 3 یه ایده ای دارم ببینین درسته؟
خب می گیم افراد رو روی یه دایره می نشونیم
و اسماشونو 1 و2 و 3 و ... 2000 میزاریم
حالا باشروع از نفر شماره یک هرکس درجهت ساعت گرد به هزارنفر بعدیش گل میده
وخب اینطوری 1000 زوج دوستی بوجودمیاد


[HR][/HR]

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

راه حل inaderi رو میتونیم اینطوری بگیم(500500 زوج دوستی بوجود میاد):یه جدول 2000 در 2000 میکشیم.در هر کدوم از ستون ها 1000 خانه را علامت میزنیم.(علامت ها بیانگر گل دادن فرد i ام به دیگری است.) مثلا ستون 1، از 2 گل داده تا 1001.(به خودش نمیتونه گل بده)برای اینکه مینیمم ایجاد بشه،ستون 2 نباید به 1 گل بده.به خودش هم که نمیتونه بده،پس تا 1002 گل میده.همینطوری ادامه میدیم تا برسیم به ستون 1000.این ستون از سطر 1001 گل میده تا سطر 2000.وقتی نوبت به ستون 1001 میرسه،این ستون از سطر 1002 گل میده تا سطر 2000، ولی یه گل دیگه هم باید بده،پس به یکی از سطر هایی که بالاتر از سطر 1001 هستن میتونه گل بده،پس تا الان یه دوستی ایجاد شد.به ترتیب مشابه برای ستون 1002، 2 دوستی ایجاد میشه.یعنی برای ستون 2000،هزار دوستی ایجاد میشه.حالا اگر مجموع این دوستی ها رو پیدا کنیم،میشه 1+2+...+1000.درسته؟ که میشه 500500 جفت دوستی


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

سوال چهارم) زیاد مرحله دویی نیست،پایین تره
از مجموعه

دو دسته هر یک شامل 16 عدد انتخاب کرده ایم.در دسته اول همه ی اعداد زوج و در دسته دوم همه اعداد فرد هستند که مجموع اعداد این دسته ها با هم برابراند.ثابت کنید دو عدد وجود دارد که مجموع آنها برابر 65 است(تورنمنت شهر ها-2007)

 

[inaderi]

پاسخ : ترکیبیات مرحله دویی

من نمی فهمم مگه سوال نگفته حداقل تعداد دوستی هارو بجوریم؟
پس این عدد 500500 برا چیه؟
من برا اثبات اینکه هزار کمینه است می گم:
گراف جهتدار ادمارو درنظر بگیر
هر راس درجه ی خروجی اش هزاره
تعداد یال ها میشه
2000*1000(هر یک از 2000 نفر به 1000 نفر گل داده)
خب حالا تعداد کل یال های گراف بدون جهت(گراف زمینه یا دوگان) رو می شمریم
که میشه
2/(1999*2000)
خب حالا تعداد یال های موازی رو می شمریم که میشه حداقل(طبق لانه)
1000=2/(1999*2000)-2000*1000
پس دست کم 1000 تا یال موازی یا دوستی وجود داره

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

سوال 4
خب اعداد رو به 32 دسته تقسیم ی کنیم در دسته ی i ام اعداد i و شصت و پنج منهای i رو می زاریم

خب از هر دسته حداکثر یه عدد انتخاب میشه و چون جمعا 32 عدد انتخاب میشه پس از هر دسته دقیقا یه عدد انتخاب میشه

خب حالا فرض می کنیم مجموع اعداد دستهی فرد ها $ باشه اونوخت مجموع اعداد دستهی زوج هارو حساب می کنیم

مجموع تمام اعداد زوج میشه 33*32

هر عددی از دسته ی فرد ها رو که انتخاب کنیم هم دسته اش از زوج ها انتخاب نمیشه

پس مجموع اعداد زوج میشه

$=($ -65*16 )- 32*33

که بدیهتا غلطه و تناقض

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

من نمی فهمم مگه سوال نگفته حداقل تعداد دوستی هارو بجوریم؟
پس این عدد 500500 برا چیه؟

شما گفتین این 2000 نفر رو دور میز میشونین.خب،نفر اول به بغلیش گل میده تا نفر 1001 ام،درست؟حالا،نفر بعدی گل میده تا نفر 1002 ام.(شما میز گذاشتی،منتها من جدول کشیدم،که از میز یا جدول به جواب یکسانی میرسیم)حالا،نفر 1000 ام گل میده به نفر 1001 ام تا 2000 ام.عنی از نفر اول تا نفر 1000ام هیچ دوستی ایجاد نمیشه.اما نفر بعدیش،یعنی نفر 1001 ام گل میده به نفر 1002 ام تا نفر 2000ام.تا اینجا این آدم 999 گل داده.خب،گل آخر رو باید به نفر اول بده،چون نفر اول پیش نفر 2000 ام نشسته.چون توی اولین خط گفتیم که نفر اول به آخرین نفری که گل داد،نفر 1001 ام بود،پس نتیجه میگیرم الان این دو تا دوست شدن.چون دو تایی شون به هم گل دادن.حالا نفر 1002 ام،گل میده به نفر 1003 ام تا 2000.تا الان این 998 تا گل داده.پس دو تا دیگه باید بده،که میده به نفر اول و دوم.چون نفر اول به این گل نداده ولی نفر دوم گل داده،پس این دو تا دوست میشن،همینطوری اگه ادامه بدیم،برای هر نفر از نفر 1000ام تا نفر 2000ام 1 دوستی ایجاد میشه که کلا میشه 1000 دوستی ،پس راه من غلطه! با جدول هم دقیقا مثل این در میاد،باید میگفتم ستون 1002ام،از سطر 1003ام تا آخر سطر 200 پر میکنه،دو تای باقی رو،یکی میذاره تو سطر 1،اون یکی رو تو سطر 2 یا هرچی قبل از سطر 1002.چون باید مینیمم در بیاد.همینطوری ادامه بدیم،از ستون 1001 به بعد دوستی ایجاد میشه که چون تو هر ستون یه دوستی،پس کلا 100 دوستی ایجاد میشه.من آخرشو اشتباه کردم:153:

 

[inaderi]

پاسخ : ترکیبیات مرحله دویی

جواب سوال 4 درسته؟
سوال سه من نشون می دوم که k بزرگ تر مساوی نود می شه
مثالم هم ای طوریه:
روی دایره 11 تا یک میزتریم بعدش 11 تا دو بعدش 11 تا 3 و... 11 تا 10 و بعدش دوباره 11 تا 1 و...

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

آره سوال 4 برهان خلفه دیگه.سوال سه رو چطور در آوردین؟



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

جواب سوال 4 درسته؟
سوال سه من نشون می دوم که k بزرگ تر مساوی نود می شه
مثالم هم ای طوریه:
روی دایره 11 تا یک میزتریم بعدش 11 تا دو بعدش 11 تا 3 و... 11 تا 10 و بعدش دوباره 11 تا 1 و...

ببخشید،من متوجه نشدم

 

[inaderi]

پاسخ : ترکیبیات مرحله دویی

حالا جواب سوال 3 رو بزارین

 

[nima1376]

پاسخ : ترکیبیات مرحله دویی

لطفا سوالای جزوه های آقای علیپور رو قرار ندید.(حداقل نه این قد ضایع!)
شاید نخوان زحماتشون هدر بره و راضی نباشن!

 

[inaderi]

پاسخ : ترکیبیات مرحله دویی

چرا هدرمیره؟
بعد مگه نمی بینی جلو سوالا منبعشو نوشته؟
اگه هم این طور باشه ایشون (آقای علی پور) برای حل کردن واستفاده این مطالبو جمع کردن

 

[n_maths]

پاسخ : ترکیبیات مرحله دویی

لطفا سوالای جزوه های آقای علیپور رو قرار ندید.(حداقل نه این قد ضایع!)
شاید نخوان زحماتشون هدر بره و راضی نباشن!

ایشون راست میگن.من نباید بدون اجازه دکتر علیپور سوالاشون رو پخش میکردم.خیلیا بخاطر همین سوالا میرن کلاس.

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

چرا هدرمیره؟
بعد مگه نمی بینی جلو سوالا منبعشو نوشته؟
اگه هم این طور باشه ایشون (آقای علی پور) برای حل کردن واستفاده این مطالبو جمع کردن

شما برید تو mathlink چقدر این سوالا اونجا هست؟