Browse · MathNet
Print48th Austrian Mathematical Olympiad
Austria counting and probability
Problem
A necklace contains pearls, each of which has one of the colours black, green or blue. In each step we replace simultaneously each pearl with a new pearl, where the colour of the new pearl is determined as follows: If the two original neighbours were of the same colour, the new pearl has their colour. If the neighbours had two different colours, the new pearl has the third colour.
a. Is there such a necklace that can be transformed with such steps to a necklace of blue pearls if half of the pearls were black and half of the pearls were green at the start?
b. Is there such a necklace that can be transformed with such steps to a necklace of blue pearls if thousand of the pearls were black at the start and the rest green?
c. Is it possible to transform a necklace that contains exactly two adjacent black pearls and blue pearls to a necklace that contains one green pearl and blue pearls?
a. Is there such a necklace that can be transformed with such steps to a necklace of blue pearls if half of the pearls were black and half of the pearls were green at the start?
b. Is there such a necklace that can be transformed with such steps to a necklace of blue pearls if thousand of the pearls were black at the start and the rest green?
c. Is it possible to transform a necklace that contains exactly two adjacent black pearls and blue pearls to a necklace that contains one green pearl and blue pearls?
Solution
a. Since is divisible by , we can alternatingly take two black and two green pearls. In the first step, all pearls are already replaced by blue pearls.
b. If we assign to each blue pearl the number , to each green pearl the number and to each black pearl the number , then it holds in each step that the new colour of a pearl modulo is equal to the negative sum of its two original neighbours. The new total sum of all colours modulo therefore can be calculated by multiplying the old total sum of all colours with and changing the sign. But modulo , a multiplication with is equivalent to a multiplication with , therefore the total sum always remains the same modulo . For a necklace with only blue pearls the total sum is . But for black and green pearls it is (mod ). Therefore, there does not exist an arrangement of black and green pearls that can be transformed into a necklace with only blue pearls using such steps.
c. Using the same assignment of numbers modulo , in each step the sum of all colours in even positions becomes the sum of the colours in odd positions, and vice versa. If these sums are and in the beginning, then at the end we still have these same two sums modulo , maybe with switched positions. But in the beginning, we have sums and modulo , because both among the even and among the odd positions there is exactly one black pearl with value , and otherwise only blue pearls with value . However, at the end we are supposed to have sums and because one of the two sums is determined only by blue pearls with value , and the other by exactly one green pearl with value and only blue pearls with value otherwise. Therefore, it is not possible.
b. If we assign to each blue pearl the number , to each green pearl the number and to each black pearl the number , then it holds in each step that the new colour of a pearl modulo is equal to the negative sum of its two original neighbours. The new total sum of all colours modulo therefore can be calculated by multiplying the old total sum of all colours with and changing the sign. But modulo , a multiplication with is equivalent to a multiplication with , therefore the total sum always remains the same modulo . For a necklace with only blue pearls the total sum is . But for black and green pearls it is (mod ). Therefore, there does not exist an arrangement of black and green pearls that can be transformed into a necklace with only blue pearls using such steps.
c. Using the same assignment of numbers modulo , in each step the sum of all colours in even positions becomes the sum of the colours in odd positions, and vice versa. If these sums are and in the beginning, then at the end we still have these same two sums modulo , maybe with switched positions. But in the beginning, we have sums and modulo , because both among the even and among the odd positions there is exactly one black pearl with value , and otherwise only blue pearls with value . However, at the end we are supposed to have sums and because one of the two sums is determined only by blue pearls with value , and the other by exactly one green pearl with value and only blue pearls with value otherwise. Therefore, it is not possible.
Final answer
a: yes; b: no; c: no
Techniques
Invariants / monovariantsModular ArithmeticColoring schemes, extremal arguments