2007 iTest Problems/Problem TB3

Problem

4014 boys and 4014 girls stand in a line holding hands, such that only the two people at the ends are not holding hands with exactly two people (an ordinary line of people). One of the two people at the ends gets tired of the hand-holding fest and leaves. Then, from the remaining line, one of the two people at the ends leaves. Then another from an end, and then another, and another. This continues until exactly half of the people from the original line remain. Prove that no matter what order the original 8028 people were standing in, that it is possible that exactly 2007 of the remaining people are girls.

Solution

Let each boy be and let each girl be . Once half of the people from the original line leave, we have a group of 4014 people that were all adjacent in the line. Thus we are looking for a block of 4014 people such that half of them are girls. Then the sum of the the people in the block would be 0.

We shall now look at 3 cases for the left-most block of the original line with size 4014:

• Case 1: The sum of the people in the block is greater than 0.

Then the sum of the people in the right-most block is less than 0, since the sum of all the people is 0. When we move a block one person over, the sum is either increased by two, decreased by two, or remains the same. Since the original sum is even (there are an even number of people adding odd integers to the sum), when we shift the block to the right, we will eventually find a block with a sum of 0, since the right-most block is negative.

• Case 2: The sum of the people in the block is less than 0.

Then the sum of the people in the right-most block is greater than 0, since the sum of all the people is 0. When we move a block one person over, the sum is either increased by two, decreased by two, or remains the same. Since the original sum is even (there are an even number of people adding odd integers to the sum), when we shift the block to the right, we will eventually find a block with a sum of 0, since the right-most block is positive.

• Case 3: The sum of the people in the block is 0.

This is what we want.

In all 3 cases we get what we want; thus we always have a group of 4014 adjacent people with half of them girls.