3-5-8

[L.e.o]

kucheto,
Не мога да намеря математическо обеснение на алгоритъм, но задачата ти е много добра. Тотално пасва на този раздел.
Последният пост на ptj наистина ме обърка, защото ако си на ход при 1-2-3 губиш, защото противника ти ще те постави с ситуации 1-1-1 или 2-2-0, при които губиш.

kucheto,
Дай хинт. Правилно ли е да се почва отзад като се търсят губештите комбинации и така да се достигне да крайна не-губешта ситуация (за 1вия)?

[allier]

Ето какво се оказва - играта се казва обратен Ним.
http://en.wikipedia.org/wiki/Pearls_Bef ... %28game%29
Решението е точно с двоично представяне. По същата логика може да се обобщи за повече купчинки.

[kucheto]

kucheto,
Не мога да намеря математическо обеснение на алгоритъм, но задачата ти е много добра. Тотално пасва на този раздел.
Последният пост на ptj наистина ме обърка, защото ако си на ход при 1-2-3 губиш, защото противника ти ще те постави с ситуации 1-1-1 или 2-2-0, при които губиш.

kucheto,
Дай хинт. Правилно ли е да се почва отзад като се търсят губештите комбинации и така да се достигне да крайна не-губешта ситуация (за 1вия)?

Този алгоритъм, който даде allier си е направо превъзходен, макар и да не важи за комбинации с числа, които са всички по-малки от 2, но за всички други важи. Доказателство за правотата му обаче не мога да дам.

Иначе логиката на играта без теореми (ще разглеждам комбинации, където този, който е на ход губи) е следната:
1. При всички комбинации x-x-0, където x>1, играчът, който НЕ е на ход печели като държи еднакакъв брой топчета в оставащите 2 купчинки, докато в един от редовете не остане 0 или 1 топчета, където просто унищожава до 0-0-1 .
2. Първата комбинация от 3 числа е 1-1-1 (разбираемо защо ).
3. Както забеляза, ще започнем разсъжденията си отзад-напред:
а) при 1-2-x, неизвестното ще намерим като потърсим най-малкото число, което не може да приведе до друга, известна на нас комбинация, така че да не спечели другият играч:
-ако имаме 1-2-0 виждаме, че противникът ни ще доведе до 1-0-0, т.е. губим;
-ако имаме 1-2-1 виждаме, че противникът ни ще доведе до 1-1-1, т.е. губим;
-ако имаме 1-2-2 виждаме, че противникът ни ще доведе до 0-2-2, т.е. губим;
-ако имаме 1-2-3 установяваме, че съперникът ни не може да доведе до никоя от известните ни комбинации и с всеки възможен ход влошава позицията си, т.е. ние печелим
б) при 1-3-x неизвестното е 2
в) при 1-4-x по логиката от а) намираме, че най-малкото негубившо число, т.е. печелившо е 5
-изобщо всички комбинации където имаме 1-константа-неизвестно и константата е по-голяма от 1, 2-те числа трябва да са последователни и нечетното да е по-голямо от четното: 1-2-3, 1-4-5, 1-6-7, 1-8-9 и т.н.
г) да разгледаме комбинациите с числото 2 - най-малкото число, което заедно с 2 не може да комбинирано с по-горните варианти е 4:
-при 2-4-0 следва 2-2-0, т.е. губим
-при 2-4-1 следва 2-3-1, т.е. губим
-при 2-4-2 следва 2-0-2, т.е. губим
-при 2-4-3 следва 2-1-3, т.е. губим
-при 2-4-4 следва 0-4-4, т.е. губим
-при 2-4-5 следва 1-4-5, т.е. губим
-при 2-4-6 забелязваме, че противникът ни не може да доведе до изгодна за него комбинация, а 6 е най-малкото негубещо число, следователно е печелившо
- по същата логика намираме 2-5-7, 2-8-10, 2-9-11, 2-12-14, 2-13-15 и т.н.
д) да разгледаме комбинациите с 3, а най-малкото, което не може да бъде комбинирано с вариантите по-горе е 4, а по-логиката за намиране на 3-тото неизвестно, установяваме, че е 7, т.е. 3-4-7
-при 3-5-x намираме, че неизвестното е 3-5-6, което е единственото, което можем да получим при начална комбинация 3-5-8
-това са АБСОЛЮТНО ВСИЧКИ комбинации с най-високо число 8, но единствено с тази логика, без теореми с двоични бройни системи можем да си доразвием комбинациите ако искаме до 100
-интересното е, че при начало 3-5-7 можем да спечелим по 3 начина: 3-5-6, 3-4-7, 2-5-7

Да обобщим:
0-0-1
0-2-2
0-3-3
0-4-4
0-5-5
0-6-6
0-7-7
0-8-8
1-1-1
1-2-3
1-4-5
1-6-7
2-4-6
2-5-7
3-4-7
3-5-6

Надявам се, че си ме разбрал!

[ptj]

Разминаването се получи, защото аз анализирах комбинацията, която оставя играча след себе си, докато вие обратното - тази от която играе.