Here's a math puzzle. Taken from the 46th International Mathematical Olympiad, held in rainy Merida, Mexico:

In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than two-fifths of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems.Give yourself four hours and thirty minutes. Incidentally, Romania won four gold medals, a silver, and a bronze at the Olympiad out of her six contestants. They're all high school students.

A nice problem! I got it in a minute or two

without pencil and paper, but that's because I

teach undergrad discrete math. I think this

would be a good homework problem for my

students, but maybe too tricky for an exam.

A hint: Remember the Lake Wobegon Principle,

which says that it is not possible for every

number in a set to be above average (strictly

greater than the arithmetic mean).

It's a bit more straightforward to show that there is at least _one_ student who answered exactly five of the questions, but once you have this it's not hard to see why there is a second one.

To clarify one of the conditions (or not): For each

pair of distinct problems A and B, the fraction of

students who answered _both_ A and B is _strictly

greater than_ two-fifths.

Posted by: Dave MB | July 20, 2005 at 06:18 PM

Ah, it is as I suspected. So there are 6C2 pairs.

Posted by: A Married New York City Math Teacher | July 20, 2005 at 07:04 PM

You know, on reflection, I think I like this problem a little less. It's possible to guess the method of the solution from the semantics of the problem, which is a little different from the combination of insight and perspiration which I believe the creators of the problem wanted.

(Took me five. I am getting slow. But I three have taught discrete math.)

Posted by: Carlos | July 20, 2005 at 09:04 PM

Minute or two. Freakin' show-offs....

Posted by: Bernard Guerrero | July 21, 2005 at 06:23 PM

[Carlos suggests problem is less satisfying]

It is sort of straghtforward for an Olympiad, but

when you consider that it's meant for high-school

students who may or may not have studied the

discrete math material, it makes a little more

sense. The extra wrinkle about the _second_

contestant with exactly five answers is a

reasonable test of the solver's care and precision.

But this was probably one of the easiest

problems on the Olympiad, sort of like the

first problem on the Putnam (US/Canada

ugrad prize exam) that always somehow

involves the year of the exam.

Looking at the other problems, I think my

favorite is #2 on the first day, although it's

also pretty easy once you see it and stop

thinking about number theory or set theory.

Problem #1 on the first day is pretty standard

geometry unless there's a slicker argument

I'm not seeing. (There are some inviting

wrong ways to do it, which is always good

on a test like this.)

Problem #4 is also very cute, and has some

of the puzzle-solving aspect you're looking

for. You can do some calculations to find out

_in what way_ the answer works, then some

basic number theory to solve it.

The other two don't interest me that much on

first sight.

Off-topic -- I recall Carlos' interest in

_luchadoras_ (female professional wrestlers)

from _For All Nails_. There's an NYT article

today about luchadoras in Bolivia, of all places.

Posted by: Dave MB | July 21, 2005 at 10:46 PM

Glancing through the scores, it looks like problem 6 was perhaps the hardest for the participants, and problem 4 the easiest. Does Belgium teach discrete math in its curriculum? Because they're the only nation which shows -- from my rough eyeballing -- a better than their expected ability for problem 6.

So my intuition on what makes a math puzzle too easy is off. Okay, that's not exactly a surprise.

Bernard, the thing about teaching this stuff is that you get a) a very hands-on feel for how students think, and get b) a lot of practice at puzzle problems.

Posted by: Carlos | July 22, 2005 at 12:03 AM

David MB, it's not that I have an interest in luchadoras per se...

(Okay, Doug, you can stop laughing.)

... but that I was trying to come up with a USM version of the difference feminism you had developed for the CNA. My reasoning behind my posts on the USM always followed the idea that the USM was the id to the CNA's superego. So USMexican feminism's leader was a combination of Tammy Faye Baker, Imelda Marcos, and Andrea Dworkin (whom I knew very slightly).

Having her title her manifesto Mi Lucha put it all together.

Posted by: Carlos | July 22, 2005 at 12:10 AM