Search problems

3 problems match “combinatorial optimisation”. Clear

Visitors search a sample. Sign in for free to search every problem. Sign in

1. Maximum red beads on a string ●●●○○ 50 ptsA string is threaded with 150 beads, each red, blue or green. Among any six consecutive beads there is at least one green bead, and among any eleven consecutive beads there is at least one blue bead. What is the maximum number of red beads on the string?
2. Guaranteed score erasing blackboard numbers ●●●●● 200 ptsThere are 68 pairs of non-zero integers on a blackboard. Some pairs may be identical. For each positive integer $k$, at most one of the pairs $(k,k)$ and $(-k,-k)$ appears on the blackboard. A student erases some of the 136 numbers so that the sum of any two erased numbers is not $0$. For each of the 68 pairs, if at least one number from that pair is erased, the student scores one point. Find the largest score that the student can guarantee, whatever the 68 pairs on the blackboard are.
3. Maximum points removing stones from piles ●●●●● 200 ptsThere are 100 piles, each containing 400 stones. On each move, Petya selects two piles, removes one stone from each, and earns as many points as the absolute difference between the numbers of stones in these two piles (before the removal). Petya must remove all the stones. What is the maximum total number of points he can earn?