11
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Nice to see a palindrome tag created and used at last! Great puzzle too. $\endgroup$ – Rand al'Thor Mar 16 '15 at 21:11
  • $\begingroup$ Could I suggest you write point 2 as "In each $n$-th round"? Maybe I'm sleep deprived or something, but it took a bit to realise you didn't mean "at some random period in these rounds". $\endgroup$ – doppelgreener Mar 17 '15 at 6:24
  • $\begingroup$ I think it might be clearer to simply say that the board starts with an $A$ or an $I$ (whichever, it doesn't matter) already written down. Then the first rule can be eliminated and the rule for rounds $2$ to $999$ becomes the rule for all rounds. The resulting game is isomorphic to the original. I think this is clearer because I initially was confused as to what a "round" was - do Anna and Isadora act in the same round, or are their actions considered to take one round each? $\endgroup$ – Jack M Mar 18 '15 at 14:31
13
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.