666 fields line up in a row, with each field being a wheat field or a rice field. Rose the hen lays an egg on each of the wheat fields and rice fields, so that for each egg, there is at most one field without egg between it and the closest egg to its right. Find the largest positive integer so that, regardless of the distribution of the wheat fields and rice fields, Rose can always make be at least .
, 2023
Solution
First we prove that she can always obtain 167 points. Without loss of generality, assume there are at least wheat fields.
Consider the following operation: let the hen start from the field at the front of the row. If she is on a wheat field, she immediately lays an egg and then advances one field; otherwise, she first advances one field, lays an egg, and then advances one more field. Note that this strategy guarantees that every wheat field has an egg, so . Moreover, for every rice field with an egg, it is guaranteed that there is a rice field without an egg preceding it, hence , so .
Now we prove that is the maximum. Consider the following arrangement (where R denotes a rice field, W denotes a wheat field):
Note that if the hen lays eggs in of the W-brackets above, then she can lay eggs in at most wheat fields, and must lay eggs in at least rice fields, so . This means that when , we have .
It remains to consider the case . Note that in the above arrangement, there are 167 W-brackets and 167 R-brackets each. This means that when , the W-brackets with eggs must include the rightmost , so at most wheat fields have eggs, and thus . This completes the proof.