یک سوال از مبحث ترکیبیات ( استقرا)

[Niloofar sharafi]

سلام
این سوال مرحله 2 المپیاد کامپیوتر سال 80 بوده . منتهی چون ترکیبیات المپیاد ریاضی و کامپیوتر تقریبا یکیه ، این جا می ذارمش .

سوال : یک سطر نامتناهی از خانه های 1*1 با شماره های 1 ، 2 و ... داده شده است . در ابتدا دو مهره در خانه های 1 و 2 قرار دارند . در هر مرحله ، یکی از دو مهره را به دلخواه انتخاب می کنیم و اگر این مهره در خانه شماره i باشد ، آن را i خانه خالی به جلو می بریم ، یعنی در صورتی که مهره دیگری در هیچ یک از خانه های i+1 تا 2i نباشد ، آن را به خانه 2i و در غیر این صورت به خانه 2i+1 می بریم . ثابت کنید به ازای هر عدد طبیعی مانند n ، می توان با انجام تعدادی حرکت یکی از مهره ها را به خانه ی شماره n برد .

بسیار به جوابش نیاز دارم .
ممنون :)

 

[monajem]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

خیلی راحت
با استقرا حل میشه
کتاب ترکیبیاتو مگه نداری شما؟
اون جا نوشته

تو بخش استقرا

 

[Niloofar sharafi]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

خیلی راحت
با استقرا حل میشه
کتاب ترکیبیاتو مگه نداری شما؟
اون جا نوشته

تو بخش استقرا

:Pخودمم گفتم که استقرائه .
سوال رو هم از همون کتاب زرد ترکیبیات فاطمی نوشتم .
منتهی راه حل و حتی راهنمایی هم نداره .

 

[monajem]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

چرا داره.....

استقرای دو پایه بزن....رو فرد و زوج

حکم را تغییر می دهیم:

به ازای هر عدد طبیعی مثل i میتوان تعدادی حرکت انجام داد که یکی از مهره ها توی i یکی تو یکی کمتر از () باشه

ادامه بده خیلی راحته

 

[Niloofar sharafi]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

می شه لطفا شماره صفحه بدین ؟ من هر چی می گردم ، پیدا نمی شه .

 

[monajem]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

راست میگی!
نیست تو کتاب ترکیبیات

خب ادامه می دیم:
من برا اعداد فرد ثابت می کنم:
اگر فرض کنیم که حکم برای اعداد یک تا n که فرد است درست است،ثابت می کنیم برای n+2 نیز درست است:
خب نصف n+1را در نظر می گیری
طبق حکم میشه یه جوری اوردش که یه دونه مهره جلوش باشه و در محدوه ی تا n
خب حالا عملیاتو روش انجام میدیم
میاد تو n+2
برا زوج ها هم یه چیزی شبیه اینه

 

[Niloofar sharafi]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

ای بابا !
چه خوب بود .
دست شما درد نکنه .
من یه سوال دیگه هم مشکل داشتم ، پس اونم می ذارم دیگه :
"در هر خانه از یک جدول ( (2 به توان ام*) -1)ضربدر ((2 به توان هاش**)-1) یکی از اعداد 1 و -1 نوشته شده است به طوری که عدد واقع در هر خانه برابر حاصل ضرب اعداد واقع در خانه هایی است که با این خانه ضلع مشترک دارند . ثابت کنید همه اعداد واقع در این جدول برابر 1 هستند ."
پیشاپیش دست شما درد نکنه

*ام = m
**هاش = h

 

[monajem]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

ناوردایی یا اکستر مال میخواد
.....روش فکر می کنم

تو کتاب ترکیبیات بود؟؟؟؟!!!

 

[Niloofar sharafi]

پاسخ : یک سوال از مبحث ترکیبیات ( استقرا)

نه ، هنوز نخوندم .
نه ، تو یکی دیگه از کتابای آقای علیپور بود . می دونم که قراره با استقرا حل شه ( استقرای ضعیف )