Challenge Response 18

Polka Dots on the Straight

This is a mathematical Olympiad problem. If the 1999 balls are of the same color, the succession of numbers is increasing or decreasing. Each number appears only once and there are 1999 (so there are not exactly 3 numbers that repeat an odd number of times (1 is odd), so there are balls of both colors.

Given a distribution of the balls that has in a certain position a blue ball THE and in the next position a red ball Rif there is The blue marbles to the left of THE and r red balls on your right so there's The + 1 blue balls to the left of R and r - 1 red balls on your right. The number written below THE é no = The + r and the number written under R é The + 1 + r - 1 = n.

If we change places THE and R, and we didn't move any other balls, in the new distribution there are The blue marbles to the left of R and r - 1 red balls on your right, while on the left of THE there is The blue balls and on your right r - 1 red balls. The numbers written below R and THE are a + r - 1= n - 1 and a + r - 1 = no - 1. The numbers written under the other balls do not change.

So after the exchange, the number no repeats twice less and the number no - 1 repeats twice more. Numbers that repeat an odd number of times will be the same in both configurations.

Therefore, just study the configuration in which all red balls are consecutive from the first, and all blue are consecutive from the last red.

Let a, b be the quantities of red and blue balls, respectively; then a + b = 1999. Below the first ball (it is red) is the number a - 1, the next, a - 2, then a - 3, and so on, until it has 0 in the last red ball (at position a ). So under the first blue ball there is 0, in the second 1 and so on, until the last one, which has b - 1 underneath.

If a <b, the numbers 0, 1, 2,…, a - 1 appear twice (even quantity) and the numbers a, a + 1, a + 2,…, b - 1 appear once (odd quantity) . If there are exactly 3 numbers that appear an odd number of times, these are a, a + 1, and a + 2 = b - 1. Therefore, a + b = 2a + 3, hence a = 998, and the three numbers repeat an odd amount of times are 998, 999 and 1000.

If a> b, the three numbers that appear an odd number of times are b, b +1 and b + 2 = a - 1, where a + b = 2b + 3 and the three numbers are again 998, 999 and 1000 .

Back to statement