Boys and girls in a circle

Question

There are $28$ students in a class, and each of them are either boy or girl. They sit in a circle, and claim that “The two people next to me are of different gender than each other.” It's known that all boys lied and exactly $3$ girls lied. How many girls are there in the class?

---

Source: HK IMO prelim 2020 Q5

Answer 1

I think there are

$19$ girls in the class

Proof

Suppose we are in a situation where no girls lie. Then each girl has a boy and a girl next to them. Looking at the adjacent boy, he must have two girls next to him. Continuing the pattern around the circle, we find that we have a pattern of the following form $$ G, G, B, G, G, B, \ldots$$ going all the way around the circle.
In particular, we find that there are two girls for each boy and the number of students must be divisible by $3$.
Now suppose we add a lying girl, then the effect on the pattern is either we have a section of three consecutive girls $$ G, G, B, G, G, G, B, G, G, B, \ldots $$ or we have a position where there is a "boy, girl, boy" section as follows $$ G, G, B, G, B, G, G, B, G, G \ldots$$ In the first case, the number of students must increase by $1$ modulo $3$ and in the second case the number decreases by $1$ modulo $3$. To make it simpler, if we begin with a $2:1$ ratio, girls to boys, then the first operation increases the number of girls by one and the second decreases it by one. Since we have $3$ lying girls and $28 \equiv 1 \mod 3$, we must have two of the first case and one of the second which means we must have $19$ girls and $9$ boys. A realisation of this is as follows $$ G, G, B, G, G, G, B, G, G, B, G, B, G, G, B, G, G, B, G, G, G, B, G, G, B, G, G, B $$

Credit where it's due

Jaap Scherphuis spotted an error in my original reasoning which helped me to fix it.

Answer 2

Here is a more algebraic approach.

Let $k$ be the number of boys. The assumption that they all lie implies that each boy is sitting between two girls. Hence they divide the $28 - k$ girls into $k$ segments, with each segment containing at least one girl.

Let $a_1, \dotsc, a_k$ be the length of these segments. We then have $$\sum_{i = 1}^k a_k = 28 - k.$$ For each segment $a_i$, if $a_i = 1$, then the unique girl in that segment lies; otherwise, exactly $a_i - 2$ girls in that segment lies.

Let $u$ be the number of segments with $a_i = 1$. It is clear that $u \leq 3$. Moreover, the number of lying girls is equal to $$2u + \sum_{i = 1}^k(a_i - 2) = 2u - 2k + \sum_{i = 1}^ka_i = 2u - 2k + (28 - k) = 28 + 2u - 3k.$$

Therefore we obtain $28 + 2u - 3k = 3$, or $3k - 2u = 25$. Together with $u \leq 3$, an argument mod $3$ shows that $u = 1$ and $k = 9$ is the only possibility.

Hence there are $9$ boys and $19$ girls.

Answer 3

Let's say there are all girls or all boys:

They are all lying since their neighbors have the same gender

So all boys are lying, what does that mean?

If we have a B, their neighbors cannot be B and G, they either have to be BBB or GBG. There have to be at least 3 girls in the class because we know exactly three of them lied. What would happen if we had two boys together? BBG or BBBBBBBG, the one on the end next to a girl would be telling the truth because there would be a string of boys on one side and a girl on the other. This isn't possible because that boy would be telling the truth and it is stated that all boys are lying, so we know that if a B appears, it must be surrounded by two Gs.

So if they were 50/50:

So there must be at least as many girls as boys because the boys have to be surrounded by girls. But if we just have one girl between two boys, she would be a liar, so it cannot just be BGBGBGBGBG all the way. To keep the boys as liars and let some girls tell the truth, they need to be BGGBGGBGGB, so two girls between the boys. This makes the girls be telling the truth and lets the boys stay liars.

How many?

If we repeat BGG 9 times we get 27 students with all boys (9) lying and all girls (18) telling the truth. We can insert another G between any two to add a lying girl, or we can remove a G to change an existing G into a liar (changing BGGB to BGB). So we move one G from a pair (making the static girl into liar #1 surrounded by two boys) to between two other G (making her liar #2 and leaving the other two girls as truth-tellers because they still have boys on the other side) and add another girl somewhere between two Gs (not affecting them, but adding a new liar #3). That's 19 girls and 9 boys.

So the answer is:

19 girls

Answer 4

Another answer seems possible with a little lateral-thinking:

there are 0 girls in the class.
All 28 boys in the circle lied about the gender of the people next to them.
3 girls (who aren't in the class) lied about being relevant to the problem.