Saturday, July 11, 2009

Solving simple International Mathematical Olympiad problems.

Solving simple International Mathematical Olympiad problems by programming is a sadistic stress reliever. They were originally thought to be solved using only paper, pencil and lots of young and smart neurons. Let's amuse ourselves solving them with a bit of code. Afterall, Why not to use the nukes? :D

Follow the links for the solutions in AS3, but if you felt tempted give them first a try, some of these problems can even make a nice programming interview exercise (if the position at hand requires minimal mathematical skills from your candidates).

IMO 1960 Problem 01
Determine all three-digit numbers N having the property
that N is divisible by 11, and N/11 is equal to the sum
of the squares of the digits of N.



It's a simple loop with known limits. I guess the average programmer can solve this quickly.


IMO 1962 Problem 01
Find the smallest natural number n which has the following
properties:

(a) Its decimal representation has 6 as the last digit.
(b) If the last digit 6 is erased and placed in front of the
remaining digits, the resulting number is four times as
large as the original number n.


A bit involved, because now your loop doesn't have a limit:


IMO 1963 Problem 06
Five students, A,B,C,D,E, took part in a contest.
One prediction was that the contestants would finish in the
order ABCDE. This prediction was very poor. In fact no
contestant finished in the position predicted, and no two
contestants predicted to finish  consecutively actually did so.
A second prediction had the contestants finishing in the
order DAECB. This prediction was  better. Exactly two of the
contestants finished in the places predicted, and two disjoint
pairs of students predicted to finish consecutively actually
did so. Determine the order in which the contestants finished.



Now we are talking.... Raise your hand if you know what a permutation is. Ok. Now every one of you have to code a working version in five minutes. Counting! :D
I couldn't do it. As always the optimized permutation generator slips through the holes in my mind. So I had to resort to my simple but inefficient recursive generator, it has the advantage that if I forget it, I can deduce it again. Here my ruby version:


Once you have a working generator of permutations the rest is just loop through all the possible outcomes and checking if the conditions are satisfied.
Hmm... pretty boring for human minds, even if there are only 5! = 120 possibilities. It's no wonder that the solution for this problem in my book is a one liner without explanation. I guess this problem deserves the nukes!


Take care!

2 comments:

  1. The first problem can be solved in Python (and in many other languages) in a single line, this shows how much powerful and clearer other languages are than C or Java.

    [n for n in range(100,1000) if n%11==0 and n/11==sum([int(d)**2 for d in str(n)])]

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete