Maths Olympiad Prep

Library / /297 of 397

, 2023

Combinatorics Difficulty 6.5 National Olympiad Prove it Taiwan

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 WW wheat fields and RR 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 SS so that, regardless of the distribution of the wheat fields and rice fields, Rose can always make WR|W - R| be at least SS.

Solution

First we prove that she can always obtain 167 points. Without loss of generality, assume there are at least 666/2=333666/2 = 333 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 W333W \ge 333. Moreover, for every rice field with an egg, it is guaranteed that there is a rice field without an egg preceding it, hence R[333/2]=166R \le [333/2] = 166, so WR333166=167W - R \ge 333 - 166 = 167.

Now we prove that S=167S = 167 is the maximum. Consider the following arrangement (where R denotes a rice field, W denotes a wheat field):
{R},{W,W},{R,R},{W,W},,{R,R},{W} \{R\}, \{W, W\}, \{R, R\}, \{W, W\}, \dots, \{R, R\}, \{W\}
Note that if the hen lays eggs in kk of the W-brackets above, then she can lay eggs in at most 2k2k wheat fields, and must lay eggs in at least k1k-1 rice fields, so WR2k(k1)=k+1W-R \le 2k-(k-1)=k+1. This means that when k<167k < 167, we have WR167W-R \le 167.

It remains to consider the case k=167k = 167. Note that in the above arrangement, there are 167 W-brackets and 167 R-brackets each. This means that when k=167k = 167, the W-brackets with eggs must include the rightmost {W}\{W\}, so at most 2k12k-1 wheat fields have eggs, and thus WR(2k1)(k1)=k=167W-R \le (2k-1)-(k-1) = k = 167. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.