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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s