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

[fitmal]

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

واسه سوال دومیه میشه کلا نشون داد ک برای همه 4k+1 ها میشه این کارو انجام داد برای 5 نشون میدیم بعد برای 9*9 میشه طوری پرکرد ک ب حالت 5*5 برسیم ب همین شکل برای 13*13 میشه برسیم ب 9*9 و...

 

[Roomina.z]

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

سوال اولی(البته مطمئن نیستم)
حاصل جمع xi-i ها بدون قدر مطلق،از اونجا که از هر یک از اعداد 1 تا n دقیقا یکی + و یکی- داریم،0 میشه:
sum(Xi, i = 1 .. n)-i = 0
حالا اگه با قدر مطلق جمع کنیم،از اونجا که هیچ کدومشون مث هم نیستن و حداکثر n-1 و حداقل 0 هستن،هر کدومشون دقیقل برابر میشه با یکی از اعداد 0 تا n-1 و مجموعشون میشه:
2/(sum(abs(xi-i), i = 1 .. n) = n(n-1
حالا اگه دو طرف این دوتا تساوی رو با هم جمع کنیم داریم:
(sum(xi-i, i = 1 .. n)+abs(xi-i) = (1/2)*n(n-1
هر کدوم از (xi-i|+(xi-i| ها یا 0 میشن یا 2*(xi-i)
پس 2/(n(n-1 باید 2 رو بشماره.پس (n(n-1 باید 4 رو بشماره.یعنی n یا باید بر 4 بخشپذیر باشه یا مضربی از 4 بعلاوه 1 باشه.:-D
درسته؟؟؟؟

 

[erfan_ashorian]

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

یه جدول n*n داریم که اولش همه خونه ها سفیدن جز یه خونه که توش یه رخ گذاشتیم و سیاس دو نفر با هم این طوری بازی میکنن که هر دفعه هر نفر میتونه قلعه رو ببره به یه خونه سفید و اون خونه جدیده این دفعه سیاه میشه کی استراتژی برد داره؟

 

[عمو ژپتو]

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

سلام بچه ها شما عایا این مسئله رو دیدید ؟
یه مجوعه x داریم که m تا عضو داره و x1,x2....xn زیر مجموعه هایی از x هستند . به طوریکه هر دوتا از این زیر مجموعه ها حداکثر 1عضو مشترک دارن.... و هرکدوم از اعضای x حداقل در kتا از این زیر مجموعه ها وجود دارند ... ثابت کنید حداقل k تا از این زیر مجموعه ها هم اندازه هستند.

 

[bealefshin]

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

یه سوال خوب چندوقت پیش دیدم به نظرم خوبه که اینجا بگم شما هم روش فکر کنین و اگه راه حلی دارید بگین:

2n-1 نقطه روی محیط یک دایره داده شده اند. حداقل مقدار k را بیابیر به طوری که به ازای هر زیر مجموعه k عضوی از نقاط دو نقطه عضو آن زیرمجموعه وجود داشته باشند که روی یکی از دو کمان بین آن دو نقطه دقیقا n نقطه وجود داشته باشد..!

 

[Anita H]

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

یه سوال خوب چندوقت پیش دیدم به نظرم خوبه که اینجا بگم شما هم روش فکر کنین و اگه راه حلی دارید بگین:

2n-1 نقطه روی محیط یک دایره داده شده اند. حداقل مقدار k را بیابیر به طوری که به ازای هر زیر مجموعه k عضوی از نقاط دو نقطه عضو آن زیرمجموعه وجود داشته باشند که روی یکی از دو کمان بین آن دو نقطه دقیقا n نقطه وجود داشته باشد..!

اول یه لم میدیم میگیم اگه n تا نقطه دور دایره باشن، حداکثر [n/2] تا نقطه از اون نقاط میتونیم انتخاب کنیم به طوری که هیچ کدومشون مجاور نباشن. (با لانه کبوتری هم اثبات میشه!)
یه گراف میسازیم این طوری که به ازای هر نقطه دور دایره، یه راس در نظر میگیریم و نقطه ی iام رو به n+1 امین نقطه ی جلوییش وصل میکنیم(یال میکشیم/ واضحه اگه بین دو تا راس یال باشه، یعنی بین اون دو تا توی دایره n تا نقطه هست!)
حالا ما باید مینیموم مقدار k رو پیدا کنیم که بشه از این گرافه k تا راس انتخاب کرد به طوری که هیچ دو تایی مجاور نباشن.
درجه ی هر راس ۲ئه پس گرافمون یه تعدادی دور هست (بدیهیه ولی لازم به ذکره که تعداد نقاط روی هر دو تا کمان واصل دو نقطه، نمیتونه برابر n باشه!)
حالا میخایم تعداد دورها رو بشمریم! یه خورده نظریه اعداد!)

اثبات میشه که مقدار این ب.م.م ها مساوی تعداد دورهای گرافمونه! (آسونه اثباتش نمینویسم )
حالا دو حالت داریم. این مقداری که بالا نوشتم(ب.م.م) یا برابر ۱ هست یا برابر ۳
اگه برابر 1 باشه با استفاده از اون لم بالاییه میگیم k = n.
اگر هم مقدار اون ب.م.م برابر ۳ باشه، نتیجه میگیریم که گرافمون به ۳ تا دور تقسیم میشه(تو این حالت باقیمانده ی n به ۳ برابر ۲ هست و ۲n-۱ به ۳ بخش پذیره).
هر دور 3 / (2n-1) تا راس داره. این مقدار رو برابر s بگیرید. به ازای این حالت طبق اون لمی که اون اول گفتم، k = 3 * [s/2] + 1 خواهد بود.

 

[javadss]

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

سوال جالبیه این
:
اعداد 1 تا 1000 را با ترتیبی دلخواه روی دایره ای چیده ایم.ثابت کنید می توان 500 پاره خط غیر متقاطع رسم کرد به طوریکه هر یک از آنها دوتا از این عدد هارا به هم وصل کند که تفاضل اعداد دو سر هر پاره خط از 749 بیشتر نباشد

 

[rozhina.sh]

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

سوال جالبیه این
:
اعداد 1 تا 1000 را با ترتیبی دلخواه روی دایره ای چیده ایم.ثابت کنید می توان 500 پاره خط غیر متقاطع رسم کرد به طوریکه هر یک از آنها دوتا از این عدد هارا به هم وصل کند که تفاضل اعداد دو سر هر پاره خط از 749 بیشتر نباشد

اعداد 1 تا 250 رو قرمز میکنیم و 251 تا 750(که اختلاف هیچ نقطه قرمز و ابی بیش از 749 نشه) آبی میکنیم و از 750 تا 1000 رو هم قرمز میکنیم
الان 500 تا قرمز و 500 تا ابی داریم که میخوایم 2 به 2 ابی و قرمز هارو به هم متصل کنیم با استقرا ثابت میکنیم که اگر 2n نقطه داشته باشیم n تا قرمز n تا ابی(با هر چیدمانی) میتونیم جوری بهم 2 نقطه های ابی و قرمز رو وصل کنیم که تقاطعی نداشته باشند
پایه:برای 2 نقطه (n=1) که بدیهیه
خوب برای n-1 فرض میکنیم درسته برای n ثابت میکنیم که یعنی 2 نقطه ابی و قرمز اضافه میشه خوب پس یه نقطه قرمز و ابی اضافه میکنیم و بدیهیه که در این ساختار حتما حداقل 1 جفت نقطه ابی و قرمز کنار هم هستند
که اون هارو به هم وصل میکنیم و خوب خطی نیست که بخواد با این خط متقاطع باشه و میدونیم که اون 2n تا رو هم میتونیم به هم به طور غیر متقاطع طبق فرض استقرا وصل کنیم پس ثابت میشه

 

[rozhina.sh]

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

3)
-یک شبکه m*n و سه رنگ داده شده است. می خواهیم هر ضلع از شبکه را با یکی از سه رنگ چنان رنگ آمیزی کنیم که هر مربع کوچک دو ضلع از یک رنگ و دو ضلع از رنگ دیگر داشته باشد. به چند طریق این کار ممکن است؟

با اینکه در سطح م2 نبود ولی خوب
اول خونه اول مثلا بالا سمت چپ برای رنگ امیزیش انتخاب 2 از 3 هست برای رنگها و برای چیدمان رنگها 6 تا حالته پس 18 تا میشه و خونه ای که در همون سطر جلوشه رنگ 1ضلعش که با خونه اول اشتراک داره مشخصه پس 2 حالت برای انتخاب رنگ و 3 حالت برای چیدمان هست که میشه 6 و این تا اخر سطر و ستونی که خونه بالا چپ توشه 6 حالت داره اما خونه ای که 2 تا از اضلاعش توسط رنگهای قبلی معلومه 2 حالت داره که اگر 2 ضلعش از 2 رنگ متفاوت بودن 2 حالت چیدمان داره و 1 حالت انتخاب رنگ ولی اگر از یک رنگ لودن 2 حالت انتخاب رنگ داره و 1 حالت چیدمان که در هر دو حالت برابر 2 عه که تعداد این خونه ها هم برابر (n-1)(m-1)
18* m+n-2^6* (m-1)(n-1)^2