Search problems

13 problems match “pigeonhole principle”. Clear

Minimum red beads in a necklace ●●●●○ 100 ptsA necklace consists of 50 blue beads and a certain number of red beads. In any segment of the necklace containing 8 blue beads, there are at least 4 red beads. What is the minimum number of red beads that can be in this necklace? The beads are arranged cyclically, so the last bead is adjacent to the first.
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.
Maximum rounds guaranteeing a four-team condition ●●●●● 200 ptsThere are 18 teams in a single round-robin tournament. In each round the 18 teams are divided into 9 pairs, and the two teams in each pair play one match. The teams are regrouped from round to round, and over 17 rounds each team plays exactly one match against each of the other 17 teams. Suppose that after $n$ rounds, played according to any feasible schedule, there always exist 4 teams that have played exactly 1 match among themselves in total. Find the maximum possible value of $n$ .