**Find, with proof, all pairs of two-digit positive
integers ab and cd such that all the digits a, b, c, and d are different from
one another and (ab)(cd) = (dc)(ba).**

*a*, *b*, *c*,
and *d* are decimal digits, distinct
integers greater than 0 and less than or equal to 9.

(In this equation, “*ac*” is taken to mean the

decimal
number with digits *a* and *c*, rather than

(*ac*)(*bd*)
= (*dc*)(*ba*), or the
multiplication of two numbers *a* and *c*.
Henceforth, we will denote multiplication of two digits with a “”
sign.)

(10*a* + *c*)(10*b*
+ *d*) = (10*d* + *c*)(10*b* + *a*)

So,

100*ac*
+ 10*ad*
+ 10*bc*
+ *bd*
= 100*bd*
+ 10*ad*
+ 10*bc*
+ *ac*

99*ac*
= 99*bd*,
or

*ac*
= *bd*

We can find a finite (and small)
number of solutions for *a**c* = *b**d* when *a*, *b*, *c*, and *d* are unique integers greater than 0 and less than or equal to
9.

There are only five numbers which can be factored into two four distinct decimal digits, or integers between 1 and 9, in two different ways.

6 (= 16, 23)

8 (= 18, 24)

12 (= 26, 34)

18 (= 29, 36)

24 (= 38, 46)

For each of these numbers, we can
let *a* equal any one of the four
factors, and *b* equal any one of the
factors in the pair that does not contain *a*. Thus, for each of these five numbers, there
are eight pairs {*ab*, *cd*}.
The 40 possible pairs {*ab*, *cd*} are listed on the next page, in
order of the *a**c* = *b**d* value.

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

**For ac = bd = 6:**

* *

*a* = 1: *a* = 2:

** {12, 63} {21,
36}**

** {13, 62} {26,
31}**

*a* = 6: *a* = 3:

** {62, 13} {31,
26}**

** {63, 12} {36,
21}**

** **

** **

**For ac = bd = 8:**

* *

*a* = 1: *a* = 2:

** {12, 84} {21,
48}**

** {14, 82} {28,
41}**

*a* = 8: *a* = 4:

** {82, 14} {41,
28}**

** {84, 12} {48,
21}**

** **

** **

**For ac = bd = 12:**

* *

*a* = 2: *a* = 2:

** {23, 64} {32,
46}**

** {24, 63} {36,
42}**

*a* = 6: *a* = 3:

** {63, 24} {42, 36}**

** {64, 23} {46,
32}**

** **

** **

**For ac = bd = 18:**

* *

*a* = 1: *a* = 2:

** {23, 96} {32,
69}**

** {26, 93} {39,
62}**

*a* = 6: *a* = 3:

** {93, 26} {62,
39}**

** {96, 23} {69,
32}**

** **

**For ac = bd = 24:**

* *

*a* = 1: *a* = 2:

** {34, 86} {43,
68}**

** {36, 84} {48,
63}**

*a* = 6: *a* = 3:

** {84, 36} {63,
48}**

** {86, 34} {68,
43}**

**Find the smallest positive
integer n such that the product (2004n + 1)(2008n + 1) is a perfect
square. Prove that n is as small as
possible.**

** **

The values (2004*n*
+ 1) and (2008*n* + 1) have a
difference of 4*n*. The greatest common factor of both (2004*n* + 1) and (2008*n* + 1) with 4*n* is 1. Thus, (2004*n* + 1) and (2008*n* + 1)
have no common factors.

Since these two numbers are prime to one another, and when multiplied
result in a perfect square, then they themselves must be perfect squares. So, (2004*n*
+ 1) and (2008*n* + 1) must each be
perfect squares.

The number (2008*n*
+ 1) is odd. Therefore, its square root
is also odd, and can be written as (2*p*
+ 1) for some integer *p*. So,

, or

,

502 can be factored as 2(251). Thus,

,

and since 251 is prime, either *p* or *p* + 1 must have 251
as a factor. (We do not need to worry
about 2 because either *p* or *p* + 1 will be a multiple of 2.)

So, values for *n*
for which (2008*n* +1) is a perfect
square will be of the form

,

with positive integer values for *a* for increasing multiples of 251.
For each possible value of *n*
for (2008*n* +1), we will check if that
*n* also results in a perfect square
value for (2004*n* +1)

When *a* = 1, *n* = 125 or 126

(2004(125) +1) = 250501, which is not a perfect square.

(2004(126) +1) = 252505, which is not a perfect square.

When *a* = 2, *n* = 501 or 503

(2004(501) +1) = 1004005, which is not a perfect square.

(2004(503) +1) = 1008013, which is not a perfect square.

When *a* = 3, *n* = 1128 or 1131

(2004(1128) +1) = 2260513, which is not a perfect square.

(2004(1131) +1) = 2266525, which is not a perfect square.

When *a* = 4, *n* = 2006 or 2010

(2004(2006) +1) = 4020025, which is a perfect square; it
equals 2005^{2}

** **

**Thus, 2006 is the
smallest value of n for which (2004n + 1)(2008n + 1) is a perfect square.**

We see that and ; thus

We can expect *n* =
2006 to work; in the solution for problem 4 of this round, we find that, when
we multiply two numbers with a difference of two and add one, we have a perfect
square, i.e., *k*(*k* + 2) + 1 = (*k* + 1)^{2}.

It is interesting to see that we can find another solution
for *n* from problem 4. In solving that problem, we find that when we
have

*a* = *k*(*k*
+ 1)(*k* + 2)(*k* + 3) + 1,

then *a *is a
perfect square.

Thus, another value of *n*
would be *n* = (2005)(2006)(2007).

This will be a solution, because both

(2004)(2005)(2006)(2007) + 1 and

(2005)(2006)(2007)(2008) + 1

fit the form

* *

*k*(*k* + 1)(*k* + 2)(*k* + 3) + 1,

and are thus both perfect squares.

So,

((2004)(2005)(2006)(2007) + 1)((2005)(2006)(2007)(2008) + 1)

would also be a perfect square.

**However, the smallest
value for n is 2006.**

**Pebbles
are put on the vertices of a combinatorial graph. For a vertex with two or more pebbles, a
pebbling step at that vertex removes one pebble at the vertex from the graph
entirely and moves another pebble at that vertex to a chosen adjacent
vertex. The pebbling number of a graph
is the smallest number t such that no matter how t pebbles are distributed on
the graph, the distribution would have the property that for every empty vertex
a series of pebbling steps could move a pebble to that one vertex. For example, the pebbling number of the graph
formed from the vertices and edges of a hexagon is eight. Find, with proof, the pebbling number of the
graph illustrated on the right.**

** **

Let us label the vertices on the graph as shown, and let {*n*_{1}, *n*_{2}, *n*_{3},* n*_{4},* n*_{5},* n*_{6},* n*_{7},* n*_{8},* n*_{9}}
be the number of pebbles on each vertex {1, 2, 3, 4, 5, 6, 7, 8, 9}.

The number of pebbles that can move from one vertex to an
adjacent vertex is ,
where *n* is the original number of
pebbles on that vertex and [*x*] is the
greatest integer less than or equal to *x*.

Suppose we move the pebbles from vertices 4 and 5 to vertex
2. The resulting number of pebbles on
vertex 2, *N*_{2}, will be:

So,

Similarly, if we move the pebbles from vertices 6 and 7 at
vertex 3, the resulting number of pebbles on vertex 3, *N*_{3}, will have

Thus, after these moves, if we move the pebbles from
vertices 2 and 3 to vertex 1, the resulting number of pebbles on vertex 1 *N*_{1} will be

, or

So,

If ,
then *N*_{1} > 1, or *N*_{1} __>__ 2.

Let us take 9 as the destination vertex. (Vertices {4, 5, 6, 7, 8, 9} are symmetric, so it does not matter which one of these we choose. Vertices {1, 2, 3} are symmetric as well. However, it is easy to see that, if we can reach a vertex in {4, 5, 6, 7, 8, 9}, we can also reach one of {1, 2, 3}. We have seen this in the above moves; we can move at least one pebble to vertex 1 if .)

If *N*_{1}
or *n*_{8} is greater than or
equal to 2, then we can move pebbles onto vertex 9.

So, if > 12, or if *n*_{8} > 1, we can move pebbles onto vertex 9.

In the figure below is the combinatorial graph with 13 pebbles placed upon it. It is not possible to place a pebble on vertex 9 through pebbling steps. (The vertices are labeled in italics, and the initial number of pebbles on each vertex is given in bold.)

**Thus, if n_{8} + n_{8} + n_{8}
+ n_{8} + n_{8} + n_{8}
+ n_{8} + n_{8} > 13, we can always move a pebble onto vertex
9. Furthermore, 13 pebbles is not enough
to reach every vertex for every distribution.
Thus, the pebbling number of this graph is t = 14.**

**An infinite sequence of
quadruples begins with the five quadruples (1, 3, 8, 120),
(2, 4, 12, 420), (3, 5, 16, 1008), (4, 6, 20, 1980), (5, 7, 24, 3432). Each quadruple (a, b, c, d) in this sequence
has the property that the six numbers ab + 1, ac + 1, bc + 1, ad + 1, bd + 1,
and cd + 1 are all perfect squares.
Derive a formula for the n ^{th} quadruple in the sequence and
demonstrate that the property holds for every quadruple generated by the
formula. **

We notice that *a* =
1 for the first quadruple, and increases by 1 for the following four
quadruples. We will assume that *a* = *n*
for the *n*^{th} quadruple in
this sequence.

** **

For the first five quadruples, we notice that *b* = *n*
+ 2.

We will check if this fits the described properties of the sequence:

*ab* + 1 = *n*(*n* + 2) + 1 = *n*^{2} + 2*n* + 1 = (*n* + 1)^{2}

This is a perfect square, so we will continue using these
values for *a* and *b*.

For the first five quadruples, we notice that *c* = 4(*n* + 1)

Check:

*ac* + 1 = 4*n*(*n* + 1) + 1 = 4*n*^{2} + 4*n* + 1 = (2*n* + 1)^{2}

*bc* + 1 = 4(*n*
+ 2)(*n* + 1) + 1 = 4*n*^{2} + 12*n* + 9 = (2*n* + 3)^{2}

For the first five quadruples, we notice that *d* = 2(2*n* + 1)(2*n* + 2)(2*n* + 3)

(It is easy to see this pattern, but I actually took the successive differences, and found the fourth order difference to be 96, and thus found the pattern.)

Check:

*ad* + 1 = 2*n*(2*n* + 1)(2*n* + 2)(2*n* + 3) + 1

= (4*n*^{2} + 6*n*)(4*n*^{2} + 6*n* + 2) + 1

*Let 4n ^{2} + 6n = x; we have x(x +
2) + 1, which we have shown equals (x + 1)^{2}.*

=
(4*n*^{2} + 6*n* + 1)^{2}

*bd* + 1 = 2(*n*
+ 2)(2*n* + 1)(2*n* + 2)(2*n* + 3) + 1

= 4(*n* + 1)(*n* + 2)(2*n* + 1)(2*n* + 3) + 1

= 4(2*n*^{2} + 5*n* + 2)(2*n*^{2} + 5*n* + 3) + 1

*Let 2n ^{2} + 5n + 2 = x; we have
4x(x + 1) + 1, which we have shown equals (2x + 1)^{2}.*

=
(4*n*^{2} + 10*n* + 5)^{2}

*cd* + 1 = 8(*n*
+ 1)(2*n* + 1)(2*n* + 2)(2*n* + 3) + 1

= 4(2*n* + 1)(2*n* + 2)(2*n* + 2)(2*n* + 3) + 1

= 4(4*n*^{2} + 8*n* + 3)(4*n*^{2} + 8*n* + 4) + 1

*Let 4n ^{2} + 8n + 3 = x; we again
have 4x(x + 1) + 1, which equals (2x + 1)^{2}.*

=
(8*n*^{2} + 16*n* + 7)^{2}

**The n^{th} term of (a, b,
c, d) is (n, n + 2, 4(n + 1), 2(2n + 1)(2n + 2)(2n + 3).**

**In
triangle ABC the lengths of the sides of the triangle opposite **

**to the vertices A, B, and C are known as a, b, and c,
respectively. **

**Prove there exists a constant k such that if the
medians **

**emanating from A and B are perpendicular to one **

**another, then a ^{2} + b^{2} = kc^{2}. Also find the **

**value of k.**

Let *NP* = *x*, *MP*
= *y*, and *MN* = z, as shown in the figure above.

*BN* and *AM* are medians; thus, *N* and *M* are the midpoints of *AC*
and *BC*, respectively. So,

and .

Also, triangle *NMC*
is similar to triangle *ABC* because and ,
and angle C is common. Thus,

Triangles *APN*, *BPM*, *NPM*,
and *APB* are right triangles. So,

Thus,

, or

,

But, triangle *NPM*
is a right triangle, so *x*^{2}
+ *y*^{2} = *z*^{2}.

We know that . So, , or

** **

**Thus, we can write a^{2} + b^{2} = kc^{2},
where k = 5.**

** **