USAMTS Problem 1/3/13

We will say that an rearrangement of the letters of a word has no fixed letters if, when the rearrangement is placed directly below the word, no column has the same letter repeated. For instance, the blocks of letters below show that ESARET is a rearrangement with no fixed letters of TERESA, but REASTE is not.

How many distinguishable rearrangements with no fixed letters does TERESA have? (The two E’s are considered identical.)

We can replace TERESA with 112345 because there are still six digits, with two being identical.

For a number that has no fixed digits with 112345, neither the first nor the second digit can be 1.

So, the first two digits can be any two of {2, 3, 4, 5}. There are ₄P₂ = 4 3 = 12 such permutations.

We will see how many numbers with no fixed digits with 112345 there are that begin with “23”

1	1	2	3	4	5
2	3	1	1	4	5
2	3	1	1	5	4
2	3	1	4	1	5
2	3	1	4	5	1
2	3	1	5	1	4
2	3	1	5	4	1
2	3	4	1	1	5
2	3	4	1	5	1
2	3	4	5	1	1
2	3	5	1	1	4
2	3	5	1	4	1
2	3	5	4	1	1

There are seven numbers that begin with “23” that have no fixed digits with 112345.

So the total number of required permutations is 12 7 = 84.

USAMTS Problem 2/3/13

Without computer assistance, find five different sets of three positive integers {k, m, n} such that k < m < n and .

Let us first consider all possible sets of two integers {a, b}, such that

So,

, or , or

Now, if a and b are integers, then must also be integers.

Thus, are integer factors of 7056.

So, the possible pairs are:

{2, 3258}	{21, 336}
{3, 2352}	{24, 294}
{4, 1764}	{28, 252}
{6, 1176}	{36, 196}
{7, 1008}	{42, 168}
{8, 882}	{48, 147}
{9, 784}	{49, 144}
{12, 588}	{56, 126}
{14, 504}	{63, 112}
{16, 441}	{72, 98}
{18, 392}	{84, 84}

By substituting these values in for , we find that the only pair that produces integer values for a and b is {49, 144}.

{49, 144} gives us a = 7 and b = 12.

So, .

Now, we can find all integers {c, d} such that , and all integers {e, f} such that .

This will give us numbers in the form and , which satisfy our given conditions.

So,

, or , or

Possible values for (c 7) and (d 7) are {1, 49} and {7, 7}

If we don’t want c to equal d, then the only solution is c = 8 and d = 56.

So, , or {8, 12, 56} is one value for {k, m, n}

Now we will find all integers {e, f} such that

, or , or

Possible values for (e 12) and (f 12) are:

{1, 144}

{2, 72}

{3, 48}

{4, 36}

{6, 24}

{8, 18}

{9, 16}

{12, 12}

If we don’t want e to equal f, the solutions for e and f are:

e = 13	f = 156
e = 14	f = 84
e = 15	f = 60
e = 16	f = 48
e = 18	f = 36
e = 20	f = 30
e = 21	f = 28

Thus, {7, 13, 156}, {7, 14, 84}, {7, 15, 60}, {7, 16, 48}, {7, 18, 36}, {7, 20, 30},

and {7, 21, 28} are all valid values for {k, m, n}.

(In fact, there are many other solutions that can be found by splitting differently.)

USAMTS Problem 3/3/13

Suppose p(x) = xⁿ + a_n-1xⁿ⁺¹ + … + a₁x + a₀ is a monic polynomial with integer coefficients. [Here monic polynomial just means the coefficient of xⁿ is one.] If (p(x))² is a polynomial all of whose coefficients are non-negative, is it necessarily true that all the coefficients of p(x) must be non-negative? Justify your answer.

If we take

p(x) = x⁵ + 100x⁴ + 100x³ x² + 100x + 100

we get

Here, p(x) is a monic polynomial with the coefficient of x² being negative. All the coefficients of (p(x))² are non-negative. Thus, it is not necessary for all the coefficients of p(x) to be non-negative for all the coefficients of (p(x))² to be non-negative.

USAMTS Problem 4/3/13

As shown in the figure on the right, in ΔACF, B is the midpoint of, D and E divide side into three equal parts, while G, H, and I divide side into four equal parts. Seventeen segments are drawn to connect these six points to one another and to the opposite vertices of the triangle. Determine the points interior to ΔACF at which three or more of these line segments intersect one another. To make grading easier, we have embedded the triangle into the first quadrant with point F at the origin, point C at

(30s, 30t), and point A at (60r, 0), where r, s, and t are arbitrary positive real numbers. Please use this notation in your solutions.

Using one specific triangle (see Fig. 1), I drew, experimentally, the seventeen segments. I found that there were only two likely cases of more than two lines intersecting at a single point. These are the intersection of, and , and the intersection of , , and . We will prove that these triplets of lines do indeed intersect at single points. (See proofs 1a and 1b) .

We will also prove that:

The shape and size of the triangle does not matter when considering if the lines intersect at a single point or not. In other words one can take any arbitrary value for (r, s, t). (See proof 2) (Thus, In fact to simplify, one can use r=t=1, and s=0)
Hence there are only two such common points in any triangle. (If the points clearly do not coincide in a particular case, they will not, in any other triangle)
We will also show mathematically that these are the only two points. (See part 3)

Using the given coordinate system, the coordinates of points A F are:

A(60r, 0), B(15s + 30r, 15t), C(30s, 30t), D(20s, 20t), E(10s, 10t), F(0, 0), G(15r, 0), H(30r, 0), and I(45r, 0)

Proof 1a:

We will show that , , and meet at one point.

The equation of is

= 20tx 1200rt …. (Eq 1)

The equation of is

= 15tx 450rt ……………(Eq 2)

The equation of is

= 30tx 1350rt …… (Eq 3)

By multiplying Eq 1 by 3 and subtracting Eq 2 multiplied by 4 we get for the point of intersection for lines and :

y(60s 180r 60s) = -1800rt

or y = 10t

Similarly, by subtracting Eq 3 from 2 times Eq 2, we get for the point of intersection of lines and :

y(45r) = 450rt

or y = 10t

Since both points have same y value, we need not check the x value because none of the above lines are horizontal.

Thus the three lines intersect at one point

Substituting the value in Eq (1) we get x = 30r+10s and so the common point is,

(30r+10s, 10t)

Proof 1b:

We will show that, , , and meet at one point.

The equation of is

, or

(s + 2r)y = tx ………… (Eq 4)

The equation of is

y(30s 15r) = 30t(x 15r) = 30tx 450tr, or

(2s r)y = 2tx - 30tr ………(Eq 5)

The equation of is

y(10s 30r) = 10t(x 30r) = 10tx 300tr, or

(s 3r)y = tx - 30tr ………(Eq 6)

By subtracting Eq 4 from Eq 6, we get, for the point of intersection of lines and :

-y(s 3r) + y(s + 2r) = 30tr, or

y = 6t

By subtracting two times Eq 4 from Eq 5, we get, for the point of intersection of lines and :

-y(2s r) + y(2s + 4r) = 30tr, or

y = 6t

Again, since both points have same y value, we need not check the x value because none of the above lines are horizontal.

Thus the three lines intersect at one point

Substituting the value of y in Eq (4) we get x = 12r + 6s,

So the common point is at

(12r+6s, 6t)

Proof 2:

Let and be two intersecting lines in ΔACF. Let L and N be the points on where these lines meet at the base. (We will later discuss the case where the end points are not on the line AF) Let the point of intersection be P.

Let us take the case where both K and M are on the line CF. (See Fig 2).

According to the problem, the values of and are given constants (they do not depend on r, s, or t)

Now, let us draw a line parallel to through C, and a line parallel to through C, meeting at points L' and N', respectively.

So,

ΔFKL ~ ΔFCL'

So, the values of and are constants and hence is also a constant.

Now

ΔPNL ~ ΔCN'L'

Thus, the height of ΔPNL is proportional to the height of ΔCN'L' . In other words, the height (or y-coordinate) of the point P depends only on the height of the original triangle, and not the shape.

Using similar logic, it is easy to see that this will hold true even if the point K is on the line , as long as the ratio of AK to AC is a given constant. Similarly, if the two end points are on lines AC and CF, one simply extends the line so that it meets the bases . (In the given problem there are no horizontal lines, so the line will meet AF) . In all the cases , the horizontal segments of the small and large triangles would be proportional to the base of the triangle and the height would be proportional to the height of the original triangle.) See following figures

Here AL’ is AL *(AC/KL) hence it is proportional to AF.

CS= (CF/RC)*CK ; SA= CA-CS ; and LA = (KA/SA)*FA and thus LA/FA is a constant (depends only on the given ratios)

This method also suggest an easy way to find the heights of the points of intersection, and thus one can calculate if more than two lines meet at a point. Each line now can be represented by two parameters. First lets us take, t=1, r=1, and s=0. The two parameters are: x- intercept of the line (We will call it p of the line) and the x-intercept of the line parallel to the line and passing through C, (We will call it q). Then the height of the point of intersection is :

(difference in p values)/(different in q values) * (Height of the triangle).

Part 3 -

Let us write for all these lines:

Line	p value	q value	p/15	q/15
AD	60	90	4	6
AE	90	180	6	12
BD	120	180	8	12
BE	-60	-180	-4	-12
BF	0	-60	0	-4
BG	15	-30	1	-2
BH	30	0	2	0
BI	45	30	3	2
CG	15	15	1	1
CH	30	30	2	2
CI	45	45	3	3
DG	15	45/2	1	3/2
DH	30	45	2	3
DI	45	135/2	3	9/2
EG	15	45	1	3
EH	30	90	2	6
EI	45	135	3	9

Note that we have added additional columns as (p/15 and q/15) ,as , we are only concerned with the ratio, and these values will make it easier to calculate:

Using the above values, we find that the “y” values of the points of intersection ( and multiplying the ratio by 30 to get the answer in the same form as before) we get:

The following table shows the y coordinates of all points of intersection:

40/3

120/13

10/3

15/4

30/7

45/4

60/7

90/7

60/11

20/3

60/11

20/3

60/7

180/17

20/3

150/13

10/3

90/7

90/13

15/2

45/7

100/9

15/2

120/7

90/11

140/11

15/2

(Lines that obviously do not intersect inside the triangle have been ignored.)

It is easy to see that the only triplets of intersecting lines that have the same y coordinate are ((AD, BH), (AD, CI), (BH, CI); y = 10), and ((BF, CG), (BF, EH), (CG, EH); y = 6)

The only points where three or more lines intersect in a way described in the problem are:

(30r + 10s, 10t) and (12r + 6s, 6t)

USAMTS Problem 5/3/13

Two perpendicular planes intersect a sphere in tow circles. These circles intersect in two points, spaced 14 units apart, measured along the straight line connecting them. If the radii of the circles are 18 and 25 units, what is the radius of the sphere?

Let O be the center of the sphere, and P and Q be the centers of the circles with radii 18 and 25, respectively. Let the circles meet at points A and B, and let C be the midpoint of .

So,

Also, OQC = QCP = CPO = PCA = 90

So,

Now, from right ΔOQA, we get

Thus, the length of radius is 30.

1	1	2	3	4	5
2	3	1	1	4	5
2	3	1	1	5	4
2	3	1	4	1	5
2	3	1	4	5	1
2	3	1	5	1	4
2	3	1	5	4	1
2	3	4	1	1	5
2	3	4	1	5	1
2	3	4	5	1	1
2	3	5	1	1	4
2	3	5	1	4	1
2	3	5	4	1	1

1	1	2	3	4	5
2	3	1	1	4	5
2	3	1	1	5	4
2	3	1	4	1	5
2	3	1	4	5	1
2	3	1	5	1	4
2	3	1	5	4	1
2	3	4	1	1	5
2	3	4	1	5	1
2	3	4	5	1	1
2	3	5	1	1	4
2	3	5	1	4	1
2	3	5	4	1	1

1	1	2	3	4	5
2	3	1	1	4	5
2	3	1	1	5	4
2	3	1	4	1	5
2	3	1	4	5	1
2	3	1	5	1	4
2	3	1	5	4	1
2	3	4	1	1	5
2	3	4	1	5	1
2	3	4	5	1	1
2	3	5	1	1	4
2	3	5	1	4	1
2	3	5	4	1	1