International Mathematical Olympiad
July 17, 2009
The Standard Prelude makes tasks like this easy; we will use list-of (fold-of), sum, square, digits, ilog and permutations.
The first task is just a list comprehension that generates three-digit numbers and tests them for the required properties:
> (list-of n
(n range 100 1000)
(zero? (modulo n 11))
(= (/ n 11)
(sum (map square (digits n)))))
(550 803)
The second task calls for us to dissect a number and stitch it back together, looping until we find the answer:
> (let loop ((n 6))
(let ((m (+ (* 6 (expt 10 (ilog 10 n))) (quotient n 10))))
(if (= (* 4 n) m) n
(loop (+ n 10)))))
153846
The third task is a bit harder. In-position and two-consecutive count the number of contestants in the specified positions; the list comprehension loops over the permutations of (A B C D E), testing each one.
(define (in-position actual predicted)
(let loop ((a actual) (p predicted) (n 0))
(cond ((null? a) n)
((equal? (car a) (car p))
(loop (cdr a) (cdr p) (+ n 1)))
(else (loop (cdr a) (cdr p) n)))))
(define (two-consecutive actual predicted)
(let loop ((a actual) (p predicted) (n 0))
(cond ((or (null? a) (null? p)) n)
((null? (cdr p)) n)
((null? (cdr a))
(loop actual (cdr p) n))
((and (equal? (car a) (car p))
(equal? (cadr a) (cadr p)))
(loop (cddr a) p (+ n 1)))
(else (loop (cdr a) p n)))))
> (list-of p
(p in (permutations '(a b c d e)))
(= (in-position p '(a b c d e)) 0)
(= (two-consecutive p '(a b c d e)) 0)
(= (in-position p '(d a e c b)) 2)
(= (two-consecutive p '(d a e c b)) 2))
((e d a c b))
You can run the suggested solution at http://programmingpraxis.codepad.org/JRGmt2wZ.
Hi, thanks for problems. I think they are really simple to solve (you can use brute force to solve them without any difficulties :-)
The last one I even solved on paper. I share my solution:
When you took the second prediction and mark 2 consecutive contestants creating 2 disjoint pairs, you get 3 choices:
DA EC and B is somewhere else
DA CB and E is somewhere else
AE CB and D is somewhere else
Your goal is to place the “unpaired” contestant in good place.
1st choice:
B DA EC – wrong, none of them finished as it was predicted
DA B EC – B can’t be after A
DA EC B – all of them finished at it was predicted
2nd choice:
E DA CB – the correct answer!!! only C,B are at the right places
=========================================================
DA E CB – all of them finished at it was predicted
DA CB E – C is on the 3rd place – it can’t be because of the first prediction
3rd choice:
D AE CB – all of them finished at it was predicted
AE D CB – A is on the 1st place – it can’t be because of the first prediction
AE CB D – A is on the 1st place – it can’t be because of the first prediction
ruby solution for first problem (http://codepad.org/eq5LqB7o)
How do you solve these problems with a mathematical approach, for example if N is very large (something like 10^9, where bruteforce won’t work).
Problem 1 with Python:
def main(): #Variables num=0 digit1=0 digit2=0 digit3=0 sum_of_squares=0 upper_bound = 999 lower_bound = 100 count = lower_bound #while loop runs through all three digit numbers while count <= upper_bound: #Only numbers divisible by 11 are evaluated if count%11==0: #convert number to string in order to seperate digits num=str(count) digit1 = num[0] digit2 = num[1] digit3 = num[2] sum_of_squares = int(digit1)**2 + int(digit2)**2 + int(digit3)**2 if count//11 == sum_of_squares: print (num) count = count+1 else: count = count+1 else: count = count+1 main()Results should be 550 and 803.
Problem 2 with Python:
def main(): #Variables number=6 rearranged = 0 modified = 0 check = 0 #loop cycles through numbers until solution is found while check == 0: #put 6 in front and exclude last digit rearranged = "6" + str(number)[0:len(str(number))-1] modified = number * 4 #Check if solution is true if int(rearranged) == int(modified): check = 1 else: #adding ten gives the next number ending in six number = number + 10 print("The original number is:",number) main()Solution should be 153846
I think both of those python approaches could be minified and simplified.
######### Problem 1
for a in range(1,10) :
for b in range(0,10) :
for c in range(0,10) :
N = a*100 + b*10 + c
if N % 11 is 0 and N/11 == a**2 + b**2 + c**2 :
print(N)
######### Problem 2
def n() :
exp = 2
while True :
start = 10**exp
for i in range(start+6,start*10,10) :
x = (i – 6)/10 + 6 * start
if 4 * i == x :
return i
exp += 1
print(n())
I’ll try problem 3 at another time
Something happened to the formatting……smh
Answers in Ruby 2.0
=begin 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. =end def problem_1 properties = [] properties << proc do |number| number%11 == 0 end properties << proc do |number| number/11 == (number.to_s.chars.map {|digit| digit.to_i**2}.inject(:+)) end collection = [] number = 100 until number > 999 number+=1 collection << number unless properties.map{|property| property[number]}.include?(false) end collection end =begin 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. =end def problem_2 properties = [] properties << proc do |number| number.to_s.end_with? '6' end properties << proc do |number| digits = number.to_s.chars last_digit = digits.pop digits.unshift(last_digit) digits.join.to_i == number*4 end index = 0 index += 1 while properties.map{|property| property[index]}.include?(false) index end problem_1 #=> [550, 803] problem_2 #=> 153846