This post follows from Part 5.

**Part 6**

In this post, we shall explore another method of colouring, more often known as **assigning weights**. Commonly in such questions, we tend to involve \( +1, -1 \) a lot since the common technique of taking *product* and *sum* gives us lots of additional information. I would advise the reader to take special care as to the motivation behind finding a suitable invariance sum or product as it would help in the exercise in the next post.

(IMO shortlist 2005) There are \( n \) markers, each with one side white and the other side black, aligned in a row with their white sides up. At each step, if possible, we choose a marker with the white side up (but not one of the outermost markers), remove it, and reverse the two neighbouring markers. Prove that one can reach a configuration with only two markers left if and only if \( 3 \nmid n-1 \).

*Solution*: Just playing around with small examples can lead to one trivial observation: the **parity** of the number of black markers remains unchanged during the game. Hence if only two markers are left, they must have the *same colour*.

We can see that we can assign "weights". Well, here the best thing to encode would be the number of black markers. Remember that \( (-1)^n \) for some \( n \) provides lots of information by encoding the parity(when we consider **sums**), let us define assign to a *white* marker with \( n \) black markers to its left the value \( (-1)^n \). We only assign values to the white markers. Denote \( \mathbb{S} \) as the sum of all numbers assigned to the white markers.

Consider an arbitrary white marker with both of its neighbours initially white and with \( k \) black markers to its left. We perform an operation on that marker and see how it affects \( (-1)^n \). Clearly, if we turn both of its neighbouring markers black and remove it, then \( \mathbb{S} \) decreases by \( -(-1)^k + (-1)^{k-1} + (-1)^{k-1} = 3 (-1)^{k-1} \). Therefore, we have just shown that \( \mathbb{S} \pmod 3 \) is invariant.

If the game ends with two black markers then \( \mathbb{S} \equiv 0 \pmod 3 \) and if it ends with two white markers then \( \mathbb{S} \equiv 2 \pmod 3 \). \( \rightarrow 3 \nmid n-1 \).

To show that if we start with \( n ≥ 5 \) markers and \( n \equiv 0,2 \pmod 3 \) satisfies the conditions. By removing the \( 3 \) leftmost white markers (that do not violate the conditions), we obtain a row of \( n-3 \) markers. By **working backwards**, we can reach \( 2 \) or \( 3 \) white markers. We are done with the former and for the latter we can reach \( 2 \) black markers. □

The next post will be tomorrow! :)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestNice solution, but I have a couple questions:

Don't you also have to consider removing a white marker with a black on at least one side? Also, at the end how do you remove 3 white markers while leaving the others still white?

Log in to reply

I have the same problem as you about considering the other cases. However, I think I can explain the second part of your question: I initially we have WWWWWW......WWWWWW, ie.

nwhites. Let us apply the operation to the white second from the left (the first legal white). This leaves us with: BBWWWWW.....WWWWWW, ie. 2 blacks followed byn-3whites. Now apply the operation to the new first legal white, the white in new position 3. This leaves us with: BWBWWWW...WWWWWWWW, ie. BWB followed byn-5whites. Finally, apply the operation to the white in position 2 to achieve WWWWWWW...WWWWWWW, ie.n-3whites.Log in to reply

Oh yeah I realized that a couple hours after I posted.

Log in to reply

Log in to reply

Log in to reply