Combi Problem - Proving Existence of a row

Question

The following problem comes from a Problem Set that concluded recently -

Problem: $50$ girls and $50$ boys stand in line in some order. There is exactly one stretch of $30$ children next to each other with an equal number of boys and girls. Show that there is also a stretch of $70$ children in a row with an equal number of boys and girls.

I've tried a couple of approaches and seem to be going nowhere. One approach I tried was applying the Pigeonhole Principle by defining the $71$ possible rows of $30$ children as pigeons, and another thing I attempted was considering the contrapositive, but nothing seems to work.

I would appreciate any hints (not a full solution) towards solving this problem.

Answer 1

For now, consider the children in a circle, instead of a line.

Hint: Show that in the circle, there are at least 2 stretches of 30 children with equal numbers.
It's a standard problem in the literature to show that there is 1 stretch, and a slight extension of the same ideas to show that there are 2 stretches.
This is where the main "work" is done in solving the problem. The rest of the statements should follow easily (so even if you're stuck showing the hint, assume the hint and move on).

Now apply the condition that there is exactly 1 stretch in the line.
What can we conclude about the other stretch(es) in the circle, given that it doesn't appear in the line?
Hence, how can we find the 70 children in the line?

Notes

• Condition can be relaxed to "at most one stretch of 30 children".

Answer 2

There is a counterexample if you replace "exactly one" by "at least one". Rearrange the line to a circle and observe the difference " boys-girls" while moving the row of 30 one to the left or right. Something intersting will happen if you cross the end of the line.

Answer 3

Consider the value of (#boys-#girls) for each stretch of 30 adjacent kids. For exactly one of these this value is zero. Can you deduce anything about all the values that occur before reaching the zero, or all the values after the zero? Apart from the zero, can all the values be positive? Or all negative? What does this mean for the values of the first and last stretches in the row?

And what do those values then tell you about the (#boys-#girls) value for the last and first stretches of 70 adjacent kids in the row?

Hint: intermediate value theorem.