The Standard Bank IT Challenge (SBITC) is an annual coding competition for undergraduate and honours students in South Africa. The contest consists of two rounds: a regional event named the “heats”, and the final. In the heats, teams of up to four students each compete against other teams from the same university, and the winning team from each of the nine top-performing universities is invited to the final round in Johannesburg. Each member of the winning team wins a prize, and the winning university receives a large cash prize, but students mostly participate for the enjoyment that is to be obtained in solving the problems, and to test their skills against a set of problems that is designed to challenge the participants.
This year, the final problem from the heats (which took place on Saturday, 16 May) was fairly mathematical in nature; or more-so than the other problems at least. Essentially, the problem asks the following:
We consider generalised Fibonacci sequences which satisfy the same recurrence relation
as the Fibonacci numbers, but with the first two terms
and
being arbitrary positive integers.
Now for some positive integer , we can ask if
will occur in such a sequence. The answer is yes, since one could consider any sequence where
. Less trivially, one could consider the sequence where
and
. The problem from the heats asks for the values of
and
for which
occurs as late in the corresponding sequence as possible. If there is a tie between two sequences which contain
, then we choose the sequence for which
is as small as possible.
Problems in coding contests usually have a story attached to them to make the problem statement more interesting. In this case, the problem was framed in terms of an archaeological expedition which sought to understand an ancient peoples to whom Fibonacci-like sequences were culturally significant. I have—however—lost my copy of the problems, and so am not able to provide the problem statement as it was given in the competition. I can provide a solution, however.
A good start to the problem would be to try to see what terms in these general Fibonacci-like sequence look like. If we start experimenting by calculating the first few terms, we see that
and we recognise the coefficients of and
as the standard Fibonacci numbers
given by
and
for
. We may conjecture that
for all
. This is indeed true, and can be proven by using mathematical induction.
The statement that occurs in such a sequence then becomes
for some positive integer
.
(We saw above that we can always make sure that is at least the third term in the sequence, and so we do not lose any generality by only considering
for positive
)
This suggests a method for trying to tackle the problem. We could consider all pairs of Fibonacci numbers which are below
, and attempt solve the corresponding equation for
and
. If we find a solution for which
and
are positive integers, then
occurs at position
in the corresponding sequence. We then simply find the largest
for which a solution exists, and use the solution
for which
is as small as possible. (In accordance with the problem specification) Since Fibonacci numbers grow exponentially, the number of pairs which we have to consider is logarithmic in
, and so this solution is feasible provided that we can efficiently solve the equation
for
and
.
Such equations for which we seek integer solutions are known as Diophantine equations, after Diophantus of Alexandria. While it is known that there is no general algorithm for solving general Diophantine equations, and no algorithm for even determining whether an arbitrary Diophantine equation has a solution, solutions are known for many special cases. In particular, there is a method for finding all solutions of linear Diophantine equations of the form , where
,
and
are known integers, and
and
are integers which are to be determined. This is exactly the form of the equation which we wish to solve, and I shall outline the method for finding all possible solutions below.
The first question which one may ask is: “When does the equation have integer solutions?”. Clearly, if
is a solution, then the greatest common divisor of
and
must be a factor of
. Is the converse true? If
divides
, then does the equation necessarily have a solution in integers? The answer is yes. To prove this, we will make use of the following lemma:
Bézout’s Lemma: If and
are any integers, then there exist integers
and
such that
.
This is often proven by considering the set of all positive integers of the form , and showing that the smallest of them must be a divisor of both
and
. A proof that is more useful if we wish to find the integers
and
is based on Euclid’s Algorithm for finding the greatest common divisor of two elements. I shall prove the following:
Suppose that and
are positive integers, each at most
. Then there exist integers
and
such that
.
This is clearly true for , since the only possibility is
. Now suppose that this holds for some
. We will show that it is also true for
as follows: Suppose
and
are positive integers, each at most
. If
, then
. Otherwise, suppose without loss of generality that
. Then
for some integers
and
, and we can take
and
.
The general case (where and
need not be positive) follows by noting that
.
The proof above shows not only that the integers and
exist, but provides a method for finding them recursively: first find the values of
and
for
, and use them to calculate the values of
and
for
(if
. The case
is similar). The base case for the recursion is
.
Many results about divisibility of numbers rely on Bézout’s Lemma. I will not prove these results, but will freely make use of them.
We now return to the question of whether the equation has integer solutions if
. Let
. By Bézout’s Lemma, we can find integers
and
such that
. If we take
and
, then
, and so we have found a solution. The question now becomes “How does one find all possible solutions?”
Suppose that is any solution to the equation, and that
is some other solution. Let
. Then
, and so
. Thus
and so
where
. Let
. Then
, and so
. We see that the most general possible solution to the equation is
where
,
is any integer, and
is any particular solution.
We now have all of the machinery which is needed to solve the problem. However, there are a few more results which greatly simplify the actual calculations which need to be performed.
Note that to find the general solution to , we need to know the value of
. It is well known that the Fibonacci numbers possess the remarkable property that
. We do not need the general case here, but only that
, which can easily be proved by induction.
We see that the equation always has a solution, and that the general solution is given by
and
where
is any solution to
, and
is an arbitrary integer.
We are interested in the cases where and
are positive, and also in the smallest possible value for
. The largest value of
for which
is positive is
. This follows from noting that
This also gives us the smallest possible positive value of since
is a decreasing function of
. If this value for
does not make
positive, then we see that it is impossible for
and
to be simultaneously positive (
is an increasing function of
), and so there is no solution. Otherwise, we can use the solution corresponding to this value of
.
We can now solve the original problem as follows:
- Loop over the pairs of Fibonacci numbers
for which
.
- For each pair, find integers
and
such that
using the algorithm from Bézout’s Lemma above.
- Let
.
- Let
and
. If
and
are positive, then store these values, along with
.
- Output the values of
and
that correspond to the largest value of
for which these values were positive.
This is the solution which we submitted. It was accepted, and ran in time, but we can make a few improvements. When calculating the integers and
such that
, for example, it is not necessary for the recursion to run to the base case. If
are the required integers for
(which we have already computed), then the integers for the pair
are
.
It is also possible to find the required integers and
explicitly. Cassini’s Identity tells us that
, so that one possible solution is
and
if
is even, and
and
if
is odd.
We can prove Cassini’s Identity directly using induction, of course, but could also use the fact that if
then
This can be proven using induction. (There’s no avoiding it) If we accept that this identity is true, then Cassini’s Identity follows by noting that
This matrix representation of the Fibonacci numbers also allows us to prove other identities relating to the Fibonacci numbers. For example
gives us that
and so
.
We could use this to prove the claim from earlier that . The key idea is to show that
. Calculating the greatest common divisor of two Fibonacci numbers then becomes equivalent to applying Euclid’s Algorithm to their indices in the sequence. The proof makes use of the addition formula obtained above, and the fact that
which we also made use of earlier. Given these results, one obtains
, where the last equality holds because
.
There is a wealth of other identities which can be discovered about the Fibonacci numbers, but they become increasingly less relevant to the SBITC problem. I will not present any further properties of the numbers here, but I do encourage you to experiment on your own and to see what you can discover.
Leave a Reply