10th Irish 1997 Problem B4 How many 1000-digit positive integers have all digits odd, and are such that any two adjacent digits differ by 2?
8·3 499 Solution Let b n be the number of such numbers with last digit 1 or 9, c n the number with last digit 3 or 7, and d n the number with last digit 5. Then we have b n+1 = c n , c n+1 = 2d n + b n , d n+1 = c n . Hence c n+2 = 2d n+1 + b n+1 = 2c n + c n = 3c n . Evidently, c 1 = 2 (3, 7), and c 2 = 4 (13, 53, 57, 97). Hence c 2n = 4·3 n-1 , c 2n-1 = 2·3 n-1 . Hence b 2n = d 2n = 2·3 n-1 , so b 2n + c 2n + d 2n = 8·3 n-1 . 10th Irish 1997 © John Scholes jscholes@kalva.demon.co.uk 17 Dec 2003 Last updated/corrected 17 Dec 03