Home » Problem of the Month – July, August 2019

Problem of the Month – July, August 2019

For positive integer k, let

Rn = {−k, −(k − 1), . . . , −1, 1, . . . , k − 1, k} for n = 2k and
Rn = {−k, −(k − 1), . . . , −1, 0, 1, . . . , k − 1, k} for n = 2k + 1.

A device consists of several balls and red or white ropes connecting some ball pairs. A
labeling is a coloring of each ball by one of the elements of Rn. We say that a labeling is
good if colors of any two connected balls are different. We say that a labeling is sensitive
if the colors of any two balls connected by white rope are different and the sum of colors
of any two balls connected by red rope is not equal to 0.

Let n ≥ 3 be fixed. Suppose that any device which has a good labeling by Rn has also a
sensitive labeling by Rm. Find the smallest possible value of m = m(n).