# Problem 7. (3 points)

On an island, there live vegetarians who always tell the truth, and cannibals who always lie. 50 residents of the island, including both women and men, gathered around a campfire. Each of them said either "All men at this campfire are cannibals" or "All women at this campfire are vegetarians," and both phrases were spoken. What is the maximum number of vegetarian women that could have been at the campfire?
Answer: 48

## Solution:

We will prove that if we have $n$ people, the maximum number of vegetarian women is $n-2$.

First, note that if someone has called someone a cannibal, then we definitely have at least one cannibal.

Second, according to the condition, there is at least one man. Therefore, the only case where we can have $n-1$ vegetarians is the case where the remaining person is a male cannibal. However, in this case, he cannot say either of the two phrases from the condition. Therefore, this case is impossible, and besides the vegetarians, there must be at least two more people.

If we have $n-2$ vegetarian women, the remaining two can either be two men (a cannibal and a vegetarian) or two cannibals (a man and a woman).