; challenge.scm -- Jens Axel Søgaard -- 17th oct 2004 ; This is a solution to the challenge set forth by Frank Buss ; at ; We consider the triangle ; C ; ^ ; / \ ; / \ ; / \ ; A ------- B ; From A we drawn n lines and from B m lines. ; The goal is to count the number of triangles the lines form. ; Theorem ; The number of triangles is given by the formula ; B(n+1,2)(m+1) + B(m+1,2)*(n+1) + (n+1)(m+1) ; n>0, m>0 ; where B denotes a binomial coeffecient. ; Proof ; Call the line AB for bottom. We look at three cases. ; i) Triangles where bottom is a side ; The other sides are formed by one line emanating from A ; and the other from B. This gives (n+1)(m+1) triangles. ; ii) Triangles formed from two non-bottom lines from A and ; one non-bottom line from B. ; There is B(n+1,2) ways of choosing two non-bottom lines ; from A. The number of non-bottom lines from B is m+1. ; This gives B(n+1,2)*(m+1) triangles. ; iii) Triangles formed from two non-bottom lines from B and ; one non-bottom line from A. ; By symmetry with ii) this gives B(m+1,2)*(n+1) triangles ;;; IMPLEMENTATION (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) (define (binomial n m) (/ (fact n) (* (fact (- n m)) (fact m)))) (define (triangles n m) (cond [(= n 0) (+ m 1)] [(= m 0) (+ n 1)] [else (+ (* (binomial (+ n 1) 2) (+ m 1)) (* (binomial (+ m 1) 2) (+ n 1)) (* (+ n 1) (+ m 1)))])) ;;; TEST ; (map (lambda (n) (triangles n n)) ; (list 0 1 2 3 4 5 6 7 8 9 10)) ; => (1 8 27 64 125 216 343 512 729 1000 1331) ; (triangles 2 1) ; => 15