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

[سیاوش]

پاسخ : استقرا

اگر m و n عدد هایی طبیعی باشند ثابت کنید:
2 به توان m+n-2 بزرگتر مساوی m * n است.
B-)

روی n استقرا میزنیم
ابتدا فرض کینم n=1 باشه حکم تبدیل به این میشه :

این حکمو 2باره با استقرا ثابت میکنیم که اثباتش خیلی آسونه نیازی به نوشتن نیست .

الان پایه استقرا اثبات شد .
فرض کینم حکم به ازای n=k برقرار باشه داریم :

درنتیجه داریم

از این 2تا حکمو نتیجه میگیریم یعنی

B-)

 

[Dark Eagle]

پاسخ : استقرا

با استقرا ثابت کنید اگر هر مجموعه از گراف G با k راس داری مجموعه ی مستقلی با سقف (k/2) راس باشد, گراف G دو بخشی است ... :-s

baaaaaaaaaale​

استقبالم چیز خوبیه ....

به چند طریق می توان اعداد 1 تا n را پشت سر هم نوشت که عدد i ام (n >= i >= 1) از همه ی اعداد قبل از خود (عدد 1 ام تا i ام) بزرگتر و

یا از همه ی آن ها کوچکتر باشد ؟

به عنوان مثال دنباله ی زیر شرایط مسئله را داراست .... (n==5)

3,2,4,1,5

 

[سیاوش]

پاسخ : استقرا

با استقرا ثابت کنید اگر هر مجموعه از گراف G با k راس داری مجموعه ی مستقلی با سقف (k/2) راس باشد, گراف G دو بخشی است ... :-s

baaaaaaaaaale​

استقبالم چیز خوبیه ....

به چند طریق می توان اعداد 1 تا n را پشت سر هم نوشت که عدد i ام (n >= i >= 1) از همه ی اعداد قبل از خود (عدد 1 ام تا i ام) بزرگتر و

یا از همه ی آن ها کوچکتر باشد ؟

به عنوان مثال دنباله ی زیر شرایط مسئله را داراست .... (n==5)

3,2,4,1,5

من ریاضی بودم زیاد گراف بلد نیستم ولی فکر کنم سوال اول توی وست بود .

اما واسه سوال دوم

با استقرا ثابت میکنیم که تعداد حالات میشه 2 به توان n-1 و تنها یک حالت وجود داره که عدد n اولین عدد دنباله باشه که به طور نزولی مرتب بشن .. ( اینو جدا هم میشه ثابت کرد )

برای حالت n=1 و n=2 حکم واضحه .

فرض استقرا تعداد حالات برای n=k برابر

باشد .و تنها یک حالت وجود داره که عدد k اولین عدد دنباله باشه که به طور نزولی مرتب بشن .
حالا حکمو برای n=k+1 ثابت میکنیم .

حالت قبلو در نظر میگیریم در سمت راست همشون k+1 رو مینویسیم تا

حالت جدید ساخته بشه .

پس دنباله ی

ساخته میشه .

برای ساختن

دیگه باز هم همون

حالت فرض استقرا رو در نظر میگیریم و به جای k عددk+1 رو میزاریم تا اینجا مشکلی نیست بعد عدد k رو سمت چپ این

حالت مینویسیم تا

تا حالت جدید ساخته بشه .

اما دنباله ی

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

ساخته میشه که قبلا شمردیمش و تکراریه .

اما دنباله ی

را هنوز نشمردیم
پس

و تنها یک دنباله با k+1 آغاز شد . و به طور نزولی مرتب شدن
حکم استقرا ثابت شد .

 

[F@temeh]

پاسخ : استقرا

اون تیکه ی آخر رو اشتباه نگفتید؟

اینجوری که درست در نمیاد. نباید عدد 1 رو بذاریم آخر ِ همه بعد به همه‌ی عدد قبلیاش 1 اضافه کنیم؟

× اول ِ اولش چجوری فهمیدین تعداد حالات دو به توان انِ منهای یک میشه؟

 

[سیاوش]

پاسخ : استقرا

آقا اصلا اون اثبات بالاییه داغون و گند و بیخوده نخونیدش
اثبات درست به کمک فاطمه

میشه اول این حکمو ثابت کرد که آخرین عدد دنباله یا 1 هست یا n
برهان خلف فرض کنیم حالتی غیر از این وجود داشته باشه یعنی آخرین عدد دنباله عددی هست مثله x و هر 2 عدد 1 و n در سمت چپ ایکس هستن که از یکی بزرگتر و از یکی کوچکتر هست تناقض .
بعد بیایم استقرا بزنیم برای ساختن

اول k+1 را به سمت راست همه ی فرض استقرا اضافه کرد .

برای ساختن

دوم از روشی که فاطمه خانوم گفت استفاده کرد یعنی به همه عدد 1 را اضافه کرد و یک رو آخرین عدد دنباله نوشت .

الان همه ی حالات رو شمردیم و ثابت کردیم حالت دیگه ای وجود نداره .

× اول ِ اولش چجوری فهمیدین تعداد حالات دو به توان انِ منهای یک میشه؟

با حدس و آزمایش

 

[Dark Eagle]

پاسخ : استقرا

بهترم میشد گفت ... البته خیلی بهتر ...

آخرین عضو جایگشت رو در نظر بگیرید ... طبق خواسته س سوال این عضو یا از همه بزرگتره یا کوچکتر .... پس یا 1 اِه یا n ...

پس از مشخص شدن عضو n-ام بقیه رو اگه اون عضو n نبود منهای 1 می کنیم .... در هر دو صورت n یا 1 تعداد بقیه حالات برابر 2 به توان n-2 اِه.

جمع این 2 تا میشه 2 به توان n-1 ....

 

[Dark Eagle]

پاسخ : استقرا

می خواهیم n عدد را مرتب کنیم ... برای این کار می توانیم در هر مرحله تعدادی از ای اعداد را به دلخواه انتخاب کنیم ...

و با همان ترتیب به انتها ببریم .... ثابت کنید می توان با سقف لاگ n مرحله اعداد را مرتب نمود ....

داری عصبیم میکنی

 

[مهدی]

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

1-یک جدول 2000*2002 داریم. در ابتدا بیش از 1999*2001خانه از خانه های آن به رنگ سفید و مابقی خانه ها به رنگ سیاه هستند.هر گاه3خانه از یک مربع2*2 از جدول به رنگ سیاه بودند،می‌توانیم خانه ی چهارم آن مربع را نیز سیاه رنگ کنیم.ثابت کنید هیچ‌گاه نمیتوان تمام خانه های جدول را سیاه کرد.

2-دنباله ی صعودی 1.3.4.9.10.12.13...شامل توان های مثبت عدد 3 و نیز حاصل جمع توان های متمایز عدد 3 می‌باشد.صدمین عضو این دنباله را بیابید .

3-مقداری پول را بین nنفر تقسیم کرده ایم .در هر مرحله دو نفر مانند aوb را پیدا می‌کنیم که aحداقل k+1 تومان بیشتر از bپول داشته باشد.سپس aرا مجبور می‌کنیم که kتومان به bبدهد.ثابت کنید این کار پایان پذیر است و در نهایت به جایی خواهیم رسید که اختلاف پول هیچ دو نفری بیش از k تومان نباشد .

4- 21 عدد متمایز از بین اعضای مجموعه ی {1,2,3,...,2046} انتخاب شده اند .نشان دهید میتوان سه عدد متمایز a,b,cاز بین آن 21 عدد انتخاب کرد به طوری که رابطه ی زیر برقرار باشد؛
bc<2a^2<4bc

5-دو نفر به ترتیب خانه های یک جدول 4*4 را رنگ آمیزی می‌کنند.برنده کسی است که برای اولین بار رنگ آمیزی ىه مربع 2*2 را کامل کند چه کسی میتواند برنده بازی باشد؟

 

[rezaezio]

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

راهنمایی واسه سوال یک و سه (درست بخوانید ) می‌نویسم !

1- محیط قسمتی که مشکیه، هیچ‌وقت زیاد نمیشه!
3- تعداد افرادی که مقدار پولشون i هست رو Ai بگیرید. حالا عدد X رو برابر با مجموع Ai* 2^i ها بگیرید. مقدار عدد X تو هر مرحله کم میشه!

 

[Phanntom]

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

چی شد؟
بازم سوال هستش

بعدا نوشت :
Damon
شما سوال می‌ذاری حل کنیم؟

انصافا سوال ۴ خیلی قشنگه
آسون هم هستش که