First, we will prove that this test works for divisibility by 19.

 

We can write the number we are testing as , where y is the units digit and x is the number represented by the other digits.

 

Now, if this number is divisible by 19, then if we multiply it by 2, getting , it will still be divisible by 19. 

If it is not, then 20x + 2y will not be either.

 

Then, if this number is divisible by 19, we can subtract 19x, getting , and still have a number divisible by 19. 

 

If this number is divisible by 19, our original number is also. 

If it is not, neither is our original. 

 

We can repeat this process until we get a number small enough to easily determine if it is divisible by 19 or not, such as a number less than or equal to 19.

 

Now, in the case of 29, we take the units digit of our original number, triple it and add it to the truncated number. 

 

We can then repeat the process until we get a number less than or equal to 29. 

 

If the number is 29, the original number is divisible by 29. 

If the number is not 29, than neither is the original. 

 

We are taking , (y is the units digit and x is the number represented by the other digits) which will be divisible by 29 if and only if  is. 

 will be divisible by 29 if and only if , our original number, is.

USAMTS Problem 2/2/12 

 

Compute 17761492!(mod 2000) ; i.e., the remainder when 17761492! is divided by 2000.  (As usual, the exclamation point denotes factorial.)

 

Doing all calculations in (mod 2000), we get

17761 ≡ 1776

17762 ≡ 3154176 ≡ 176

17763 ≡ 1776  176 ≡ 312576 ≡ 576

17764 ≡ 1776  576 ≡ 1022976 ≡ 976

17765 ≡ 1776  976 ≡ 1733376 ≡ 1376

17766 ≡ 1776  1376 ≡ 2443776 ≡ 1776

…

 

We see that the pattern repeats with a period of 5. 

 

We can easily show that 13762 ≡ 1893376 ≡ 1376 (mod 2000)

and thus 13763 ≡ 1376 (mod 2000)

or 1376n ≡ 1376 (mod 2000)

 

This means that if I take a power of 1776 that is divisible by 5, the result will be 1376 (mod 2000).

 

So, since 1492! ≡ 1 2  3  4  5  …, it is a multiple of 5.

 

Therefore, 17761492! ≡ 1376 (mod 2000)

 

The answer is 1376.

 

[Note: One can see that 1376 ≡  0  (mod 16) and  1  (mod 125), so any power of this n would remain 0  (mod 16) and  1  (mod 125).]

USAMTS Problem 3/2/12 

 

Given the arithmetic progression of integers,

308, 973, 1638, 2303, 2968, 3633, 4298,

determine the unique geometric progression of integers,

b1, b2, b3, b4, b5, b6

so that

308 < b1 < 973 < b2 < 1638 < b3 < 2303 < b4 < 2968 < b5 < 3633 < b6 < 4298 .

 

 

Given:

           (Because it is a geometric progression.)

 

Let   ,    where p and q are positive integers and are prime to each other.

Now, , so  

Since  is divisible by q5,              b1  p5     is also divisible by q5.

Since q and p have no common factors, b1 is divisible by q5

 

So, 

b1 = aq5     (where a is an integer, and a > 1).

 

Now our numbers b1, b2, … , b6 can be written as

aq5,  apq4,  ap2q3, ap3q2, ap4q, ap5

 

Since    45 = 1024

and       aq5 < 973

=> q < 4

or  q < 3           (1)

Also,  > 1 so p > q    (2)

 

Also,  = r4 < (4297/974)

 > (3634/1637)

So r < (4297/974)1/4 < 1.45

and r > (3634/1637)1/4 > 1.22

 

So 1.22 <  < 1.45

So if q = 3, then p = 4

If q = 2, then there are no possible values for p

 

The only possible values are  p =4, q = 3 and r =  

 

b1 = a  35 = 243a

So 308 < 243a < 973

1.27 < a < 4.01

or  2 < a < 4  --(3)

 

 

Also, ap5 > 3633

a  45 > 3633

a > 3.5

Thus, this and (3) give   a = 4

 

Thus,

b1 = 972, b2 = 1296, b3 = 1728, b4 = 2304, b5 = 3072, b6 = 4096

USAMTS Problem 4/2/12 

 

Prove that every polyhedron has two vertices at which the same number of edges meet.

 

Let the polyhedron have    n   vertices.

 

Now, the minimum number of edges that can meet at a vertex is   3.

The maximum number of edges that can meet at a vertex is      n  1

 

Now let us assume that we have a pigeon sitting on each vertex of our polyhedron (We assume that these pigeons can count and read.), and we have pigeonholes marked 3, 4, 5, … , n  1.

 

The pigeons count the number of edges that meet on their vertex, and fly to the pigeonhole with the same number. 

 

Now, since we have   n   pigeons and only   n  3   pigeonholes, there must be at least one pigeonhole with more than one occupant. 

 

The vertices from where these pigeon roommates originally flew from have the same number of edges meeting,

 

Thus, there are at least two vertices that have the same number of edges meeting.

 

(The argument is still valid even if we do not have pigeons that can count and read <smile>!)  


USAMTS Problem 5/2/12 

 

In ΔABC, segments PQ, RS, and TU are parallel

to sides AB, BC, and CA, respectively, and intersect

at the points X, Y, and Z, as shown in the figure

on the right.  Determine the area of ΔABC if

each of the segments PQ, RS, and TU                                              1

bisects (halves) the area of ΔABC, and

if the area of ΔXYZ is one unit.  Your

answer should be in the form

, where a and b are positive

integers.

 

Let AB = c, AC = b, and XY = z.

 

First, we will prove that .

 since  

and  is common to both triangles

 

So,  

 

Now,  since  and  since  

Also,  since  and  

 

Thus,  

 

The area of two similar triangles is proportion to the square of the ratio of the sides.

(This is proven on p. 556  of Modern School Mathematics: GEOMETRY by Jurgensen, Donnelly, and Dolciani.)

 

It is given that the area of ΔABC is twice the area of ΔPQC, so PC = . 

 

Since ΔABC ~ ΔPQC, we can set up a proportion to find PQ in terms of c:  . 

 

Quadrilateral AUXP is a parallelogram, so AU = PX = .

 

Now, we can find z:

.

Now,  .

 

W =  

 

So, the area W of ΔABC is .