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

[کاربر حذف شده 8031]

تو این تاپیک قراره که سوالای ترکیبیات در سطح مرحله دوّم بررسی بشن.لزومی نداره که حتماً برای مرحله دوّم های قبل باشن. منظور سطح سوالا هست . پس اگه یه وخ احساس کردید که سوال هندسه ای تقریبا مرحله اولی دارید نباید اینجا مطرح بشه باید تو تاپیک های دیگه مطرح بشن.
ضمناًقابل توجه هست که باید از این بعد تو این سری تاپیک های جدید بغل هر سوالی که مطرح میکنید شماره ی مربوط به اون رو بنویسید تا دیگه سوالا گم نشن و...![nb]یعنی اولین سوال این تاپیک شمارش میشه یک و به همون طور بقیه سوالا.[/nb]
پس از این به بعد سر هر سوالی که بحث میشه لطف کنید که شماره ی سوال مورد نظرتون رو هم ذکر کنید.

 

[Dark Eagle]

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

1)
قیچی شطرنجی ماشینیس که یک صفحه ی شطرنجی را فقط از روی خطوط جدول برش میدهد و مقدار کل برش را در حافظه قرار میدهد
یک صفحه شطرنجی 7*8 داریم با قیچی شطرنجی آن را به تعدادی قطعه تقسیم میکنیمبه طوری که اندازه هر قطعه حد اکثر 5 باشد و طول برش کمینه باشد.
کم ترین طول برش را بیابید .

 

[S.M.P]

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

2)
-به چند طریق می توان رئوس یک 12 ضلعی منتظم را با دو رنگ، رنگ آمیزی کرد بطوریکه هیچ دو چند ضلعی منتظمی درون آن با رئوس همرنگ ایجاد نشود؟

 

[S.M.P]

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

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

 

[S.M.P]

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

4)
- فرض کنیدهر مربع از یک صفحه ی شطرنجی 5*16 با یکی از 3 رنگ a و b و c رنگ آمیزی شده باشد. ثابت کنید که یک مستطیل وجود دارد که
چهار مربع واحد گوشه های آن همرنگ اند.

 

[S.M.P]

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

4) راهنمایی:
از آنجایی که تمام خانه های این جدول برابر با 80 می باشد و با توجه به اینکه با سه رنگ رنگ آمیز ی شده پس حداقل 80/3 = 27 خانه به یک رنگ می باشند. حال با توجه به تعداد روش های قرار گرفتن خانه های یکرنگ می توان اثبات کرد که یک مستطیل رنگی وجود دارد.

 

[most wanted]

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

​

 

[erfan_ashorian]

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

در صفحه 4n/3 تا مستطیل داریم که اضلاعش موازی محور هاست هر مستطیل حداقل n تا مستطیل دیگه رو قطع میکنه ثابت کنید مستطیلی هست که همه ی مستطیل های دیگه رو قطع میکنه ..

 

[مهدی]

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

راه حلی که پایین اشاره شد درست هستش و نیازی به این نیست

 

[erfan_ashorian]

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

استدلالت غلطه و صرفا لانه کبوتری گفتنت درسته...

 

[y.a]

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

در صفحه 4n/3 تا مستطیل داریم که اضلاعش موازی محور هاست هر مستطیل حداقل n تا مستطیل دیگه رو قطع میکنه ثابت کنید مستطیلی هست که همه ی مستطیل های دیگه رو قطع میکنه ..

راهنمايي 1: مستطيل ها رو روي محور هاي مختصات تصوير كنيد و اون‌ها رو به صورت بازه روي دو محور در نظر بگيريد.

راهنمايي2: از اين سوال و لانه كبوتري كمك بگيريد: 2n+1 بازه داريم كه هر بازه با حداقل n بازه‌ي ديگر اشتراك داره. ثابت كنيد بازه‌اي وجود داره كه با 2n بازه‌ي ديگر اشتراك داشته باشه...

 

[y.a]

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

۸-متناهی مهره روی یک نوار نامتناهی از مربع‌ها قرار داده شده. در هر حرکت می‌توان خانه‌ای که بیش از یک مهره دارد انتخاب کرد و ۲ مهره از آن را برداشت و ۱ مهره در خانه سمت راست و ۱مهره در خانه سمت چپ قرار داد. یک وضعیت آغازی داده شده. نشان دهید هر دنباله ای از حرکات پس از تعداد ثابتی حرکت و در یک وضعیت نهایی ثابت متوقف می‌شود.

نکته: سوال معروفه، اما اگه قبلا ندیدیدش حتما روش فکر کنید، چون ایده‌ی جالب و مهمی داره.
اگه تا آخر هفته کسی حل نذاشت راهنمایی میذارم.

 

[Fliqpy]

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

مهره ها رو با 1 تا n شماره گذاری میکنیم.
َai رو برابر مربعی که مهره i ام توشه قرار میدیم(یه مربع رو برابر صفر قرار میدیم و از اون استفاده میکنیم. ai ها میتونن منفی هم باشن)
حالا عبارت زیر رو در نظر میگیریم.

http://latex.codecogs.com/gif.latex?%5Csum_%7B1%5Cleq%20i%3Cj%5Cleq%20n%7D%20%7Ca_%7Bi%7D-a_%7Bj%7D%7C


این کمیت در هر مرحله دقیقاً دوتا کم میشه (برای اونایی که جابجا شدن 2 تا تغییر میکنه، برای بقیه اعضا با یکی از اینا 1 دونه زیاد 1 دونه کم میشه، برای بقیه اعضا با خودشون ثابت میمونه) ولی هیچ وقت منفی نمیشه پس بعد از یه مدت متوقف میشیم.

 

[y.a]

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

اشتباه کردید ، مثلا در نظر بگیرید که تو خونه شماره ۱ سه تا مهره و تو خونه‌ی شماره ۳ یک مهره داشته باشیم. حالا این عمل رو روی خونه شماره ۱ انجام بدید ۴ واحد زیاد میشه

شما توی محاسبتون به این موضوع دقت نکردی که تفاضل مهره‌های جابه‌جا شده خونه‌ی iام با مهره‌های همون خونه رو در نظر بگیری.

 

[ehsan-mokhtarian]

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

مهره ها رو با 1 تا n شماره گذاری میکنیم.
َai رو برابر مربعی که مهره i ام توشه قرار میدیم(یه مربع رو برابر صفر قرار میدیم و از اون استفاده میکنیم. ai ها میتونن منفی هم باشن)
حالا عبارت زیر رو در نظر میگیریم.

http://latex.codecogs.com/gif.latex?%5Csum_%7B1%5Cleq%20i%3Cj%5Cleq%20n%7D%20%7Ca_%7Bi%7D-a_%7Bj%7D%7C


این کمیت در هر مرحله دقیقاً دوتا کم میشه (برای اونایی که جابجا شدن 2 تا تغییر میکنه، برای بقیه اعضا با یکی از اینا 1 دونه زیاد 1 دونه کم میشه، برای بقیه اعضا با خودشون ثابت میمونه) ولی هیچ وقت منفی نمیشه پس بعد از یه مدت متوقف میشیم.

جوب زدی هر دفعه یه تعداد نامعین زیاد می شه می شه این متغیرتون ...
چند تا راه حل داره
اول باید اثبات کنیم که بعد از متناهی حرکت متوقف می شه ( مثلا یه راهش اینه که با برهان خلف راست ترین و چب ترین خونه داره همین جوری راست تر و چپ تر می ره (البته با استقرا برای حکم اصلی) ولی اگه به ازای یک حرکت که روی یک خونه می زنیم یک خط روی اون خونه بکشیم و در مرحله ی بعدی اگه یک حرکت روی یکی از خونه ی سمت راستش که با اون حداقل 2 خانه فصله داره انجام بدیم روی اون خط می کشیم و ... (اگه انجام ندیم کلا با استقرا مسئله حل می شه) و می شه اثبات کرد که بین خط های متوالی حتما مهره وجود داره ...)
تیکه ی دوم یعنی یکتاییش راحت تره اگه 2 تا دنباله داشته باشیم می شه ترتیب حرکاتش رو عوض کرد ( روی هر خانه تعداد مهره ی آن را می نویسیم و این عدد رو فرض می کنیم منفی هم بشه) حالا می شه به راحتی طول دنباله ها رو کم کرد و مثلا با استقرا حلش کرد ...
دقیق ننوشتم ولی ...

 

[moreda]

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

یه راه اینه:
1-اثبات کنید که نامتناهی راست نمیشه رفت:
فرض خلف کنید پس دنباله از حرکات وجود دارد که در هر خانه راست تر از خانه قبل است.
حال ثابت کنید سمت چپ هر عضو این دنباله همیشه حداقل یک مهره باقی می ماند پس سمت چپ عضو n+1 باید n+1 خانه بماند
حال برای اثبات این گذاره هم به هر خانه یک مهره نسبت دهید.
اگر خانه ای انتخاب شد که 1 مهره اش منسوب شده بود آن مهره که چپ می رود مهره منسوب جدید میشود
اگر خانه ای انتخاب شد که حداقل2 مهره اش منسوب شده بود آن مهره که که چپ می رود آن مهره با خانه چپ تر وآن مهره که زاست می رود خانه راست تر
2-اثبات کنید متناهی راست و متناهی چپ برود متوقف می شود.
اگه نشود 2بار یک وضعیت تکرار میشود حال فرض خلف
اما راسترین مهره را که در مرحله ای جابجا می شود را در نظر بگیرد تناقض است.
پس در متناهی مرحله تمام میشود
حال گرافی بسازید دو وضعیت را به هم وصل کنید(جهت دار) اگر با یک حرکت از یکی به دیگری رفت
حال اگه چند وضعیت مختلف پایانی داشته باشیم طولانی ترین مسیر را بگیرید بین وضعیت اولیه و وضعیت هایی که حداقل دو وضعیت پایانی را نتیجه می دهند.حال مثلا A آن وضعیت است
(N<-...<-C<-A->B->...->M)
A-b->B
,A-c->C
اگر با انتخاب خانه b,c این اعمال انجام شود
حال A-b-c->D
,A-c-b->D پس
B->D
C->D
حال از D حداقل به یک وضیعیت پیایانی میرسیم مثل P که حداقل P=/=M یا P=/=N
حال پس B یا C به حداقل دو وضعیت متقاوت می رسند و مسیر طولانی تری دارند تناقض


دیگه دسم خسته شد.


این هم برای کسانی که می خواهند قویتر کار کنند.
chip-firing game
سوال به عنوان لم در این مبحث است

 

[moreda]

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

راه 7:بعضی وقت ها باید یک شی پیدا کنید که خاصیت های A,B,C,... را داشته باشد معمولا باید همه اشیا با خاصیت A را بگیرید بعد از بینشان همه اشیا با خاصیت B و ...
اینجا هم دنبال مستطیلی هستیم که بقیه مستطیل ها هم در افقی هم در عمودی با همه اشتراک داشته باشد
حال بیش از نصف هر خاصیت را دارند پس یکی هست که هر دو خاصیت را دارد.

 

[Fliqpy]

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

9- فرض کنید p عددی طبیعی بین 0 و 1 باشد.همچنین Ai ها و Bi ها (i بین 1 و n)زیرمجموعه هایی از مجموعه اعداد طبیعی هستند بطوری که

و به ازای هر i و j متمایز بین 1 و n

ثابت کنید

 

[ehsan-mokhtarian]

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

ببخشید که تو صف سوال نیستم،ولی جواب این سوالو فوری میخوام
فرض کنید A مجموعه ای 13 عضوی از اعداد حقیقی باشد.نشان دهید دو عدد X , Y از A وجود دارند که

هر عضو رو به صورت tan یه زاویه نشون می دیم و عبارت گفته شده رابطه ی tan(x-y) می شه ...

 

[Phanntom]

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

دوتا سوال نسبتا زیبا دی

برای کدام اعداد طبیعی n یک تبدیل (X1,X2,...,XN) از اعداد 1تا n وجود دارد که تمام |XK - K| ها مختلف باشند؟

ثابت کنید اسب بازی شطرنج را روی صفحه ی شطرنجی 201*201 میتوان طوری حرکت داد که
ر همه ی خانه ها و در ضمن در هر کدام یک بار قرار بگیرد.
N_MATHS:
2-sqrt(3)= tan (π/12)
ما هم 13 تا عدد داریم