5
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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".
$\endgroup$
7
  • $\begingroup$ Very nice! Just to clarify how it works- Label the children from $1,2,...,100$. Assuming that the hint is true, from the given condition, one of the (reversed) sets $(72,..,1), (73,...,2),..., (100,...,29)$ of 30 people are forced to have an equal number of boys and girls. But then we can simply take the complement set of $70$ people, which clearly also has equal number of boys and girls, and also appears in the original line. Is that about right? $\endgroup$
    – Bananas
    Dec 7, 2021 at 1:28
  • $\begingroup$ Denote a boy by $1$ and a girl by $0$. In a circle, there are $100$ possible groups of $30$ people which can be formed, and each person is counted exactly $30$ times. Hence, the sum of all $100$ groups is $30 \cdot 50=1500.$ On the other hand, suppose there is no stretch of $30$ people with equal numbers. W.L.O.G. suppose there is one group of people $(1,...,30)$ with value greater than $15$. Note that adjacent groups differ by a value of $0$ or $1$. This forces every other group of $30$ to have value greater than $15$. The total sum is greater than $15 \cdot 100=1500$, a contradiction. $\endgroup$
    – Bananas
    Dec 7, 2021 at 1:50
  • 1
    $\begingroup$ @SeeHai 1) Yes, that's how to complete the proof from the hint. (In writing up the solution for the competition, I would add a line of "Since only one stretch is found in the line, it means that the other stretches in the circle must overlap with 100-1". This provides the logical reasoning, whereas you skipped this step to arrive at the conclusion) 2) Yes, that's how I was thinking to prove the hint. $\endgroup$
    – Calvin Lin
    Dec 7, 2021 at 16:01
  • 1
    $\begingroup$ 1) It is obvious. But for competition proof writing, if the solution is very short, it's best to provide each of the steps. It also depends on who the grader is. 2) 30 and 70 are complementary. Finding a 70-stretch implies the remainder 30 are also equal. However, the remainder are split into 2 groups, which makes it troublesome to account for. (EG Jaap's approach) I employed wishful thinking to combine the 2 ends and then deal with the implications, which is that the desired stretch of 30 must lie across this break. $\endgroup$
    – Calvin Lin
    Dec 7, 2021 at 20:10
  • 1
    $\begingroup$ So it boils down to showing that such a 30-stretch exists. Since we're given that there is exactly 1 30-stretch in the line, this suggests that we should show there are 2+ 30-stretches in the circle. It helps that this is a well-known fact to me. Then I reversed the approach in my writeup. $\endgroup$
    – Calvin Lin
    Dec 7, 2021 at 20:11
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @CalvinLin I have reworded it to make it a bit more explicit now. $\endgroup$ Dec 6, 2021 at 15:52
  • $\begingroup$ I'm trying to decide if my approach is essentially the same as yours. It does cover the same ideas, but with a very different presentation that makes it almost immediate (the main work is done in proving the hint). $\endgroup$
    – Calvin Lin
    Dec 6, 2021 at 15:59
  • $\begingroup$ @CalvinLin Yes, I think they are equivalent, but yours is much nicer and more direct. You're using IVM using a stretch of 30 over the rest of the circle which must cover the join, while I'm using the complement, using IVM with a stretch of 70 without the join. Yours is more direct since mine needs to set up the boundary values more explicitly and kind of already use the IVM in doing so, whereas yours rolls it all up into one application. $\endgroup$ Dec 6, 2021 at 16:10
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .