يك سوال از مرحله دوم كامپيوتر

[abdi]

اين سوال يكي از دوره‌هاي مرحله دوم كامپيوتر با كمي تغيير هست. يك كم طولانيه، اما خيلي راحت حل مي‌شه.
دو نفر اين بازي را با تعدادي سنگ‌ريزه انجام مي‌دهند: در ابتدا n سنگريزه موجود است (n>1). با توجه به قاعده بازي، دو نفر به ترتيب يكي در ميان از اين سنگريزه‌ها برمي‌دارند. قاعده بازي به اين صورت است كه در اولين حركت، بازيكن اول مي‌تواند به هر تعدادي كه بخواهد از اين سنگريزه‌ها بردارد، ولي بايد حداقل يك و حداكثر n-1 سنگريزه بردارد. پس از آن هر بازيكن در نوبت خودش مي‌تواند حداقل يك و حداكثر به اندازه تعدادي كه بازيكن ديگر در حركت قبل برداشته، سنگريزه بردارد. براي مثال اگر بازيكن اول در اولين حركتش 5 سنگريزه بردارد، در حركت بعدي بازيكن دوم مي‌تواند از 1 تا 5 سنگريزه بردارد. برنده بازي كسي است كه آخرين سنگريزه را بردارد.
nهايي را تعيين كنيد كه به ازاي آنها نفر دوم استراتژي برد داشته باشد و ثابت كنيد به ازاي بقيه nها، نفر اول استراتژي برد دارد.

 

[Olympiad]

خوب اگر نفر اول در همه ي حركت هايش يك سنگريزهبردارد و نيز n فرد باشد ، بديهي است نفر اول مي برد.نفر اول بايد درمرحله ي اول بايد كمتر از

تا سنگريزه بردارد كه بديهي است. فقط به ازاي n=2,4 نفر دوم استراتژي برددارد و براي بقيه ي n ها نفر اول استراتژي دارد.حوصله نداشتم كامل توضيحبدم اگه لازم شد بگيد تا توضيح بدم.

 

[abdi]

جوابتان غلط است. نفر دوم به ازاي بي‌شمار n استراتژي برد دارد، نه فقط به ازاي n=2,4

 

[mahanmath]

n=2[SUP]k[/SUP]

javabesh hamin balaee mishe

va ba esteghra sabet mishe vali borhan kholfesho yadam nist alan
(baraye n haye dige nemishe )

 

[abdi]

نيازي به برهان خلف نيست. اگر n تواني از 2 نباشد، نفر اول به اندازه‌اي سنگريزه برمي‌دارد كه تعداد باقي‌مانده سنگريزه‌ها نزديك‌ترين توان 2 شود.

 

[Olympiad]

ثابت كرديم به ازاي n هاي فرد نفر اول استراتژي برد دارد.فرض كنيد n=6 ، بنابراين نفر اول به اينگونه استراتژي برد دارد كه :
نفر اول ابتدا 2 مهره برمي دارد ، اگر نفر دوم يك مهره برداشت ، نفر اول هم يك مهره و در مرحله ي بعد نفر دوم مجبور است يك مهره بردارد و بعد مهره ي آخر را نفر اول
برمي دارد. اگر هم نفر دوم بعد از حركت نفر اول بيشتر از يك مهره برداشت نفر اول بقيه ي مهره ها را مي تواند بردارد .بنابراين نفر اول به ازاي n=6 استراتژي برد دارد.
براي n هاي زوج بالا تر نفر اول يكي يكي مهره برميدارد تا به 6 مهره برسد و همين استراتژي را به كار ميگيرد ،چجوري به ازاي بي نهايت n نفر دوم استراتژي دارد؟!؟!!؟

 

[navidjalalmanesh]

نفر دوم به ازای

استراتژی برد دارد . این حکم را به استقرا روی n ثابت می کنیم . حکم را برای 1 تا n-1 درست فرض می کنیم .

ابتدا به این نکته توجه کنید که اگر بازی از عددی مثل u شروع شود به طوری

(که در اینجا

و

) نفر اول t سنگریزه برمی دارد و طبق فرض استقرا نفر دوم در بازی باقیمانده برنده است که در این بازی نفر دوم , همان نفر اول بازی اصلی است .

حال حکم را برای

ثابت می کنیم . نفر اول می داند که تنها در صورتی برنده است که بعد از حرکت او ,

سنگریزه باقی بماند( با توجه به نکته ی بالا) . یعنی اگر t سنگریزه بردارد باید معادله زیر برقرار باشد :

. از طرفی نفر اول باید کمتر از نصف سنگریزه ها را بردارد ( زیرا درغیر این صورت نفر دوم در حرکت بعد می برد ) .

در نتیجه

که این با طبیعی بودن a در تناقض است . پس نفر اول در هر صورت می بازد و حکم ثابت شد .

 

[abdi]

ثابت كرديم به ازاي n هاي فرد نفر اول استراتژي برد دارد.فرض كنيد n=6 ، بنابراين نفر اول به اينگونه استراتژي برد دارد كه :
نفر اول ابتدا 2 مهره برمي دارد ، اگر نفر دوم يك مهره برداشت ، نفر اول هم يك مهره و در مرحله ي بعد نفر دوم مجبور است يك مهره بردارد و بعد مهره ي آخر را نفر اول
برمي دارد. اگر هم نفر دوم بعد از حركت نفر اول بيشتر از يك مهره برداشت نفر اول بقيه ي مهره ها را مي تواند بردارد .بنابراين نفر اول به ازاي n=6 استراتژي برد دارد.
براي n هاي زوج بالا تر نفر اول يكي يكي مهره برميدارد تا به 6 مهره برسد و همين استراتژي را به كار ميگيرد ،چجوري به ازاي بي نهايت n نفر دوم استراتژي دارد؟!؟!!؟

طبق سوال هركس مي‌تواند حداكثر به اندازه‌اي بردارد كه نفر قبل برداشته است. پس نفر اول نمي‌تواند يكي‌يكي بردارد تا به 6 سنگريزه برسد و سپس دو سنگريزه بردارد.

 

[abdi]

البته نيازي به استقراي قوي نيست. فرض مي‌كنيم براي

درست است و مي‌خواهيم براي

اثبات كنيم. سنگريزه‌ها را به دو دسته‌ي

سنگريزه‌اي تقسيم مي‌كنيم. طبق فرض نفر دوم براي هركدام از اين دو دسته استراتژي برد دارد، پس براي كل سنگريزه‌ها استراتژي برد دارد.

 

[Goharshady]

استقرای ضعیف ؛ قوی ؛ ضربی و نزول نامتناهی هم ارز هستند.
پس تفاوت زیادی ندارد.