Winning strategy at "Turning Turtles". From the written above I understand how to calculate the Nim-Value of it: H=1, T=0.

Konciljev56

Konciljev56

Answered question

2022-09-04

Winning strategy at "Turning Turtles"
I'd like like to know if there is a winning strategy for this game.
From the written above I understand how to calculate the Nim-Value of it:
H = 1 , T = 0
H T T H T T H T H T = 1001001010, and Nim-Value of it is:
( 100 ) ( 100 ) ( 10 ) ( 10 ) = 0 - this is loosing situation (if I understand right...).
So my question is:
How can I bring from loosing situation to a winning situation? (if it's possible)
And I don't understand something: lets say that this is the board H T T H T T H T H T = 1001001010 - and it's my turn. I'm at loosing position (Nim-Val is 0), and I can do a move that make the next player at loosing position also:HTTHTTTTTT - and the next player is at Nim-Val of 0 (loosing position). Where is my mistake here?

Answer & Explanation

Lena Ibarra

Lena Ibarra

Beginner2022-09-05Added 13 answers

Step 1
You need to understand two things:
1. How to translate Turning Turtles to Nim, and back.
2. What the winning strategy is in Nim.
Turning Turtles Nim
A coin with the Head side up at position i is equivalent to a Nim heap of size i. That is, HTTHTTHTHT is equivalent to a Nim position with heaps of size 1,4,7 and 9.
Flipping coins numbered i and j, where i<j, so that coin number j was originally heads, is equivalent to reducing the Nim heap of size j to a Nim heap of size i. For example, from HTTHTTHTHT, you could flip coins number 2 and 7, resulting in HHTHTTTTHT. If you translate both to Nim positions, this looks like
( 1 , 4 , 7 , 9 ) ( 1 , 2 , 4 , 9 ) ,
which is indeed like reducing a Nim heap of size 4 to one of size 2.
Step 2
The exception to this correspondence is when both coins are turned from heads to tails. For example, moving from HH,H to THT. In this case, the first Nim position was (1,2,3), and it seems like the result should be (1,1,2), since we flipped coins 3 and 1. Here, we have to mentally delete any repeated heaps, so instead of (1,1,2), we just get a single Nim heap of size 2. These repeated heaps do not affect the Nim outcome.
Now that you know how Turning Turtles positions and moves correspond to Nim, all you need to know is…
Winning Strategy in Nim
To find a winning move in a Nim position with heap size n 1 , , n k , all you need to do is the following:
- Compute the Nim sum of the heap sizes: m = n 1 n k . A winning move exists iff m 0.
- Compute n i m for each i { 1 , , k }. If n i m is a smaller number than n i , then reducing the n i heap to n i m is a winning move.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?