1
$\begingroup$

Sixty points, of which thirty are coloured red, twenty are coloured blue and ten are coloured green, are marked on a circle. These points divide the circle into sixty arcs. Each of these arcs is assigned a number according to the colours of its endpoints: an arc between a red and a green point is assigned a number $1$, an arc between a red and a blue point is assigned a number $2$, and an arc between a blue and a green point is assigned a number $3$. The arcs between two points of the same colour are assigned a number $0$. What is the greatest possible sum of all the numbers assigned to the arcs?

Let $W$ be function which assign to each red/green/blue point value $1/0/3$. By this assigment we can generate proper assigment of arcs, if consecutive points on circle are $x_i$ and $x_{i+1}$ then we assign to arc beetwen them $|W(x_i)-W(x_{i+1})|$. So we want maximum value of $$ S= \sum_{i=1}^{60}|W(x_i)-W(x_{i+1})|$$ where $x_{61} =x_1$. Now we see that $S$ does not decrease if we have in a sequence two consecutive points of the same color, say with colors $a,a,b,c$, where $b,c$ can also be $a$ or can be the same colors $b=c$, by replacing $a$ and $b$: $$|a-a|+|a-b|+ |b-c|\leq |a-b|+|b-a|+|a-c|$$

So we see that the best arrangement of colors is if don't have consecutive points with the same color.

Have I missed something?

Edit: Thanks to Yorch

$\endgroup$
1
  • $\begingroup$ I suspect that may not be the only best arrangement (try others where there are no blue pairs and no green pairs) but it seems to be equal best $\endgroup$
    – Henry
    Jul 27, 2021 at 14:43

1 Answer 1

3
$\begingroup$

A correct red/green/blue function $W$ would be $1/0/3$

We now have $S = \sum\limits_{i=1}^{60} |W(x_i) - W_{x_{i+1}}| = \sum\limits_{i=1}^{60} x_i + x_{i+1}- 2\min(W(x_{i}),W(x_{i+1})) = 2(30(1) + 10(0) + 20(3)) - 2\sum\limits_{i=1}^{60}\min(W(x_{i}),W(x_{i+1}))$.

So now we would like to minimize the sum on the right. It is clear that at most $20$ summands can be $0$, and so the sum is at least least $40$, and that is achievable by placing the green balls in positions that are multiples of $6$ and placing the red balls in positions that are odd. We get that $S= 180 - 2\cdot 40 = 100$.

$\endgroup$
2
  • $\begingroup$ I know this argument is mostly correct, but when you color the points with the repeating pattern $\mathrm{RBRGRB}$, the score should be $100$, not $140$. There are $40$ red-blue pairs, and $20$ red-green pairs, for a score of $40\cdot 2+20\cdot 1=100$. I cannot see what went wrong in your calculation of $S$, however. $\endgroup$ Jul 27, 2021 at 17:33
  • $\begingroup$ Thank you very much, fixed ! $\endgroup$
    – Asinomás
    Jul 27, 2021 at 17:46

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.