Who wins the AI-game?

Question

Anna and Isadora play a game by writing letters on the blackboard.

• In the first round, Anna starts by writing down the letter $A$ or the letter $I$.
• In the $n$-th round with $2\le n\le 999$, Anna first writes down a new letter $A$ or $I$ immediately to the right of the other letters. Then Isadora chooses two letters already on the blackboard and swaps them.
• Isadora wins, if at the end of the $999$-th round the $999$ letters form a palindrome (= a symmetric letter sequence). Otherwise Anna wins.

Questions: Can Anna enforce a win? Can Isadora enforce a win? (As usual, we assume that Anna and Isadora use optimal strategies.)

Answer 1

Isadora wins with this strategy:

In rounds $2$ to $500$, she can swap letters at random, or swap two of the same letter. It doesn't matter what she does.

Her strategy from round $501$ onward uses the following observations: 1) a sequence of three letters that is not a palindrome can be turned into a palindrome by swapping the middle letter with either the first or third letter, and 2) a sequence of three letters that is a palindrome remains a palindrome if the first and third letters are swapped.

2) is obvious: a palindromic sequence of three letters must have the same first and third letter, so swapping them does not alter the sequence.

For 1), we just need to check these cases:
- AII: swap first and second: IAI
- IAA: swap first and second: AIA
- IIA: swap second and third: IAI
- AAI: swap second and third: AIA

In round $501$, Isabella turns the middle three letters of the final sequence of letters (the last three on the board after Anna writes a new letter, which will be in positions $499$, $500$, and $501$ in the final sequence) into a palindrome if they are not already.

In the $n$-th round, for $502 \le n \le 999$ , Isadora considers only characters $n$, $500$, and $1000-n$. She can apply observations 1 and 2 to ensure that these three letters could be part of a palindrome: that is, that the letter in position $n$ is the same as the letter in position $1000-n$. If Isadora does this every round until the end of the game, this guarantees that after round $n$, the letters from position $1000-n$ to position $n$ on the board are palindromic. After the $999$-th round, all the letters on the board will be a palindrome.

Anna cannot do anything to stop this strategy. On her turn she cannot alter the existing sequence except to append a new letter, and whichever letter she appends on round $n$, Isadora can ensure that the letters from $1000-n$ to $n$ are a palindrome.

Answer 2

Isadora will never

lose

Because:

She skips the first 500 turns(because 500th character is the middle one)
Then, starting from turn 501(and every other turn $t$) she should start making palindromes of the last $2(t-500) + 1$ characters.
For $t = 501$ we get: $2(501-500) + 1 = 3$ last characters that she should form into a palindrome.
So let's say 499th character is $A$, 500th is $A$ and 501st is $I$. In this case she should swap 500th and 501st characters and last 3 characters will form a palindrome. Repeat for every next step.
If Anna puts a letter that will make a palindrome of last $2(t-500)+1$ characters(so in previous example if 501st char would be $A$), Isadora should do nothing and wait for the next move.
If Anna puts a letter that will not make a palindrome of last $2(t-500)+1$ characters, Isadora should do one of the following:
If $charAt(500-(t-500)) \neq charAt(t)$, then
If $charAt(500) \neq charAt(t)$, then
Swap characters 500 and t,
Else
Swap characters (500-(t-500)) and t
And she will get a palindrome again.

Answer 3

Isadora can eventually

WIN

• Lets assume A is 0 and I=1

• Lets note a whichever sequence 00110... = AeI where e is the middle of sequence since 999 is odd

regardless of Ana's final sequence , Isadora can switch each two digits she wants after each round , n-1 times , it means an even number of swaps , that means the final sequence we have is :

• (AeI) $\oplus$ C

When isadora swaps the 2nd and 4th digits this operation takes place:

• abcd $\oplus$ 0101

When isadora swaps the fifth and 4th digits after anna's next move this operation would take place:

• abcde $\oplus$ 0101 $\oplus$ 00011 = abcde $\oplus$ 01001

That does mean

• C contains an even occurence of 1

lets sepatare C into ( C1 c C2 )

AeI $\oplus$ C = (A $\oplus$ C1) (e $\oplus$ c) (I $\oplus$ C2)

The winning condition for Isadora is :

• A $\oplus$ C1 = I $\oplus$ C2

there s many solutions can verify this equation , lets take an example of C1=I and C2=A

if the number of 1 is odd in C1 C2 we make c=1 and it wouldnt change anything since it is the middle of an odd sequence.