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.

	public function solve():void {
	txtResult.text = "";
	var count:int = 1;
	var k:int = 10;
	while (k * 11 < 1000) {
	// Calculate sum of the squares of the digits
	var sumSquares:int = 0;
	var n:int = k * 11;
	while (n > 0) {
	var digit:int = n % 10;
	sumSquares += digit * digit;
	n /= 10;
	}
	// Check
	if (sumSquares == k) {
	txtResult.text += count + ") " + (k * 11) + "\n";
	++count;
	}
	++k;
	}
	}

view raw gistfile1.as hosted with ❤ by GitHub

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:

	public function solve():void {
	txtResult.text = "";
	var k:int = 1;
	var k_up:int = 10; // Minimum (10^p) greater that k.
	while (true) {
	var n:int = (10 * k) + 6;
	var m:int = (6 * k_up) + k;
	// Check
	if (m == 4 * n) {
	txtResult.text += "ANSWER: " + n;
	break;
	}
	++k;
	if (k >= k_up) {
	k_up *= 10;
	}
	}
	}

view raw gistfile1.as hosted with ❤ by GitHub

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:

	def permutations(array)
	n = array.length
	return [array] if n < 2
	rt = Array.new
	for i in 0...n
	## Create a new array from [array] where the
	## [i]-th term has been ignored.
	t = Array.new(array)
	t.delete_at(i)
	tz = permutations(t)
	tz.each do |tp|
	rt << tp.unshift(array[i])
	end
	end
	return rt
	end

view raw gistfile1.rb hosted with ❤ by GitHub

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!

	public function solve():void {
	txtResult.text = "";
	// Create array of permutations of students.
	var p:Array = permutations(students.split(""));
	// Check every possibility.
	for (var k:int = 0; k <= p.length; ++k) {
	var s1:int = singleCorrectPredictions(p[k], guess1.split(""))
	var d1:int = doubleConsecutivePredictions(p[k], guess1.split(""))
	var s2:int = singleCorrectPredictions(p[k], guess2.split(""))
	var d2:int = doubleConsecutivePredictions(p[k], guess2.split(""))
	if ((s1 == 0) && (d1 == 0) && (s2 == 2) && (d2 == 2)) {
	// Conditions satisfied, print solution!
	txtResult.text += p[k] + "\n";
	}
	}
	}
	private function singleCorrectPredictions(master:Array, guess:Array):int {
	var rt:int = 0;
	for (var k:int = 0; k <= guess.length; ++k) {
	rt += (guess[k] == master[k])? 1 : 0;
	}
	return rt;
	}
	private function doubleConsecutivePredictions(master:Array, guess:Array):int {
	var rt:int = 0;
	for (var i:int = 0; i <= guess.length - 1; ++i) {
	for (var j:int = 0; j <= master.length - 1; ++j) {
	if ((guess[i] == master[j]) && (guess[i + 1] == master[j + 1])) {
	++rt;
	break; // breaking here because elements are different.
	}
	}
	}
	return rt;
	}

view raw gistfile1.as hosted with ❤ by GitHub

Take care!