Solutions for October Problems
Comment on problems 339 and 342. In both these problems,
a condition was left out and made each of them trivial. Accordingly,
problem 339 is marked out of 4 and problem 342 out of 3, for the
basic solution. However, additional marks were provided for students
who recognized that the problems might have been misstated and
provided work that led to the intended solutions. While I try to
make sure that the problems are correct, and certainly on contests,
the problems are generally gone over very carefully, mistakes do
occur. If on a contest, you feel that a mistake has been made in
formulating a problem, then you should state clearly a nontrivial
version of the problem and solve that. In the solutions below,
the corrected version of the problem is given.

339.

Let a, b, c be integers with abc ¹ 0,
and u, v, w be integers, not all zero, for which
au^{2} + bv^{2} + cw^{2} = 0 . 

Let r be any rational number. Prove that the equation
ax^{2} + by^{2} + cz^{2} = r 

is solvable for rational values of x, y, z.
Solution 1. Suppose, wolog, that u
¹ 0.
Try a solution of the form
(x, y, z) = (u(1 + t), vt, wt) . 

Then au
^{2} + 2au
^{2}t + au
^{2}t
^{2} + b
^{2}v
^{2}t
^{2} + cw
^{2}t
^{2} = r
implies that 2au
^{2}t = r
 au
^{2}, from which we find the value
t = (r
 au
^{2})/((2au
^{2}). Since a, b, c, u, v, w, r, t are all
rational, so is the trial solution.
Solution 2. [R. Peng] Suppose that r = p/q. Then the
equation with r on the right is satisfied by
(x, y, z) = 
æ è


p
2

+ 
1
2qa

, 
æ è


p
2

 
1
2qa


ö ø


æ è


v
u


ö ø

, 
æ è


p
2

 
1
2qa


ö ø


æ è


w
u


ö ø


ö ø

. 

Comment. If not all a, b, c are zero, then it is trivial
to prove that the equation with r on the right has a solution;
the only rôle that the equation with 0 on the right plays is to
ensure that a, b, c do not all have the same sign. However,
some made quite heavy weather of this. The hypothesis that integers
are involved should alert you to the fact that some special character
of the solution is needed. It is unreasonable to ask that the
solution be in integers, but one could seek out rational solutions.

340.

The lock on a safe consists of three wheels, each
of which may be set in eight different positions. Because of a
defect in the safe mechanism, the door will open if any two of
the three wheels is in the correct position. What is the smallest
number of combinations which must be tried by someone not knowing
the correct combination to guarantee opening the safe?
Solution. The smallest number of combinations that will
guarantee success is 32. Denote the eight positions of each
whell by the digits 0, 1, 2, 3, 4, 5, 6, 7, so that each combination
can be represented by an ordered triple (a, b, c) of three digits.
We show that a suitably selected set of 32 combinations will do the
job. Let A = { (a, b, c) : 0
£ a, b, c
£ 3
and a + b + c
º 0 (
mod ) 4 } and
B = { (u, v, w) : 4
£ u, v, w
£ 7
and u + v + w
º 0 (
mod ) 4 }. Any entry in the triples of A and
B is uniquely determined by the other two, and any ordered pair
is a possibility for these two. Thus, each of A and B contains
exactly 16 members. If (p, q, r) is any combination, then either
two of p, q, r belong to the set { 0, 1, 2, 3 } and agree with
corresponding entries in a combination in A, or two belong to
{ 4, 5, 6, 7 } and agree with corresponding entries in a combination
in B.
We now show that at least 32 combinations are needed. Suppose, if
possible, that a set S of combinations has three members
whose first entry is 0: (0, a, b), (0, c, d), (0, e, f).
There will be twentyfive combinations of the form (0, y, z)
with y ¹ a, c, e, z ¹ b, d, f, that will not match
in two entries any of these three. To cover such combinations, we
will need at least 25 distinct combinations of the form (x, y, z)
with 1 £ x £ 7. None of the 28 combinations identified
so far match the 7 ×6 = 42 combinations of the form
(u, v, w), where v Î { a, c, e }, w Î {b, d, f },
(v, w) ¹ (a, b), (c, d), (e, f). Any combination of the
form (u, v, t) or (u, t, w) can cover at most three of these
and of the form (t, v, w) at most 7. Thus, S will need
at least 37 = 3 + 25 + (42/7) members to cover all the combinations.
A similar argument obtains if there are only three members in S
with any other given entry. If there are only one or two members
in S with a given entry, say first entry 0, then at least 36
combinations would be needed to cover all the entries with
first entry 0 and the other entries differing from the entries of
these two elements of S.
Thus, a set of combinations will work only if there are at least
four combinations with a specific digit in each entry, in particular
at least four whose first entry is k for each of k = 0, ¼, 7.
Thus, at least 32 entries are needed.
Comment. Some solvers formulated the problem in terms of the
minimum number of rooks (castles) required to occupy or threaten
every cell of a solid 8 ×8 ×8 chessboard.

341.

Let s, r, R respectively specify the semiperimeter,
inradius and circumradius of a triangle ABC.


(a) Determine a necessary and sufficient condition on s, r, R
that the sides a, b, c of the triangle are in arithmetic
progression.


(b) Determine a necessary and sufficient condition on s, r, R
that the sides a, b, c of the triangle are in geometric progression.
Comment. In the solutions, we will use the following facts, the
establishment of which is left up to the reader:
ab + bc + ca = s^{2} + 4Rr + r^{2} 

An efficient way to get the second of these is to note that
the square of the area is given by
r
^{2}s
^{2} = s(s
a)(s
b)(s
c) from which
r^{2}s = s^{3}  (a + b + c)s^{2} + (ab + bc + ca)s  abc = s^{3}  2s^{3} + (ab + bc + ca)s  4Rrs . 

Solution 1. (a) a, b, c are in arithmetic progression if and
only if


= (2a  b  c)(2b  c  a)(2c  a  b) 
 
 
= (2s  3a)(2s  3b)(2s  3c) 
 
 
= 8s^{3}  12s^{2}(a + b + c) + 18s(ab + bc + ca)  27abc 
 
 
= 2s^{3}  36Rrs + 18r^{2}s . 

Since s
¹ 0, the necessary and sufficient
condition that the three sides be in
arithmetic progression is that s
^{2} + 9r
^{2} = 18Rr.
(b) First, note that


= (a + b + c)^{3}  3(a + b + c)(ab + bc + ca) + 3abc 
 
 
= 2s^{3}  12Rrs  6r^{2}s , 

and

a^{3} b^{3} + b^{3} c^{3} + c^{3} a^{3} 

= (ab + bc + ca)^{3}  3abc(a + b + c)(ab + bc + ca) + 3(abc)^{2} 
 
 
= (s^{2} + 4Rr + r^{2})^{3}  24Rrs^{4}  48R^{2}r^{2}s^{2}  24Rr^{3}s^{2} . 

a, b, c are in geometric progression if and only if


= (a^{2}  bc)(b^{2}  ca)(c^{2}  ab) 
 
 
= abc(a^{3} + b^{3} + c^{3})  (a^{3}b^{3} + b^{3}c^{3} + c^{3}a^{3}) 
 
 
= 32Rrs^{4}  (s^{2} + 4Rr + r^{2})^{3} , 

The necessary and sufficient condition is that
(s^{2} + 4Rr + r^{2})^{3} = 32Rrs^{4} . 

Solution 2. The three sides of the triangle are the
three real roots of the cubic equation
x^{3}  2sx^{2} + (s^{2} + r^{2} + 4Rr)x  4Rrs = 0 . 

The three sides are in arithmetic progression if and only if
one of them is equal to 2s/r and are in geometric progression
if and only if one of them is equal to their geometric mean
^{3 }Ö{4Rrs}.
(a) The condition is that 2s/3 satisfies the cubic equation:
0 = 8s^{3}  6s(4s^{2}) + 9(s^{2} + r^{2} + 4Rr)(2s)  108Rrs = 2s(s^{2} + 9r^{2}  18Rr) . 

(b) The condition is that ^{3 }Ö{4Rrs} satisfies the
cubic equation:
2s(4Rrs)^{1/3} = s^{2} + 4Rr + r^{2} or 32Rrs^{3} = (s^{2} + 4Rr + r^{2})^{3}.
Solution 3. [B.H. Deng] Assume that b lies between a and
c, inclusive. (a) The three sides are in arithmetic progression if and
only if b = ^{2}/_{3}s or a + c = 2b. Since 4Rrs = abc,
this is equivalent to 6Rr = ac, which in turn is equivalent to
r^{2} + s^{2} + 4Rr = (a + c)b + ac = 2b^{2} + ac = (8/9)s^{2} + 6Rr 

or s
^{2} + 9r
^{2} = 18Rr.
(b) The three sides are in geometric progression if and only if
b^{3} = abc = 4Rrs and ac = b^{2}. This holds if and only if
r^{2} + s^{2} + 4Rr = (a + c)b + ac = (2s  b)b + ac = 2s  3
Ö

4Rrs

 b^{2} + ac = 2s  3
Ö

4Rrs



or (r
^{2} + s
^{2} + 4Rr)
^{3} = 32Rrs
^{4}.

342.

Prove that there are infinitely many solutions in
positive integers, whose greatest common divisor is equal to
1, of the system
Solution 1. Suppose that a, b, c are in arithmetic
progression, so that c = 2b
 a and x + y = 3b. Then
x^{2}  xy + y^{2} = 
a^{3} + b^{3} + c^{3}
a + b + c

= 3b^{2}  4ab + 2a^{2} 

so that
3xy = (x + y)^{2}  (x^{2}  xy + y^{2}) = 6b^{2} + 4ab  2a^{2} 

and
xy = 2b^{2} + 
2a(2b  a)
3

. 

Therefore
(y  x)^{2} = (x + y)^{2}  4xy = b^{2}  
8a(2b  a)
3

= 
(3b  8a)^{2}  40a^{2}
9

. 

Let p = 3b  8a, q = 2a. We can get solutions by solving
p^{2}  10q^{2} = 9. Three solutions are (p, q) = (3, 0),(7, 2), (13, 4). The fundamental solution of u^{2}  10v^{2} = 1
is (u, v) = (19, 6). So from any solution (p, q) = (r, s)
of p^{2}  10q^{2} = 9, we get another
(p, q) = (19r + 60s, 6r + 19s). For these to yield solutions
(a, b, c; x, y) of the original system, we require q to be
even and p + 4q to be divisible by 3. Since 19r + 60s º r (mod 3) and 6r + 19s º s (mod 2), if (p, q) = (r, s)
has these properties, then so also does (p, q) = (19r + 60s,6r + 19s). Starting with (r, s), we can define integers
p and q, and then solve the equations
x + y = 3b, y  x = 1. Since p and so b are odd, these
equations have integer solutions. Here are some examples:


(3, 0; 0, 1, 2; 1, 2), (57, 18; 9, 43, 77; 64, 65), 
 
 
(7, 2; 1, 5, 9; 7, 8), (253, 80; 40, 191, 342; 286, 287) . 

Solution 2. [D. Dziabenko] Let a = 3d.
c = 2b  3d, so that x + y = 3b and a, b, c are in arithmetic
progression. Then


= 27d^{3} + b^{3} + 8b^{3}  36b^{2}d + 54bd^{2}  27d^{3} 
 
 
= 9b^{3}  36b^{2}d + 54bd^{2} = 9b(b^{2}  4b^{2}d + 6d^{2}) , 

whence x
^{2}  xy + y
^{2} = 3b
^{2}  12bd + 18d
^{2}. Therefore
3xy = (x + y)^{2}  (a^{2}  xy + y^{2}) = 6b^{2} + 12bd  18d^{2} 

so that xy = 2b
^{2} + 4bd
 6d
^{2} and
(x  y)^{2} = (x + y)^{2}  4xy = b^{2}  16bd + 24d^{2} = (b  8d)^{2}  40d^{2} . 

Let b
 8d = p
^{2} + 10q
^{2} and d = pq. Then
x  y =  Ö

p^{4}  20p^{2}q^{2} + 100q^{4}

= p^{2}  10q^{2} . 

Solving this, we find that
(a, b, c; x, y) = (3pq, p^{2} + 8pq + 10q^{2}, 2p^{2} + 13pq + 20q^{2};2p^{2} + 12pq + 10q^{2}, p^{2} + 12pq + 20q^{2}) . 

Some numerical examples are
(a, b, c; p, q) = (3, 19, 35;24, 33), (6, 30, 54; 42, 48), (6, 57, 108; 66, 105) . 

Any common divisor of a and b must divide 3pq and
p
^{2} + 10q
^{2}, and so must divide both p and q. [Justify this;
you need to be a little careful.] We can get the solutions we want
by arranging that the p and q are coprime.
Solution 3. [F. Barekat] Let m = a + b + c = x + y and
n = a^{3} + b^{3} + c^{3} = x^{3} + y^{3}. Then
3xy = m^{2}  
n
m

= 
m^{3}  n
m



and


= 
x^{3} + y^{3}
x + y

 xy = 
4n  m^{3}
3n


 
 
= 
4(a^{3} + b^{3} + c^{3})  (a + b + c)^{3}
3(a + b + c)


 
 
= (c  a  b)^{2}  
4ab(a + b)
a + b + c

. 

Select a, b, c so that

4ab(a + b)
a + b + c

= 2(c  a  b)  1 . 

so that x
 y = c
 a
 b
 1. Then we can solve for rational
values of x and y. If we can do this x + y = a + b + c
and x
 y = c
 a
 b
 1. Note that, these two numbers have
different parity, so we will obtain fractional values of x and
y, whose denominators are 2. However, the equations to be
solved are homogeneous, so we can get integral solutions by
doubling: (2a, 2b, 2c; 2x, 2y).
Let c = u(a + b). Then
4ab = 2(u1)(u+1)(a + b)  (u + 1) . 

Let u = 4v + 3, Then we get
ab = 4(v + 1)(2v + 1)(a + b)  4(v + 1) , 

from which
[a  4(v + 1)(2v + 1)][b  4(v + 1)(2v + 1)] = (v + 1)[16(v + 1)(2v + 1)^{2}  1] . 

We use various factorizations of the right side and this equation
to determine integer values of a and b, from which the
remaining variables c, x and y can be determined.
For example, v = 0 yields the equation (a  4)(b  4) = 15
from which we get the possibilities
(a, b, c) = (5, 19, 72), (7, 9, 48) . 

Doubling to clear fractions, yields the solutions
(a, b, c; x, y) = (10, 38, 144; 49, 143), (14, 18, 96; 33, 95) . 

Additional solutions come from v = 1:
(a, b, c; x, y) = (76, 130, 1442; 207, 1441),(50, 1196, 8722; 1247, 8721) . 

Solution 4. [D. Rhee] An infinite set of solutions is
given by the formula


= (2, n^{2} + 3n, n^{2} + 5n + 4; n^{2} + 4n + 2, n^{2} + 4n + 4) 
 
 
= (2, n(n + 3), (n+1)(n+4); (n+2)^{2}  2, (n+2)^{2}) . 

Examples are (a, b, c; x, y) = (2, 4, 10; 7, 9),(2, 10, 18; 14, 16), (2, 18, 28; 23, 25).
Comment. M. Fatehi gave the solution
(a, b, c; x, y) = (5, 6, 22; 12, 21) . 


343.

A sequence { a_{n} } of integers is defined by
a_{0} = 0 , a_{1} = 1 , a_{n} = 2a_{n1} + a_{n2} 

for n > 1. Prove that, for each nonnegative integer k,
2^{k} divides a_{n} if and only if 2^{k} divides n.
Solution 1. Let m and n be two nonnegative integers.
Then a
_{m+n} = a
_{m}a
_{n+1} + a
_{m1}a
_{n} = a
_{m+1}a
_{n} + a
_{m}a
_{n1}.
This can be checked for small values of m and n and established
by induction. The induction step is


= 2a_{m+n} + a_{m+n1} = 2(a_{m}a_{n+1} + a_{m1}a_{n}) +(a_{m}a_{n} + a_{m1}a_{n1} 
 
 
= a_{m} (2a_{n+1} + a_{n}) + a_{m1}(2a_{n} + a_{n1}) = a_{m} a_{n+2} + a_{m1}a_{n+1} . 

In particular, for each integer n,
a_{2n} = a_{n} (a_{n1} + a_{n+1}) . 

It is straightforward to show by induction from the recursion that
a_{n} is odd whenever n is odd and even whenever n is even.
Suppose now that n is even. Then a_{n+1} = 2a_{n} + a_{n1} º a_{n1} º a_{1} = 1 (mod 4), so that
a_{n1} + a_{n+1} = 2b_{n} for some odd number b_{n}. Hence
a_{2n} = 2a_{n}b_{n}. For k = 0, we have that 2^{k} a_{n}
if and only if 2^{k} n. Suppose that this has been established
for k = r.
Suppose that n = 2^{r+1}m for some integer m. Then n/2 is
divisible by 2^{r}, and therefore so is a_{n/2}. Hence
a_{n} = 2a_{n/2}b_{n/2} is divisible by 2^{r+1}. On the other
hand, suppose that n is not divisible by 2^{r+1}. If
n is not divisible by 2^{r}, then a_{n} is not so divisible by
the induction hypothesis, and so not divisible by 2^{r+1}.
On the other hand, if n = 2^{r}c, with c odd, then
a_{n} is divisible by 2^{r}. But n/2 = 2^{r1}c, so a_{n/2}
is not divisible by 2^{r}. Hence
a_{n} = 2a_{n/2}b_{n/2} is not divisible by 2^{r+1}.
The result follows.
Solution 2. For convenience, imagine that the sequence is
continued backwards using the recursion a_{n2} = a_{n}  2a_{n1}
for all integer values of the index n. We have for every integer
n, a_{n+1} = 2a_{n} + a_{n1} Þ 2a_{n+1} = 4a_{n} + 2a_{n1}Þ a_{n+2}  a_{n} = 4a_{n} + a_{n}  a_{n2} Þa_{n+2} = 6a_{n}  a_{n2}. Suppose, for some positive integer r,
we have established that, for every integer n,
a_{n + 2r} = b_{r} a_{n}  a_{n2r} 

where b
^{r} º 2 (mod 4). This is true for r = 1 with b
_{1} = 6.
Then
b_{r} a_{n + 2r} = b_{r}^{2} a_{n}  b_{r} a_{n  2r} 

Þ a_{n + 2r+1} + a_{n} = b_{r}^{2} a_{n}  (a_{n} + a_{n2r+1}) 

Þ a_{n + 2r} = b^{r+1}a_{n}  a_{n  2r+1} , 

where b
_{r+1} = b
_{2}^{2}  2
º 2 (mod 4).
Observe that, since a_{n+1} º a_{n1} (mod 2) and a_{0} = 0,
a_{1} = 1, a_{n} is even if and only if n is even. When n is
even, then a_{n+2} º a_{n2} (mod 4), so that a_{n} is divisible
by 4 if and only if n is.
Let m ³ 2 be a positive integer. Suppose that it has been
established for 1 £ s £ m, that 2^{s} divides a_{n} if and only
if 2^{s} divides n. Then 2^{s+1} will divide a_{n} only if
n = 2^{s} p for some integer p. Now
a_{2s} = b_{s1}a_{2s1}  a_{0} = b_{s1}a_{2s1} ; 

since 2
 b
^{s1} and 2
^{s1}  a
^{2s1}, it follows that
2
^{s}  a
_{2s}. (The notation 2
^{k}  q means that 2
^{k} is the
highest power of 2 that divides q.) Thus 2
^{s+1} does not
divide 2
^{s}.
Suppose that it has been established for 1 £ i £ p that
when n = 2^{s} i, 2^{s+1} n if and only if p is even.
We have that
a_{2s(p+1)} = b_{s} 2^{s}p  a_{2s(p1)} . 

If p is even, then b
^{s} a
_{2sp} º 0 (mod 2
^{s+1}),
so that a
_{2s(p+1)} º a
_{2}^{s}(p
1)
º 2
^{s} (mod 2
^{s+1}),
and a
_{2s(p+1)} is not a multiple of 2
^{s+1}. If p is odd,
then each term on the right side of the foregoing equation is
a multiple of 2
^{s+1}, and therefore so is a
^{2s(p+1)}.
The desired result follows by induction.
Solution 3. The characteristic equation for the recursion is
t^{2}  2t  1 = 0, with roots t = 1 ±Ö2. Solving the
recursion, we find that


= 
1
2 Ö2

[(1 + Ö2)^{n}  (1  Ö2)^{n}] 
 
 
= 
1
Ö2


é ë


¥ å
k=0


æ è

n
2k + 1

ö ø

2^{k} Ö2 
ù û


 
 
= 
¥ å
k=0


æ è

n
2k+1

ö ø

2^{k} = n + 
¥ å
k=1


æ è

n
2k + 1

ö ø

2^{k} 
 
 
= n + 
¥ å
k=1


n
2k+1


æ è

n1
2k

ö ø

2^{k} . 

(We use the convention that (i  j) = 0 when i < j.
Suppose that n = 2
^{r}s where r is a nonnegative integer and
s is odd. Since the odd number 2k + 1 divides
n ((n
1)  2k) = 2
^{r} s ((n
1)  2k), 2k + 1
must divide s ((n
1)  2k), so that 2
^{s} must divide
n ((n
1)  2k) = (n  (2k+1)). Therefore,
2
^{s+1} must divide each term (n  (2k+1)) for k
³ 1.
Therefore a
_{n} º n (mod 2
^{s}) and the desired result follows.
Comment. Y. Zhao obtained by induction that

æ ç ç
ç è

 
ö ÷ ÷
÷ ø

= 
æ ç ç
ç è

 
ö ÷ ÷
÷ ø

n



from which the matrix equation

æ ç ç
ç è

 
ö ÷ ÷
÷ ø

= 
æ ç ç
ç è

 
ö ÷ ÷
÷ ø

2



yields the equation a
_{2n} = a
_{n} (a
_{n1} + a
_{n+1}.

344.

A function f defined on the positive integers is
given by
f(1) = 1 , f(3) = 3 , f(2n) = f(n) , 

for each positive integer n. Determine, with proof, the number
of positive integers no exceeding 2004 for which f(n) = n.
Solution. Let g(n) be defined for positive integer
n by writing n to base 2 and reversing the digits. Specifically,
if n =
å_{k=0}^{r} a
_{k} 2
^{r} with each a
_{k} equal to 0 or 1
and a
_{r} = 1,
then g(n) =
å_{k=0}^{n} a
_{rk}2
^{k}. We prove that g(n) has the
properties ascribed to f(n). It is checked that g(1) = g(2) = g(3) = 1. Let n = a
_{r}2
^{r} + a
_{r1}2
^{r1} +
¼+ a
_{1}2 + a
_{0}.
Then 2n = a
_{r}2
^{r+1} +
¼+ a
_{0}2 + 0 and
g(2n) = 0·2
^{r+1} + a
_{0} 2
^{r} +
¼+ a
_{r1}2 + a
_{r} = g(n).
Since 4n + 1 = a_{r}2^{r+2} + a_{r1}2^{r+1} + ¼+ a_{1}2^{3} + a_{0}2+ 0·2 + 1,


+ g(4n+1) = (a_{0}2^{r} + a_{1}2^{r1} + ¼+ a_{r1}2 + a_{r}) +(2^{r+2} + a_{0}2^{r} + a_{1}2^{r1} + ¼+ a_{r1}2 + a_{r}) 
 
 
= 2^{r+2} + a_{0}2^{r+1} + a_{1}r^{r} + ¼+ a_{r1}2^{2} + a_{r}2 = 2(2^{r+1} + a_{0}2^{r} + a_{1}2^{r1} + ¼+ a_{r1}2 + a_{r} 
 
 
= 2g(a_{2} 2^{r+1} + a_{0} 2^{r} + a_{1} 2^{r1} + ¼+ a_{r1} 2+ a_{r}) = 2g(2n+1) . 

(This uses the fact that a2
^{i} + a2
^{i} = a2
^{i+1}.)
Since 4n + 3 = a_{r}2^{r+2} + a_{r1}2^{r+1} + ¼+ a_{1}2^{3} + a_{0}2+ 1·2 + 1,


 
 
= (a_{0}2^{r+1} + a_{1} 2^{r} + a_{2} 2^{r1} + ¼+ a_{r1}2^{2} + a_{r} 2) 
 
 
+ (2^{r+2} + 2^{r+1} + a_{0}2^{r} + a_{1}2^{r1} + ¼+ a_{r1}2 + a^{r}) 
 
 
= (2^{r+2} + a_{0}2^{r+1} + a_{1}2^{r} + ¼+ a_{r}2) + (2^{r+1} + a_{0}2^{r} + a_{1}2^{r1} + ¼+ a_{r}) 
 
 
= 2g(2n+1) + g(2n+1) = 3g(2n + 1) . 

We show by induction that f(n) = g(n) for every positive integer
n. This is true for 1 £ n £ 4. Suppose it holds for
1 £ n £ 4m. Then
f(4m + 1) = 2f(2m + 1)  f(m) = 2g(2m + 1)  g(m) = g(4m + 1) ; 

f(4m + 2) = f(2m + 1) = g(2m + 1) = g(4m + 2) ; 

f(4m + 3) = 3f(2m + 1)  2f(m) = 3g(2m + 1)  2g(m) = g(4m + 3) ; 

f(4m + 4) = f(2m + 2) = g(2m + 2) = f(4m + 4) . 

Thus we have a description of f(n).
For f(n) = n, it is necessary and sufficient that n is a
palindrome when written to base 2. We need to find the number of
palindromes between 1 and 2004 = (11111010100)_{2} inclusive.
The number of (2r1) and 2rdigit palindromes is each
2^{r1} as the first and last digits must be 1 and there are
r1 other matching pairs of digits or central digits that can
be set to either 0 or 1. The number of palindromes up to
2^{11}  1 = 2047 is 2(1 + 2 + 4 + 8 + 16) + 32 = 94. The
only palindromes between 2004 and 2048 are (11111011111)_{2}
and (11111111111)_{2}, and these should not be counted. Therefore,
there are exactly 92 palindromes, and therefor 92 solutions of
f(n) = n between 1 and 2004, inclusive.

345.

Let C be a cube with edges of length 2.
Construct a solid figure with fourteen faces by cutting off all
eight corners of C, keeping the new faces perpendicular to
the diagonals of the cuhe and keeping the newly formed faces identical.
If the faces so formed all have the same area, determine the common
area of the faces.
Solution 1. In the situation where the cuts pass through
the midpoints of the edges, yielding a cubeoctahedron with six square
and eight equilateraltriangular sides, we find that the square
faces have area 2 and the triangular faces have area
(
Ö3/4)(
Ö2) =
Ö6/4 < 2. Moving the cuts closer
to the vertices yields triangular faces of area less than 2
and octahedral faces of area greater than 2. Thus, for equal areas
of the corner and face figures, the cuts must be made a a distance
exceeding 1 from each vertex.
The corner faces of the final solid are hexagons formed by large
equilateral triangles with smaller equilateral triangles clipped off
each vertex; the other faces are squares (diamonds) in the middle
of the faces of the cube. Let the square faces have side length
x. The vertices of this face are distant 1  (x/Ö2)
from the edge of the cube, so that smaller equilateral triangles
of side Ö2(1  (x/Ö2)) = Ö2  x are clipped
off from a larger equilateral triangle of side
2(Ö2  x) + x = 2Ö2  x. The areas of the hexagonal
faces of the solid figure are each

Ö3
4

[(2Ö2  x)^{2}  3(Ö2  x)^{2}] = 
Ö3
2

+ 
xÖ6
2

 
x^{2}Ö3
2

. 

For equality, we need
x^{2} = 
Ö3
2

[1 + xÖ2  x^{2}] , 

or
(2 + Ö3)x^{2}  xÖ6  Ö3 = 0 . 

Hence
and the common area is
x^{2} = 
7 + 4Ö3

= (6 + 2Ö3 +  Ö

27 + 12Ö3

)(7  4Ö3) . 

Solution 2. Let the cut be made distant u from a vartex.
As in Solution 1, we argue that 1 < u < 2. Then the edge of the
square face of the final solid is distant u/Ö2 from the
vertex of the cube and Ö2(1  (u/2)) from the centre of
the face. Thus, the square face has side length Ö2(2  u)
and area 8  8u + 2u^{2}.
The hexagonal face of the solid consists of an equilateral triangle
of side Ö2u with three equilateral triangles of side
Ö2(u  1) clipped off. Its area is
(Ö3/2)[2u^{2} + 6u  3. For equality of area of all the faces,
we require that
2(8  8u + 2u^{2}) = Ö3(2u^{2} + 6u  3) 

or
2(2 + Ö3)u^{2}  2(8 + 3Ö3)u + (16 + 3Ö3) = 0 . 

Solving this equation and taking the root less than 2 yields that
whence
Thus, the common area is
2(2  u)^{2} = 
7 + 4Ö3

= (6 + 2Ö3 +  Ö

27 + 12Ö3

)(7 4Ö3) . 
