BLOG

• ---

  Cayley problem 23, 1997

  
  January 22, 2020
  

  Given the set $S=\{1, 2, 3, 5, 8, 13, 34, 55\}$, how many integers $3 \leq n \leq 89$ cannot be written as the sum of exactly two different elements of $S$?

  The numbers in $S$ are Fibonacci numbers, so we may guess that some magic is involved here. Indeed, we vaguely remember something about numbers having unique representations as sums of Fibonacci numbers. If the sum of any two Fibonacci numbers is a unique integer, the job of counting possibilities would be a lot simpler. Perhaps we can prove this. Here are the first 10 Fibonacci numbers:

  
  

  $n$	1	2	3	4	5	6	7	8	9	10
  $F_n$	1	1	2	3	5	8	13	21	34	55

  Set $S$ contains $F_2$ to $F_{10}$. Notice that $F_1$ is not included in $S$. We want to prove that the sum of any two different Fibonacci numbers $F_m$ and $F_n$ with $m,n > 1$ is unique.

  Let $m < n$. There are two situations to think about. First, if $m = n-1$ then

  $$F_m + F_n = F_{n-1} + F_n = F_{n+1}$$

  by definition of Fibonacci numbers. And if $m<n-1<n$ it is clear that

  $$F_n < F_m + F_n < F_{n+1}.$$

  Either way, $F_m < F_m+F_n \leq F_{n+1}$.

  Suppose the same number $q$ can be written as the sum of two different Fibonacci numbers in two different ways:

  $$q = F_m + F_n = F_{m'} + F_{n'}.$$

  There is no loss if we suppose $m<n$ and $m' < n'$. Since $q = F_m+F_n$, we have

  $$F_n < q \leq F_{n+1}.$$

  And since $q = F_{m'} + F_{n'}$, we have

  $$F_{n'} < q \leq F_{n'+1}.$$

  Since $q$ is sandwiched between two consecutive Fibonacci numbers, it must be that $F_n=F_{n'}$ and $F_m = F_{m'}$. For Fibonacci numbers greater than $F_1$, these imply $m=m'$ and $n=n'$.

  Now we can count. Imagine all the possible sums of two elements of $S$ organized into a $9\times 9$ table. We remove the sums of the form $a + a$: this amounts to removing the diagonal which has 9 element. Then we divide by two to remove one of the upper or lower triangles of the table, because we don’t want to count both $a+b$ and $b+a$. This leaves

  $$\frac{81 - 9}{2} = 36.$$

  There are 36 integers expressible as the sum of two elements of $S$. Smallest is 3, largest is 89. In the range $3\leq n \leq 89$ there are $89-3+1= 87$ numbers. The total number of integers not expressible is therefore 87 - 36 = 51.

  Let’s check this by Racket programming.

  First we create a list of all the numbers expressible as the sum of two different elements of $S$. We use a nested for-loop with a when-clause to catch the cases we are interested in.

  (define cayley-23-list (list 1 2 3 5 8 13 21 34 55))
  
  (define expressibles
    (for*/list ((Fm cayley-23-list)
                (Fn cayley-23-list)
                #:when (> Fm Fn))
      (+ Fm Fn)))
  

  And then we filter the range of numbers from 3 to 89, keeping only the ones that are not in the expressible list. Getting the length of this filtered range solves the problem.

  (define (solve-cayley-23)
    (length
     (filter
      (lambda (n)
        (not (member n expressibles)))
      (range 3 90))))
  

  Run it in the Racket interactive REPL

  > (solve-cayley-23)
  51
  

  There we go!

• ---

  Cayley problem 21, 1997

  
  January 14, 2020
  

  From the Cayley competition, 1997. Consider the equation

  $$\dfrac{\frac{a}{c}+\frac{a}{b} + 1} {\frac{b}{a} + \frac{b}{c} + 1} = 11$$

  with the constraint ​$a + 2b + c \leq 40.$ Find all solutions ​$a,b,c$ among the natural numbers.

  If we set ​$u = \frac{a}{b}$ and do a bit of algebra, the variable ​$c$ vanishes and we are left with ​$a = 11b.$ Organizing the possible values of $a$, $b$ and $c$ into a table, we get something like…

  
  

  $a$	$b$	$c$	$a+2b+c$
  11	1	1	$11 + 2 + 1 = 14$
  11	1	2	$11 + 2 + 2 = 15$
  $\cdots$	$\cdots$	$\cdots$	$\cdots$
  11	1	27	$11 + 2 + 27 = 40$
  $\cdots$	$\cdots$	$\cdots$	$\cdots$
  22	2	1	$22 + 4 + 1 = 27$
  $\cdots$	$\cdots$	$\cdots$	$\cdots$

  If you have good bookkeeping skills, finish the whole table. You should get 42 rows! So there are 42 possible solutions.

  But let’s verify this with a little computer programming. Define a predicate that is true when the given conditions of the problem are true:

  #lang racket
  
  (define (cayley-21-conditions? a b c)
    (and (= (/ (+ (/ a c) (/ a b) 1)
               (+ (/ b a) (/ b c) 1))
  	  11)
         (<= (+ a (* 2 b) c)
             40)))
  

  Then loop through all the possibilities for $a$, $b$ and $c$ from 1 to 40 and collect them into a giant list of triples $(a,b,c)$. Then we filter this list by applying the cayley-21-conditions? predicate to each one. Those that pass are kept, those that are false are filtered out.

  (define (abc-filter max-a max-b max-c predicate)
    (filter (lambda (args)
              (apply predicate args))
            (for*/list ((a (range 1 (+ max-a 1)))
                        (b (range 1 (+ max-b 1)))
                        (c (range 1 (+ max-c 1))))
              (list a b c))))
  

  Running

  > (abc-filter 40 40 40 cayley-21-conditions?)
  

  Yields a list of solutions. Then calling length on this list gives the total number of solutions: 42.

  How many solutions would there be if the second condition was $a + 2b + c \leq 100$?