7
$\begingroup$

There are 1000 marbles of different colors such that each color is present no more than 500 times. Prove that you can place marbles around a circle so any adjacent marbles are of different colors.

$\endgroup$
2

3 Answers 3

13
$\begingroup$

Here is a bit different, in my opinion simpler, solution.

Number the positions from 1 to 1000 around the circle.

If there are 500 marbles of the same color, put them in all the odd positions and the rest in the even positions.

If not, group the marbles by color. Using one group after another, fill the odd positions 1, 3, 5, ..., 999, then fill the even positions 2, 4, ..., 1000.

Since no group has 500 marbles, a group will be used up before doing a full circle. Therefore, the marble of a color will have no chance to be placed adjacent to a previous marble of the same color.

And here is another way

Let's say the most numerous marbles are the white ones.

Arrange the white marbles in a circle, leaving holes between them.

Then put one marble, any color, in each gap. There are more marbles remaining than holes, so you have a marble in each hole.

Finally, take the remaining marbles and place them anywhere between two white marbles where there isn't one marble of the same color. Since there are at least as many holes as marbles of any color, you will always find a suitable hole.

Voilà! Every white marble is separated from the next one with at least one marble (1st round), and for every other color, the marbles are in different holes, so they are separated by at least one white marble.

$\endgroup$
2
  • $\begingroup$ clever solution and simpler indeed. seems like i overkilled it. $\endgroup$ Dec 17, 2022 at 19:16
  • $\begingroup$ A really good solution (the one I initially came up with when I got this puzzle), but there's still a more elegant one! $\endgroup$
    – NielIGuess
    Dec 17, 2022 at 21:15
3
$\begingroup$

Label the positions 1, 2, ..., 1000 so that each one is adjacent to the ones with the next higher and lower numbers, and 1000 is adjacent to 1.

If there are (say) 500 red marbles, then put those in the odd positions, and the other 500 marbles in the even positions in any order.

Otherwise, if there are (say) 499 red marbles, then put those in odd positions 1 through 997. There are at least two other colors (say green and blue), at least one of which has two or more marbles (say green); put green marbles in 998 and 1000, a blue marble in 999, and the rest in the other even positions in any order.

Otherwise, fill the positions in this order: 1, 502, 3, 504, ..., 499, 1000, 501, 2, ..., 997, 498, 999, 500. Start with all of the marbles of one color, then all the marbles of a second color, and so on. No two positions on the list are adjacent, and even if e.g. the first 498 are the same color, then they'll end up in odd positions 1 through 499 and even positions 502 through 998, none of which are adjacent to each other; or if the second 498 are the same color, then they'll end up odd positions 3 through 499 and even positions 502 through 1000, none of which are adjacent to each other.

$\endgroup$
3
$\begingroup$

More mathematical/graph theory based solution:

This is doable for any even $n$ marbles such that the same marble appears atmost $\frac{n}{2}$ times.

Consider a graph where there is an edge between marble $x$ and marble $y$ if they are not of the same colour. Then this problem reduces to finding a Hamiltonian cycle in this graph.

In general this is NP-complete, but note that the graph here is very dense. For any marble $x$, there are atleast $\frac{n}{2}$ valid edges. In particular, for any two vertices $x$ and $y$, $degree(x) + degree(y) \ge n$.

Ore's theorem states that a Hamiltonian cycle would exist for such a graph. A proof can be found in the wiki page here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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