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

[مهسا.ق]

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

بچه ها جم کنيد خودتونو ديگه. به هر دوتاتون تذکر دادم. اين قدر با هم جر و بحث نکنيد ديگه. لطفا صورت سوال ها رو کامل بذاريد بسه لطفا بحثه ديگه اي در اين مورد نکنيد!

ویرایش: پست های بی مورد و اضافی پاک شد! لطفا دیگه تکرار نکنید

 

[most wanted]

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

n سنگریزه در یک دسته داریم،دو نفر به روش زیر روی این سنگریزه ها بازی میکنند:

هر کس در نوبت خود تمام دسته های موجود با بیش از یک مهره رابه دو دسته ی ناتهی تقسیم می کند(دقت کنید لزومی ندارد تعداد مهره های دسته ها برابر باشند.)،کسی که آخرین حرکت را انجام دهد،برنده ی بازی است، "استراتژی برد این بازی با کدامیک است؟"

_________________________________________________________________________________________________________

دو نفر در یک جدول m*m بازی زیر را انجام می دهند:

هر کس در نوبت خود یک مهره اسب را وارد صفحه می کند،به طوری که مهره های قبلی را تهدید نکند،کسی که نتواند حرکتی انجام دهد بازنده است،برای چه m هایی نفر اول و چه m هایی نفر دوم برنده است؟!

 

[Dark Eagle]

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

n سنگریزه در یک دسته داریم،دو نفر به روش زیر روی این سنگریزه ها بازی میکنند:

هر کس در نوبت خود تمام دسته های موجود با بیش از یک مهره رابه دو دسته ی ناتهی تقسیم می کند،کسی که آخرین حرکت را انجام دهد،برنده ی بازی است، "استراتژی برد این بازی با کدامیک است؟"

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

 

[عمو ژپتو]

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

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

مخالفم به نظرم داری اشتباه میکنی اینی که تو میگی در حالتی دروست بود که میگفت فقط یک دسته رو دو قسمت کنه
ولی برای ای شک ندارم که به یه توان 2 ای ربط داره

 

[most wanted]

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

برایه n های فرد نفر 2 میبره برای زوج ها نفر اول..........

1.لطفا بزارین بقیه هم به سوال فک کنند،یکی بیاد زیره سوال جوابه چه فایده.
2.واسه راه حل شما: n=5 رو در نظر بگیر،نفر اول دو دسته ی 2 تایی و 3 تایی درست کنه نفر دوم مجبوره دسته های 1.1.1.2 تولید کنه که واضحه نفر اول می برد.
3.قسمت قرمز شده مهمه ها ازش نگزرید.

 

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

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

نیما جان اکثر پستات اسپمه!
اگه اینجوری ادامه بدی بَن میشی ها! چوب خطتت پر شده!مدیرای سایت کلافه شدن!
تو رو خدا بیخیال اسپم شو! هر چی میخوای با علیرضا صحبت کنی تو پ . خ! :)

 

[Dark Eagle]

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

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

 

[most wanted]

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

یک لم:قبول داریم که اگر به دو دسته که یکی بزرگتر از دیگری هست برسیم آن که چه کسی برنده میشود به دسته ی بزگتر بستگی دارد دارد چون دسته ی کوچکتر زود تر به پایان می رسد...........

دو دسته ی 7 و8 رو در نظر بگیر.بنا به فرض تو 7 تاثیر نداره.
حالا دسته 7 رو می کنیم 1و6 ودسته 8 رو 4و4 پس حالا باید تنها 6 مهم باشه ولی 6 از هفتی بوجود اومده که مهم نبود.
و با کاری مشابه می تونیم 4و4 را زود تر از 1و6 تموم کنیم.
لمت یه چیزیه در حد جمله هایی مثل همه دروغ گو اند.
فک کنم لمتو بد بیان کردی
لمت درسته ولی نه به دلیلی که گفتی.
کمی فکر لطفا

 

[Dark Eagle]

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

دو دسته ی 7 و8 رو در نظر بگیر.بنا به فرض تو 7 تاثیر نداره.
حالا دسته 7 رو می کنیم 1و6 ودسته 8 رو 4و4 پس حالا باید تنها 6 مهم باشه ولی 6 از هفتی بوجود اومده که مهم نبود.
و با کاری مشابه می تونیم 4و4 را زود تر از 1و6 تموم کنیم.
لمت یه چیزیه در حد جمله هایی مثل همه دروغ گو اند.
فک کنم لمتو بد بیان کردی
لمت درسته ولی نه به دلیلی که گفتی.
کمی فکر لطفا

نه عزیزیم شما منظوره منو نفهمیدی منظورم این بود که اگه مثلا 7 رو به 6 و 1 تقسیم کنیم نفری برنده میشه که توی 6 تایی برنده شده چون توی مراحلی که 6 به دسته های 1 تایی تقسیم میشه اون دسته ی دیگه که الان 1 هست به دسته های 1 تای تقسیم شده .
و هیچ ربطی به این که 4و4 زود تر از 6و1 تموم میشه نداره .....
امیدوارم فهمیده باشی وگرنه بیا تو مدرسه حس تایپ ندارم .......

این آخرین پستم نیس........

 

[Dark Eagle]

پاسخ : استقرا

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

 

[سیاوش]

پاسخ : استقرا

اگر 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
شما سوال می‌ذاری حل کنیم؟

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