# Problem 6.

There are $n$ houses in a row, painted in $k$ different colors, and for any color, there are 100 consecutive houses, among which the number of houses of this color is strictly greater than the number of houses of any other color. What is the largest $k$ for which this is possible if: a) $n=404$? b) $n=406$?
Answer: 202 colors in both parts. Solution:

Example for part a) with 202 colors:

Let's call a 198-block a sequence of 198 consecutive houses, where any pair of houses 99 apart is painted in a unique color (i.e., among all 404 houses, there are no other houses of that color).

Let's call a 2-block a pair of houses painted in a unique color.

Now, paint the 404 houses as follows: 2-block, 198-block, 2-block, 2-block, 198-block, 2-block

406 houses can also be painted in 202 colors by adding two houses at the end, whose color matches the last 2-block.

Estimate for part a):

For each color, there must be at least 2 houses → a maximum of 404 houses

Estimate for part b):

Suppose we could paint 406 houses in 203 colors, meaning each color was used twice.

Number the colors in the order they appear when traversing the houses, so for the $i$-th color, the houses with numbers $a_{i}$ and $b_{i}$ are painted, and $a_{i} < b_{i}$. If $a_{i} < a_{j} < b_{j} < b_{i}$, then any segment containing both houses of the $i$-th color also contains both houses of the $j$-th color.

Now, instead of painting the houses, consider a sequence of letters $a$ and $b$, where $a$ represents the houses with numbers of the form $a_{i}$ (where $b$ represents $b_{i}$).

Among the first 100 letters, there is exactly one $b$, since for the 1st color, the segment can only be from the 1st to the 100th house

(That is, the first color appears twice in this segment, while any other color appears at most once)

This means that among the first 100 letters, there are 99 $a$s. Therefore, among the letters from 100 to 199, there are at least 98 $b$s

(Since there are 98 numbers $a_{i \geq 2}$ for which $b_{i} \geq 100$, but $b_{i} \leq 199$, since $b_{i} - a_{i} \leq 99$)

Then, among the first 199 houses, there are at most 100 $a$s, so $a_{101} \geq 200$

Similarly, among the last 199 houses, there are at most 100 $b$s, so $b_{103} \leq 206$, which means

$$
200 \leq a_{101} < a_{102} < a_{103} < b_{103} \leq 206, \quad 200 \leq a_{101} < b_{101} < b_{102} < b_{103} \leq 206
$$

Now consider the hundred for $a_{102}$ and $b_{102}$.

Either it contains 206, in which case it contains $a_{103}$ and $b_{103}$, or it contains 200, in which case it also contains $a_{101}$ and $b_{101}$

Then this hundred contains two houses of another color, a contradiction

Criteria: Correct solution: 25 points (+)

Checking the correct example is not required, the example in part b) is not evaluated separately

Part a) (example plus simple estimate): 13 points $(+/ 2)$

Only example: 8 points ( (