## Queuing

From the 2011 South African Junior Olympiad:

Several people line up in single file. A solitary latecomer wishes to join the queue. Prove that it is always possible for them to join the line so that the number of men in front of them is equal to the number of women behind them.

What a beautiful problem statement! Such a simple idea, a pleasing result, but no immediate explanation. Thankfully, it comes out fairly quickly with the correct approach.

Consider the quantity

number of men in front – number of women behind.

If the latecomer joins the back of the queue, this quantity is either zero (in which case we are done) or positive. But what is most useful about this quantity is that as they move forward through the queue, no matter whether they pass a man or a woman, the quantity always decreases by 1. Hence is must eventually reach zero, at which point we are done.

The proof above is the one I came up with. Now I will present a brilliant alternative argument from one of my pupils:

Place the latecomer so that the number of people in front of them is equal to the total number of women (excluding the extra person) in the queue!

Convince yourself that this always works, and you will appreciate its elegance.

Advertisements

### One thought on “Queuing”

1. Byron June 18, 2017 / 3:48 pm

I believe this is equivalent to another puzzle: You are seated at a table in a dark room. On the table are 100 identical flat coins (90 heads up, 10 tails up). You cannot see or feel whether a coin is heads up or tails up. Your task is to create two piles of coins containing identical numbers of tails up coins.

Like