ماراتن ترکیبیات
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:b406fe81fb]41[/center:b406fe81fb]استراتژی برد این سوال هم دقیقا مثل نیم معمولی است با این تفاوت که وقتی هیچ دسته ای از لوبیاها با بیش از 2 لوبیا نداشته باشیم ، باید تعداد فردی دسته ی تک لوبیایی باقی بگذاریم.(در بازی معمولی باید تعداد زوجی باقی بگذاریم تا جمع نیم صفر شود)
برای اطلاعات بیشتر به این جا مراجعه کنید:
http://en.wikipedia.org/wiki/Nim#Mathematical_theory
به این بازی می گن Misere nim چون همون nim هست که به صورت Misere بازی می شود.
برای اطلاعات بیشتر به این جا مراجعه کنید:
http://en.wikipedia.org/wiki/Nim#Mathematical_theory
به این بازی می گن Misere nim چون همون nim هست که به صورت Misere بازی می شود.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:7a13330ac7]41[/center:7a13330ac7]استراتژی برد این سوال هم دقیقا مثل نیم معمولی است با این تفاوت که وقتی هیچ دسته ای از لوبیاها با بیش از 2 لوبیا نداشته باشیم ، باید تعداد فردی دسته ی تک لوبیایی باقی بگذاریم.(در بازی معمولی باید تعداد زوجی باقی بگذاریم تا جمع نیم صفر شود)
برای اطلاعات بیشتر به این جا مراجعه کنید:
http://en.wikipedia.org/wiki/Nim#Mathematical_theory
به این بازی می گن Misere nim چون همون nim هست که به صورت Misere بازی می شود.
برای اطلاعات بیشتر به این جا مراجعه کنید:
http://en.wikipedia.org/wiki/Nim#Mathematical_theory
به این بازی می گن Misere nim چون همون nim هست که به صورت Misere بازی می شود.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:232e33d325]42[/center:232e33d325]
پی نوشت: برای درک درست از مسابقات پلی آف این تصویر را ببینید:
[center:232e33d325]
[/center:232e33d325]
فدراسیون تنیس به همه ی تنیس بازان کشور نمره ی شایستگی داد. به بهترین بازیکن شماره ی 1 به بعدی 2 و ...
می دانیم در بازی دو تنیس باز اگر اختلاف شماره ی آنها بیش از 2 باشد ، حتما تنیس باز با شماره ی کمتر برنده می شود.
در بازیهایی به شیوه ی المپیک (پلی آف)1024تنیس باز شرکت کردند. قهرمان این مسابقات حداکثر کدام شماره را می تواند داشته باشد؟
تعمیم: برای حالت کلی 2[SUP]k[/SUP] تنیس باز هم حل کنید.
----پی نوشت: برای درک درست از مسابقات پلی آف این تصویر را ببینید:
[center:232e33d325]
[/center:232e33d325]
SABB گفت
[center:39f6760f89]
42
[/center:39f6760f89]اینی که مینویسم مطمئن نیستم؛
اگه
تا تیم باشند، تیمی که برنده نهایی است باید در مجموع
بازی انجام دهد. از طرفی هر تیم با شماره
(به جز تیم شماره 1) حداکثر می تواند در بازی با
تیم برنده شود. حالا برای این که
حداکثر شود باید داشته باشیم
که برای
نتیجه می گیریم
.
42
[/center:39f6760f89]اینی که مینویسم مطمئن نیستم؛
اگه
Olympiad گفت
SABB گفت
[center:43ce0cb402]
42
[/center:43ce0cb402]اینی که مینویسم مطمئن نیستم؛
اگه
تا تیم باشند، تیمی که برنده نهایی است باید در مجموع
بازی انجام دهد. از طرفی هر تیم با شماره
(به جز تیم شماره 1) حداکثر می تواند در بازی با
تیم برنده شود. حالا برای این که
حداکثر شود باید داشته باشیم
که برای
نتیجه می گیریم
.
42
[/center:43ce0cb402]اینی که مینویسم مطمئن نیستم؛
اگه
سوالو اشتباه متوجه شده بودم
- ارسال ها
- 302
- لایک ها
- 5
- امتیاز
- 0
من نتونستم تو این استدلال اشتباهی ببینم:
فرض کنید x_0 = 1 و x_n شماره‌ي کسیه که x_{n-1} رو برده.
بنابراین x_{n+1} <= (x_n)+2 چون در غیر این صورت نمیتونه x_n رو ببره.
حالا دقت کنین که برنده‌ی نهایی x_k هست و با نامساوی ای که نوشتم x_k <= 2k+1
اگه تساوی اتفاق بیافته یعنی باید شماره‌ی 3 ، 1 رو ببره. بنابراین شماره‌ی 2 رو باید 4 ببره.
پس شماره‌ی 5 ، 3 رو باید ببره و شماره‌ی 6 ، 4 رو. با ادامه‌ی این استدلال می‌بینیم که
تو مرحله‌ي یکی مونده به آخر 2k و 2k-1 باید فقط باقی مونده باشن یعنی 2k+1 نمیتونه برنده بشه.
پس بیشترین شماره‌ی برنده برابره با 2k. خیلی راحت میشه یه روش بازی برای بردن شماره‌ی 2k ساخت.
فرض کنید x_0 = 1 و x_n شماره‌ي کسیه که x_{n-1} رو برده.
بنابراین x_{n+1} <= (x_n)+2 چون در غیر این صورت نمیتونه x_n رو ببره.
حالا دقت کنین که برنده‌ی نهایی x_k هست و با نامساوی ای که نوشتم x_k <= 2k+1
اگه تساوی اتفاق بیافته یعنی باید شماره‌ی 3 ، 1 رو ببره. بنابراین شماره‌ی 2 رو باید 4 ببره.
پس شماره‌ی 5 ، 3 رو باید ببره و شماره‌ی 6 ، 4 رو. با ادامه‌ی این استدلال می‌بینیم که
تو مرحله‌ي یکی مونده به آخر 2k و 2k-1 باید فقط باقی مونده باشن یعنی 2k+1 نمیتونه برنده بشه.
پس بیشترین شماره‌ی برنده برابره با 2k. خیلی راحت میشه یه روش بازی برای بردن شماره‌ی 2k ساخت.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
43
[center:076f8216ff]43[/center:076f8216ff]
سوال چهل و سوم را از این لینک بگیرید:
[center:076f8216ff]×××http://informatics.iranblog.com/?mode=DirectLink&id=716440×××
[/center:076f8216ff]
[center:076f8216ff]43[/center:076f8216ff]
سوال چهل و سوم را از این لینک بگیرید:
[center:076f8216ff]×××http://informatics.iranblog.com/?mode=DirectLink&id=716440×××
[/center:076f8216ff]
- ارسال ها
- 302
- لایک ها
- 5
- امتیاز
- 0
هر دو تا نفر دوم استراتژی برد داره.
قسمت اول :
هر جا اولی رنگ کرد دو تا خونه پایین تر یا دو تا خونه بالاترشو رنگ می‌کنیم
(دقت کنید دقیقا یکی از این حرکتا قابل انجامه).
قسمت دوم :
جدول رو به چهار مربع دو در دو تقسیم می‌کنیم.
اگه نفر دوم بتونه یه مربعو کامل کنه که هیچ.
وگرنه‌ی اون گوشه‌ی جدول که تو مربع دو در دویی که
نفر اول توش یه خونه رو رنگ کرده هست رنگ می‌کنه.
اگه نفر اول یکی از گوشه‌های جدول رو رنگ کرده باشه
میتونه تو همون مربع دو در دو خونه‌ای رو رنگ کنه که نفر
اول با یه حرکت برنده نشه.
قسمت اول :
هر جا اولی رنگ کرد دو تا خونه پایین تر یا دو تا خونه بالاترشو رنگ می‌کنیم
(دقت کنید دقیقا یکی از این حرکتا قابل انجامه).
قسمت دوم :
جدول رو به چهار مربع دو در دو تقسیم می‌کنیم.
اگه نفر دوم بتونه یه مربعو کامل کنه که هیچ.
وگرنه‌ی اون گوشه‌ی جدول که تو مربع دو در دویی که
نفر اول توش یه خونه رو رنگ کرده هست رنگ می‌کنه.
اگه نفر اول یکی از گوشه‌های جدول رو رنگ کرده باشه
میتونه تو همون مربع دو در دو خونه‌ای رو رنگ کنه که نفر
اول با یه حرکت برنده نشه.
[center:2521aa34cc]44[/center:2521aa34cc]دو نقطه یکی به رنگ آبی و دیگری به رنگ قرمز روی خطی مشخص شده اند و نقطهی آبی در سمت چپ نقطه ی قرمز قرار دارد. می توانید دو نقطه همسایه همرنگبه خط اضافه کنید یا دو نقطه این چنینی را حذف کنید. ثابت کنید پس از چندبار استفاده از این تبدیل نمی توان به حالتی رسید که فقط دو نقطه ی رنگیروی خط باشند که یکی آبی و دیگری قرمز باشد و نقطه قرمز در سمت چپ نقطه یآبی باشد. (تورنمنت شهرها - 1993)