USAMTS Problem 1/4/12

Determine all positive integers with the property that they are one more than the sum of the squares of their digits in base 10

No single digit numbers can fit these criteria because that would mean, for a one-digit number n,

n = n² + 1

n = (1 + √(-3))/2

which is not a real number, let alone a positive integer!

We now test all two-digit numbers written 10x+y, where x and y are non negative integers (and are less than 10)

All numbers that work will be solutions for

x² + y² + 1 = 10x + y

or x² 10x + y² y + 1 = 0

Solving for x, we get

x = (10 + √(100 4(y² y + 1)))/2

= 5 + √(25 y² + y 1)

= 5 + √(24 y(y 1))

= 5 + D where D = √(24 y(y 1))

Trying y = 0, 1, 2, 3, … 9, we find that if y > 5, (24 y(y 1)) becomes negative and there are no real solutions for x. Thus y<6.

Trying 0, 1, 2, 3, 4, and 5, we find that the only integer solution is y = 5, and we get D = 2

This gives x = 5 + 2,

or x = 3 or 7.

35 and 75 are the only two-digit answers.

We will now prove that there are no other solutions.

Let N be the number and S be the sum of the squares of its digits plus one.

When N is 999, the largest possible three digit number, S = 244. This means that we need only test up to 244, because for any number above that S will be less than N.

Now since the first digit is either 1 or 2, S is less than (4 + 81 + 81 + 1), or 167. Thus the first digit can only be 1.

Now let the 3-digit number be 100 + 10x + y.

Then,

1 + x² + y² + 1 = 100 + 10x + y

or x² 10x + y² y 98 = 0

Again, solving for x gives

x = (10 + √(100 4(y² y 98)))/2

= 5 + √(25 y² + y + 98)

= 5 + √(123 y(y 1)

= 5 + D where D² = 123 y(y 1)

Now the smallest possible value of D² is when y = 9, and in this case,

D > 7.

But if D > 7, there are no valid values for x , and hence there are no solutions.

(Note: x is non negative and less than 10)

Now, if we increase the number of digits by 1, we add at most 81 to S, but we add at least 1000 to N, and thus we can never have S and N equal. Thus there are no more solutions.

35 and 75 are the only solutions.

USAMTS Problem 2/4/12

Prove that if n is an odd positive integer, then N = 2269ⁿ +1779ⁿ +

1730ⁿ 1776ⁿ is an integer multiple of 2001.

The prime factors of 2001 are 3, 23, and 29, or

2001 = 3 × 23 × 29

In modulo 3:

2269 ≡ 1

1779 ≡ 0

1730 ≡ 2

1776 ≡ 0

So,

N ≡ 1ⁿ + 0ⁿ + 2ⁿ 0ⁿ

≡ 1ⁿ + (-1)ⁿ

Now, if n is an odd positive integer, then a negative number raised to n will be negative, or (-1)ⁿ = -1ⁿ.

N ≡ 1ⁿ 1ⁿ ≡ 0

In modulo 23, similarly

2269 ≡ 15 ≡ (-8)

1779 ≡ 8

1730 ≡ 5

1776 ≡ 5

So,

N ≡ 15ⁿ + 8ⁿ + 5ⁿ 5ⁿ

≡ (-8)ⁿ + 8ⁿ + 5ⁿ 5ⁿ

≡ 8ⁿ 8ⁿ + 5ⁿ 5ⁿ

N ≡ 0 (mod 23)

Again, in modulo 29:

2269 ≡ 7

1779 ≡ 10

1730 ≡ 19 ≡ (-10)

1776 ≡ 7

So,

N ≡ 7ⁿ + 10ⁿ + 19ⁿ 7ⁿ

≡ 7ⁿ + 10ⁿ + (-10)ⁿ 7ⁿ

≡ 7ⁿ 7ⁿ + 10ⁿ 10ⁿ

N ≡ 0 (mod 29)

So, N is divisible by 3, 21, and 29, thus N is divisible by 2001.

USAMTS Problem 5/4/12

Hexagon RSTUVW is constructed by starting with a right triangle of legs measuring p and q, constructing squares outwardly on the sides of this triangle, and then connecting the outer vertices of the squares, as shown in the figure below.

Given that p and q are integers with p > q, and that the area of RSTUVW is 1922, determine p and q

We label the figure as shown above. We will determine the area of RSTUVW in terms of p and q.

Triangles ABC and ARW are congruent because corresponding legs are congruent, and both triangles are right. Thus, they have the same areas.

To find the area of ΔUVC, we will draw a line parallel to VC through U. We will draw a perpendicular to this line through C, and call the point of intersection X, forming the right triangle CXV with the same base and height (and, therefore, the same area) as ΔVCU.

ABC measures 90 mACB because CAB is a right angle. XCU also measures 90 mACB because UCB measures 90 and C lies on AX. Thus, XCU is congruent to ABC. Also, UC is congruent to CB because they are sides of the same square. So, by HA, ΔABC is congruent to ΔXCU, and thus the base height of ΔVCX and ΔVCU are equal respectively, and thus they have the same area as ΔABC.

Using the same procedure, we can find the area of ΔTBS by drawing a parallel to BS through T and a perpendicular to this line through B. We will call the intersection of these two lines Y. Using the same method as above, we find that TBY is congruent to BCA, and using HA, we can say that ΔTBS has the same area as ΔABC.

The area of ΔABC is (pq)/2 and since there are four triangles with this area, the area of all the triangular regions of RSTUVW is 2pq.

The area of square ABSR is p², the area of WRCV is q², and the area of square CBTU is p² + q² because ΔABC is a right triangle.

The area of RSTUVW in terms of p and q is

2pq + 2(p²+ q²)

This quantity is given as equal to 1922, so

2pq + 2(p² + q²) = 1922

or p² + pq + q² = 961

As we take p > q,

961 = p² + pq + q² > q² + q(q) + q² = 3q²,

or q < √(961/3) < 17

Solving for p, we get

p² + pq + q² 961 = 0

p = (-q + √(q² 4(q² 961))/2

Since (p + q) is positive, we need only consider the positive sign on the radical.

p = (-q + √(3844 3q²))/2

or p = (-q + √(D))/2, where D = √(3844 3q²)

Now, since 17 is a small number, we can use brute force, and find which values of integer q give an integer value for D.

q	D²	Comments
1	3841	Not a perfect square
2	3832	Not a perfect square
3	3817	Not a perfect square
4	3796	Not a perfect square
5	3769	Not a perfect square
6	3736	Not a perfect square
7	3697	Not a perfect square
8	3652	Not a perfect square
9	3601	Not a perfect square
10	3544	Not a perfect square
11	3481	= 59²
12	3412	Not a perfect square
13	3337	Not a perfect square
14	3256	Not a perfect square
15	3169	Not a perfect square
16	3076	Not a perfect square
17	2977	Not a perfect square

Thus, the only integer solution for q is 11, and this gives

p = (-11 + 59)/2

p = 24

p = 24, q = 11