Maths Olympiad Prep

Library / /443 of 520

Combinatorics Difficulty 6.1 National olympiad Prove it

Example 38 Place 4 Go stones evenly on the circumference of a circle, and define the operation rules as follows: if the adjacent stones are of the same color, place a black stone between them; if they are of different colors, place a white stone between them. Then remove the original 4 stones, and this completes one operation. Prove: regardless of the initial arrangement of black and white stones on the circumference, it will take at most 4 operations for the circumference to be entirely black stones.

Solution

To prove that due to the unknown colors and arrangement of the initial 4 chess pieces, the situation is relatively complex according to the problem statement. Below, we construct a valuation model that reflects the requirements of the problem, which can simplify the problem and thus provide a proof.

Let the initial 4 chess pieces be xi(i=1,2,3,4) x_{i} (i=1,2,3,4) , and assign values to the chess pieces.
Let
xi={1, if xi is a black piece, 1, if xi is a white piece. (i=1,2,3,4) x_{i}=\left\{\begin{array}{l} 1, \text { if } x_{i} \text { is a black piece, } \\ -1, \text { if } x_{i} \text { is a white piece. } \end{array}(i=1,2,3,4)\right.

And define xixi+1={1, if xi and xi+1 are the same color, 1, if xi and xi+1 are different colors,  x_{i} x_{i+1}=\left\{\begin{array}{c}1 \text {, if } x_{i} \text { and } x_{i+1} \text { are the same color, } \\ -1, \text { if } x_{i} \text { and } x_{i+1} \text { are different colors, }\end{array}\right. and xi2=1 x_{i}^{2}=1 .

After the first operation, the 4 chess pieces can be represented as
(x1x2),(x2x3),(x3x4),(x4x1). \left(x_{1} x_{2}\right),\left(x_{2} x_{3}\right),\left(x_{3} x_{4}\right),\left(x_{4} x_{1}\right).

After the second operation, the 4 chess pieces can be represented as
(x1x2)(x2x3),(x2x3)(x3x4),(x3x4)(x4x1),(x4x1)(x1x2), \left(x_{1} x_{2}\right)\left(x_{2} x_{3}\right),\left(x_{2} x_{3}\right)\left(x_{3} x_{4}\right),\left(x_{3} x_{4}\right)\left(x_{4} x_{1}\right),\left(x_{4} x_{1}\right)\left(x_{1} x_{2}\right),
which simplify to (x1x3),(x2x4),(x3x1),(x4x2)\left(x_{1} x_{3}\right),\left(x_{2} x_{4}\right),\left(x_{3} x_{1}\right),\left(x_{4} x_{2}\right).

After the third operation, the 4 chess pieces can be represented as
(x1x3)(x2x4),(x2x4)(x3x1),(x3x1)(x4x2),(x4x2)(x1x3), \left(x_{1} x_{3}\right)\left(x_{2} x_{4}\right),\left(x_{2} x_{4}\right)\left(x_{3} x_{1}\right),\left(x_{3} x_{1}\right)\left(x_{4} x_{2}\right),\left(x_{4} x_{2}\right)\left(x_{1} x_{3}\right),
which simplify to (x1x2x3x4)\left(x_{1} x_{2} x_{3} x_{4}\right).

After the fourth operation, the 4 chess pieces are all (x1x2x3x4)2\left(x_{1} x_{2} x_{3} x_{4}\right)^{2}, so the values of these 4 chess pieces are all 1.
This indicates: after only 4 operations, all the pieces on the circle are black.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.