• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

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

  • شروع کننده موضوع کاربر حذف شده 8031
  • تاریخ شروع
  • شروع کننده موضوع
  • #1

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

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

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
657
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

S.M.P

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
18
نام مرکز سمپاد
Helli 2
شهر
تهران
مدال المپیاد
مرحله اول ریاضی و کامپیوتر
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

S.M.P

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
18
نام مرکز سمپاد
Helli 2
شهر
تهران
مدال المپیاد
مرحله اول ریاضی و کامپیوتر
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

S.M.P

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
18
نام مرکز سمپاد
Helli 2
شهر
تهران
مدال المپیاد
مرحله اول ریاضی و کامپیوتر
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

S.M.P

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
18
نام مرکز سمپاد
Helli 2
شهر
تهران
مدال المپیاد
مرحله اول ریاضی و کامپیوتر
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

most wanted

کاربر نیمه‌حرفه‌ای
ارسال‌ها
215
امتیاز
669
نام مرکز سمپاد
علامه حلی2
شهر
تهران
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

 

erfan_ashorian

کاربر حرفه‌ای
ارسال‌ها
397
امتیاز
1,243
نام مرکز سمپاد
2
شهر
تهران
دانشگاه
_ان شا الله قوزاباد
رشته دانشگاه
_علوم کامپیوتر(البته در این
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

erfan_ashorian

کاربر حرفه‌ای
ارسال‌ها
397
امتیاز
1,243
نام مرکز سمپاد
2
شهر
تهران
دانشگاه
_ان شا الله قوزاباد
رشته دانشگاه
_علوم کامپیوتر(البته در این
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

y.a

کاربر فوق‌فعال
ارسال‌ها
119
امتیاز
306
نام مرکز سمپاد
فرزانگان3/ فرزانگان۱
شهر
تهران
مدال المپیاد
طلای ریاضی سال ۹۲
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی کامپیوتر - نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

به نقل از PETERSON :
در صفحه 4n/3 تا مستطیل داریم که اضلاعش موازی محور هاست هر مستطیل حداقل n تا مستطیل دیگه رو قطع میکنه ثابت کنید مستطیلی هست که همه ی مستطیل های دیگه رو قطع میکنه ..
راهنمايي 1: مستطيل ها رو روي محور هاي مختصات تصوير كنيد و اون‌ها رو به صورت بازه روي دو محور در نظر بگيريد.

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

y.a

کاربر فوق‌فعال
ارسال‌ها
119
امتیاز
306
نام مرکز سمپاد
فرزانگان3/ فرزانگان۱
شهر
تهران
مدال المپیاد
طلای ریاضی سال ۹۲
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی کامپیوتر - نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

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

Fliqpy

کاربر نیمه‌حرفه‌ای
ارسال‌ها
181
امتیاز
303
نام مرکز سمپاد
غیر انتفاعی علامه حلی 3
شهر
تهران
مدال المپیاد
هر جوری حساب میکنم افتخار نمیکنم بهش
دانشگاه
شريف
رشته دانشگاه
نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

مهره ها رو با 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

کاربر فوق‌فعال
ارسال‌ها
119
امتیاز
306
نام مرکز سمپاد
فرزانگان3/ فرزانگان۱
شهر
تهران
مدال المپیاد
طلای ریاضی سال ۹۲
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی کامپیوتر - نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

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

ehsan-mokhtarian

کاربر فوق‌فعال
ارسال‌ها
104
امتیاز
361
نام مرکز سمپاد
علامه حلی 1
شهر
تهران
مدال المپیاد
نقره ریاضی 1391 طلا ریاضی 1392
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

به نقل از The Overlord :
مهره ها رو با 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 دونه کم میشه، برای بقیه اعضا با خودشون ثابت میمونه) ولی هیچ وقت منفی نمیشه پس بعد از یه مدت متوقف میشیم.
جوب زدی :D هر دفعه یه تعداد نامعین زیاد می شه می شه این متغیرتون ...
چند تا راه حل داره
اول باید اثبات کنیم که بعد از متناهی حرکت متوقف می شه ( مثلا یه راهش اینه که با برهان خلف راست ترین و چب ترین خونه داره همین جوری راست تر و چپ تر می ره (البته با استقرا برای حکم اصلی) ولی اگه به ازای یک حرکت که روی یک خونه می زنیم یک خط روی اون خونه بکشیم و در مرحله ی بعدی اگه یک حرکت روی یکی از خونه ی سمت راستش که با اون حداقل 2 خانه فصله داره انجام بدیم روی اون خط می کشیم و ... (اگه انجام ندیم کلا با استقرا مسئله حل می شه) و می شه اثبات کرد که بین خط های متوالی حتما مهره وجود داره ...)
تیکه ی دوم یعنی یکتاییش راحت تره اگه 2 تا دنباله داشته باشیم می شه ترتیب حرکاتش رو عوض کرد ( روی هر خانه تعداد مهره ی آن را می نویسیم و این عدد رو فرض می کنیم منفی هم بشه) حالا می شه به راحتی طول دنباله ها رو کم کرد و مثلا با استقرا حلش کرد ...
دقیق ننوشتم ولی ...
 

moreda

کاربر فوق‌فعال
ارسال‌ها
128
امتیاز
438
نام مرکز سمپاد
علامه حلی
شهر
تهران
مدال المپیاد
ریاضی
دانشگاه
شریف
رشته دانشگاه
کامپیوتر نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

یه راه اینه:
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

کاربر فوق‌فعال
ارسال‌ها
128
امتیاز
438
نام مرکز سمپاد
علامه حلی
شهر
تهران
مدال المپیاد
ریاضی
دانشگاه
شریف
رشته دانشگاه
کامپیوتر نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

Fliqpy

کاربر نیمه‌حرفه‌ای
ارسال‌ها
181
امتیاز
303
نام مرکز سمپاد
غیر انتفاعی علامه حلی 3
شهر
تهران
مدال المپیاد
هر جوری حساب میکنم افتخار نمیکنم بهش
دانشگاه
شريف
رشته دانشگاه
نرم افزار
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

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

ثابت کنید
gif.latex
 

ehsan-mokhtarian

کاربر فوق‌فعال
ارسال‌ها
104
امتیاز
361
نام مرکز سمپاد
علامه حلی 1
شهر
تهران
مدال المپیاد
نقره ریاضی 1391 طلا ریاضی 1392
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

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

Phanntom

کاربر فوق‌فعال
ارسال‌ها
115
امتیاز
364
نام مرکز سمپاد
helli
شهر
تهران
مدال المپیاد
سابقه دارم!
دانشگاه
light massage(پیام نور)
پاسخ : سوالات ترکیبیات هم سطح مرحله دوّم

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

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

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