July 20, 2005
You want math puzzles?
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.
Posted by coyu at July 20, 2005 02:51 PMA 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.
Ah, it is as I suspected. So there are 6C2 pairs.
Posted by: A Married New York City Math Teacher at July 20, 2005 06:04 PMYou 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 at July 20, 2005 08:04 PMMinute or two. Freakin' show-offs....
Posted by: Bernard Guerrero at July 21, 2005 05: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.
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 at July 21, 2005 11:03 PMDavid 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 at July 21, 2005 11:10 PM