The sides of a $99$-gon are initially colored so that consecutive sides are red, blue, red, blue, $\,\ldots, \,$ red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides are red, blue, red, blue, red, blue, $\, \ldots, \,$ red, yellow, blue?

  • 1
    $\begingroup$ Possible hint (I haven't followed up): think about the question for small odd values of $n$ before you tackle $99$. I suspect the answer depends on $n$ mod $3$. $\endgroup$ – Ethan Bolker Dec 25 '17 at 20:26

Consider $\nu =$ the number of (yellow, red) pairs minus the number of (red, yellow) pairs in the configuration. $\nu=1$ for the initial configuration, and $\nu=-1$ for the desired configuration. The constraint on modifications effectively requires that when we make a modification of a side, its two neighboring sides should have the same color; thus modifications don't change $\nu$. Therefore passing from a $\nu=1$ configuration to a $\nu=-1$ one is impossible.

  • $\begingroup$ However correct, this answer has left me a bit dissatisfied, being asymmetrical in the colours... It would be more symmetrical if you cyclically ordered the colours (red, yellow, blue) and then added +1/3 for every colour transition in the same direction as the cycle and -1/3 in the opposite direction - $\nu$ would be the whole number and I guess then it would still be preserved... Also, any idea whether there is some hidden algebra behind this? Something modulo 3, or something to do with 3rd roots of unity or something...? $\endgroup$ – user491874 Dec 25 '17 at 21:46
  • $\begingroup$ @user8734617 I agree that the asymmetry is disturbing; in fact, we can consider any of three invariants: $\nu_\text{ry}$ (mine), $\nu_\text{yb}$, $\nu_\text{br}$; they all are equal to each other and to yours. In fact, rephrasing your idea, we can assign a $2\pi/3$ rotation to a "(ryb)-positive" color transition and $-2\pi/3$ rotation to a "(ryb)-negative" transition, and that invariant is the total number of whole turns; the winding number. $\endgroup$ – colt_browning Dec 25 '17 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.