پايه استقرا:n=1 درست است. 1 قوطي 2شكلات فرض استقرا:n=k درست. حكم استقرا: 2k+2 شكلات ,k+1 قوطي,n=k+1 ========================================================================================================== اثبات: رضا بايد در حركت اول خود يك قوطي را خالي و حذف كند زيرا در اين صورت k قوطي و 2kتا شكلات داريم كه طبق فرض اثبات شده است. حركت اول علي سه حالت دارد.1-از يك قوطي با يك شكلات بر مي دارد: در اين صورت يك قوطي حذف و رضا با برداشتن يك شكلات به طور دلخواه k قوطي و2k تا شكلات خاهيم داشت كه طبق فرض استقرا 2 شكلات دريك قوطي در آخر مي ماند. 2-از قوطي كه 2شكلات دارد بردارد: كه در اين صورت رضا از همان قوطي يك شكلات بر مي دارد و يك قو طي حذف مي شود وطبق فرض اثبات مي شود. 3-از قوطي كه بيش از 2شكلات داشته باشد بردارد: كه در اين صورت حتما ما قوطي خواهيم داشت كه يك شكلات دارد كه در اين صورت رضا با برداشتن آن شكلات يك قوطي را حذف مي كند كه در اين صورت طبق فرض اثبات مي شود.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
قسمت آخر اثباتتون اشتباهه چون ممکنه قوطی خالی هم داشته باشیم. فرض کنید همه ی قوطی ها غیر از ۲ تا خالی باشند و هر دو تا قوطی بیش از ۲ شکلات داشته باشند در این صورت حالت ۳ اتفاق می افتد ولی رضا نمی تواند کاری که شما گفتید را انجام بدهد. ضمنا در صورت مسئله نیامده که علی بازی را شروع می کند.
اثبات اصلی شبیه همین است ولی باید فرض استقرا را قوی کنید
اثبات اصلی شبیه همین است ولی باید فرض استقرا را قوی کنید
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
Olympiad گفت
اصل سوال :
تعداد 2n شکلات، به صورتی در n قوطی گذاشته شده است. دختربچه و پسربچه ای به نوبت، و هر بار يک شکلات، بر می دارند. نخستين شکلات را
دختربچه انتخاب می کند. ثابت کنيد، پسربچه می تواند طوری شکلات انتخاب کند که دو شکلات آخر، متعلق به يک قوطی باشند.
تعداد 2n شکلات، به صورتی در n قوطی گذاشته شده است. دختربچه و پسربچه ای به نوبت، و هر بار يک شکلات، بر می دارند. نخستين شکلات را
دختربچه انتخاب می کند. ثابت کنيد، پسربچه می تواند طوری شکلات انتخاب کند که دو شکلات آخر، متعلق به يک قوطی باشند.
پايه استقرا كه معلومه .....
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه فقط 1 شكلات داشته ، ما ميتونيم از جعبه اي كه بيش از 1 شكلات داره ، يه شكلات برداريم و بنابراين به فرض استقرا ميرسيم.
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه داراي تنها 2 شكلات باشد ، اونوقت ما شكلات بعدي همون جعبه رو برميداريم و به فرض استقرا مي رسيم.
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه بيشتر از 2 شكلات داشته باشد ، اونوقت ما از يك جعبه كه داراي 1 شكلات است ، شكلات برميداريم و به فرض استقرا مي رسيم
(بدهيه كه بعد از حركت نفر اول حتما جعبه اي وجود دارد كه فقط 1 شكلات داره...)
فكر كنم دقيقا راه حل rza شد !!!!!
من فكر مي كنم راه حل درسته ....
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه فقط 1 شكلات داشته ، ما ميتونيم از جعبه اي كه بيش از 1 شكلات داره ، يه شكلات برداريم و بنابراين به فرض استقرا ميرسيم.
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه داراي تنها 2 شكلات باشد ، اونوقت ما شكلات بعدي همون جعبه رو برميداريم و به فرض استقرا مي رسيم.
اگر نفر اول در حركت اول از جعبه اي شكلات بردارد كه بيشتر از 2 شكلات داشته باشد ، اونوقت ما از يك جعبه كه داراي 1 شكلات است ، شكلات برميداريم و به فرض استقرا مي رسيم
(بدهيه كه بعد از حركت نفر اول حتما جعبه اي وجود دارد كه فقط 1 شكلات داره...)
فكر كنم دقيقا راه حل rza شد !!!!!
من فكر مي كنم راه حل درسته ....
اینم راه منه:
پایه برای n=1 که گلابیه!
---
واسه n درست فرض میکنیم و واسه n+1ی: مینیمم شکلات خونه ها رو برابر min قرار می دیم. واضحه که min<=2. پس سه تا حالت زیر رو در نظر میگیریم:
min==0: بعد اینکه دختره و پسره هر کدوم یک شکلات برداشتن مساله با فرض استقرا حل میشه.
min==1: در اینصورت امکان داره دختر اول از اون خونه برداره؛ پس پسر تو نوبت بعدی از یه قوطی دیگه بر میداره و باتوجه به اینکه این قوطی رو میذاریم کنار فرض استقرا برقرار میشه. ولی اگه دختر از این برنداره، پسر تو نوبت خودش از این برمیداره و این قوطی رو کنار میذاریم و باز با فرض استقرا حل میشه.
min==2: در اینصورت همه ی قوطی ها دقیقا دو شکلات دارن. پس پسره هر دفعه از قوطی یی که دختره برداشته بر میداره.
درسته؟!
فکر کنم دقیقا راه بقیه شد
پایه برای n=1 که گلابیه!
---
واسه n درست فرض میکنیم و واسه n+1ی: مینیمم شکلات خونه ها رو برابر min قرار می دیم. واضحه که min<=2. پس سه تا حالت زیر رو در نظر میگیریم:
min==0: بعد اینکه دختره و پسره هر کدوم یک شکلات برداشتن مساله با فرض استقرا حل میشه.
min==1: در اینصورت امکان داره دختر اول از اون خونه برداره؛ پس پسر تو نوبت بعدی از یه قوطی دیگه بر میداره و باتوجه به اینکه این قوطی رو میذاریم کنار فرض استقرا برقرار میشه. ولی اگه دختر از این برنداره، پسر تو نوبت خودش از این برمیداره و این قوطی رو کنار میذاریم و باز با فرض استقرا حل میشه.
min==2: در اینصورت همه ی قوطی ها دقیقا دو شکلات دارن. پس پسره هر دفعه از قوطی یی که دختره برداشته بر میداره.
درسته؟!
فکر کنم دقیقا راه بقیه شد
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
جواب :
۱- این را بدانید که خیلی فرق دارد چه کسی شروع می کند. وقتی گفته به نوبت شما باید ثابت کنید نفر دوم استراتژی این کار را دارد و همچنین ثابت کنید نفر اول نمی تواند این کار را بکند پس خیلی فرق دارد
۲- شما در حالت سوم گفته بودید یک ظرف هست که یک شکلات دارد من الآن مثال نقض زدم بنابراین اثبات حالت سوم شما غلط است.
۳- لطفا ۱ و ۲و ۳ ننویسید!
۱- این را بدانید که خیلی فرق دارد چه کسی شروع می کند. وقتی گفته به نوبت شما باید ثابت کنید نفر دوم استراتژی این کار را دارد و همچنین ثابت کنید نفر اول نمی تواند این کار را بکند پس خیلی فرق دارد
۲- شما در حالت سوم گفته بودید یک ظرف هست که یک شکلات دارد من الآن مثال نقض زدم بنابراین اثبات حالت سوم شما غلط است.
۳- لطفا ۱ و ۲و ۳ ننویسید!
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
