4. (13 points) In a circle, there are 17 people: each of them is either a truth-teller (he always tells the truth) or a liar (he always lies). Everyone said that both of their neighbors are liars. What is the maximum number of liars that can be in this circle?
Answer: 11.

Solution. A truth-teller can only be surrounded by liars. Three liars in a row cannot stand, so between any two nearest truth-tellers, there is one or two liars. Then, if there are 5 or fewer truth-tellers, there can be no more than 10 liars in the gaps between them, making a total of no more than 15 people. This leads to a contradiction. Therefore, there must be at least 6 truth-tellers, and no more than 12 liars, but there are 17 people in total, so there must be 11 liars. An example with 11 liars is easily provided.

Grading Criteria. Full solution - 13 points. Example constructed - 3 points. Estimate proven - 9 points. Correct estimate named but not justified by considering examples - 2 points.