A school night out

From the 2004 Turkey Junior Maths Olympiad:

One evening, more than \frac{1}{3} of the students at a school go to the cinema. On the same evening, more than \frac{3}{10} go to the theatre and more than \frac{4}{11} go to a concert. What is the smallest possible number of students at the school?

When I first saw this problem, I thought it would be fairly easy to solve with a little bit of algebra. It ended up taking much longer than I expected, and I admire the problem as a result.

Let n be the number of students at the school, and let x, y, z be the number of students who go to the cinema, the theatre and the concert respectively. The conditions given amount to:

x> \frac{n}{3}

y> \frac{3n}{10}

z> \frac{4n}{11}.

These turn into

n < 3x

3n < 10y

4n < 11z.

Since all these quantities are positive integers, we have

n \leq 3x-1

3n \leq 10y-1

4n \leq 11z-1.

Adding 110 lots of the first inequality, 33 lots of the second and 30 lots of the third yields

329n \leq 330(x+y+z) - 173.

But x+y+z \leq n, so in fact we have

329n \leq 330n - 173,

so that n \geq 173. To show that 173 is possible, we replace all the inequalities with equations, to obtain

173 = 3x-1

519 = 10y-1

692 = 11z-1.

Solving these gives us (x,y,z) = (58,52,63). Since 58 is more than \frac{1}{3} of 173, and 52 is more than \frac{3}{10} of 173, and 63 is more than \frac{4}{11} of 173, this is indeed a solution, and so the minimum possible number of students at the school is 173.

This is a great problem. What really makes it tricky is the fact that \frac{1}{3} + \frac{3}{10} + \frac{4}{11} is almost 1, and since the problem is discrete, a lot of objects are required to provide such sensitive fractions. The discreteness is crucial, since it allows you to convert strict inequalities into the more useful ‘less than or equal to’ inequalities above.

 

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