Solutions for problems "A" in September, 2000
In this page only the sketch of the solutions are published;
in some cases only the final results. To achieve the maximum score in the
competition more detailed solutions needed.
A. 242. 2001 points are given in a 5x5x10 rectangular
box. Prove that there can be found two points among them whose distance is less
Solution. Put a sphere of radius 0.35 around each point. The sum of
volumes of the spheres is . Offsetting the
faces of the box by 0.35, the augmented box contains all the spheres. The
volume of this augmented box is 5.7x5.7x10.7347.6 which is smaller than the sum of volumes of all spheres.
Thus, the interiors of the spheres are cannot be pairwise disjoint. But, if two
spheres have a common interior point, their centers are closer than 0.7.
A. 243. Determine all pairs of prime numbers p,q which
for some integer
Proposed by: E. Fried, Budapest
Solution. Subtracting 1 and multiplying by (p-1) we obtain
If qpn-1 then the factors on the left hand side are
greater than the factors on the right hand side, respectively; thus qpn. Because q is a prime but pn is not, this implies qpn+1.
One of the factors of the left hand side is divisible by the prime q.
By the last inequality, this is possible only if q=pn+1. Substituting this,
p(pn-1)=(p-1)(pn+2), thus pn-3p+2=0.
Then p|2, p=2, n=2, finally q=pn+1=5.
A. 244. A sequence of numbers is called of Fibonacci-type if
each term, after the first two, is the sum of the previous two. Prove that the
set of positive integers can be partitioned into the disjoint union of infinite
Proposed by: B. Énekes, Tolna
Solution 1. We define a funcion f: NN; this function will map from any positive integer to the next
element of the corresponding Fibonacci-type sequence.
Let f(1)=2. If f(1), ..., f(n-1) are already
defined, then check whether n is one of the defined values of the
function. If n=f(m) for some m, then take the
smallest such m and let f(n)=n+m. If
n is not a value, then let f(n)=f(n-1)+1.
The first values of this function are:
For each positive integer n, which is not a value of f, take
the sequence n, f(n), f(f(n)),
... . These sequences are Fibonacci-type, because by the definition of
f, for all x,
First we prove that for all n f(n)>n. By
induction, if n=f(m), then
f(n)=n+m>n. If nf(m) for any m, then
Now we prove that f is strictly increasing. This has been seen for
n<10. If nf(m) for
any m, then
n=f(m), then by the previous result m<n,
and only one such m can exist. Let k=f(m-1); of
course k<n. The numbers k+1, k+2, ..., n-1
are between the values f(m-1)=k and
f(m)=n . Thus
Also in this case we have f(n)>f(n-1).
By these properties the sequences cover all the positive integers and they
are pairwise disjoint.
Solution 2. Similarly to the previous solution, we define a function
which is strictly increasing and satisfies
Let , the positive root of the equation
q2=q+1. For an arbitrary positive integer n let
f(n) be the closest integer to qn.
The function is strictly increasing, because the difference between
qn and q(n+1) is q>1, thus the closest integer to
q(n+1) is greater than the closest integer to qn.
Finally, for all n we have
Solution 3 (by A. Zsbán and P. Csívári). It is
well-known, that any positive integer can uniformly be written as the sum of
different Fibonacci numbers such that no neighboring Fibonacci numbers are
used, for example, 17=1+3+13. Consider a positive integer, for which the
Fibonacci number 1 is one of the terms. Shifting in such a way that each term
is replaced by the next element of the Fibonacci sequence, another number is
obtained, repeating this step we obtain a Fibonacci-type sequence:
Doing this construction for any possible number, we obtain infinitely many
Fibonacci-type sequences. Each positive integer n is contained by a
single sequence, because the first element of the corresponding sequence can be
determined by shifting back the terms of n; for example, the number
100=3+8+89 is contained by the sequence beginning with 1+2+34=37.
1, 2, 3, 5, 8, 13, 21, ...