Bunuel wrote:
Two non-decreasing sequences of nonnegative integers have different first terms. Each sequence has the property that each term beginning with the third is the sum of the previous two terms, and the seventh term of each sequence is N. What is the smallest possible value of N ?
(A) 55
(B) 89
(C) 104
(D) 144
(E) 273
We can let the first sequence be a, b, c, d, e, f, g, … and the second sequence be r, s, t, u, v, w, x, ….
Notice that in the first sequence, we have:
c = a + b
d = b + c = b + (a + b) = a + 2b
e = c + d = (a + b) + (a + 2b) = 2a + 3b
f = d + e = (a + 2b) + (2a + 3b) = 3a + 5b
g = e + f = (2a + 3b) + (3a + 5b) = 5a + 8b
As we can see from the above, the 7th term of the first sequence, which is g, can be written in terms of the first two terms as 5a + 8b. Using the same logic, we can express the 7th term of the second sequence, which is x, in terms of r and s as 5r + 8s. That is,
5a + 8b = g and 5r + 8s = x
We need to have g = x. So we need to find two sets of distinct nonnegative integers {a, b} and {r, s} such that 5a + 8b = 5r + 8s provided that 0 ≤ a ≤ b and 0 ≤ r ≤ s.
Let’s rewrite the equation as:
5a - 5r = 8s - 8b
5(a - r) = 8(s -b)
Since we are looking for the smallest value of N (the 7th term of each sequence), we need to keep a, b, r and s as small as possible. To that end, let’s let a - r = 8 and s - b = 5, or, equivalently, a = r + 8 and s = b + 5. If we let r = 0, then a = 8. Since b is greater than or equal to a, the smallest value we can obtain for b is also 8. Then, s = 8 + 5 = 13. Let’s work the sequences using the values we obtained above:
a = 8, b = 8, 16, 24, 40, 64, 104
r = 0, s = 13, 13, 26, 39, 65, 104
As we can see, the smallest value of N is 104.
Answer: C