USAMTS Problem 1/4/14

The sequence of letters TAGC is written in succession 55 times on a strip, as shown below.  The strip is to be cut into segments between letters, leaving strings of letters on each segment, which we will call words.  For example, a cut after the first G, after the second T, and after the second C would yield the words TAG, CT, and AGC.  At most how many distinct words could be found if the entire strip were cut?  Justify your answer.

Suppose we separate this string of letters into four sections of length 55.  Since 55 is not divisible by four, each section will begin with a different letter: the first, T, the second, C, the third, G, and the fourth, A.

Now, because this pattern consists of four letters in a four character repetition, there are four possible words of any given word length, one beginning with each of the four letters.  Thus, there are four 1 letter words, four two letter words, etc.

Now, 55 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10.

Thus, we can separate each 55 letter string into ten words: 1 1-letter, 1 2-letter, etc.

Because the four 55 letter strings are offset from one another, if we cut each strip in the same 1  2  3  4  5  6  7- 8  9  10 letter word pattern, corresponding words of different strands will be distinct, because each will start with a different letter.

Furthermore, with this arrangement, we attain the maximum possible number of words; all four 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 letter words.

There are ten words in each 55 letter strand Thus, the maximum possible number of words is 4(10) = 40

USAMTS Problem 2/4/14

We define the number s as

We can determine the nth digit right of the decimal point of s without summing the entire infinite series because after summing the first n terms of the series, the rest of the series sums to less than 2 / 10n  1.  Determine the smallest prime number p for which the pth digit right of the decimal point of s is greater than 2.  Justify your answer.

For this sum, each term can be written:

.1111111111... + 0.0101010101… + 0.0010010010… + 0.0001000100…

The nth term is a repeating decimal with ‘1’ appearing at every nth position.

In other words, the decimal representation of the nth term has a 1 at the ith position if n is a factor of i. All other digits are zero.

Thus, if we ignore carryover, the nth digit of the sum s is given by d(n) where d(n) is the number of divisors of n.

Since a prime number has only 2 divisors (itself and 1) we will get a 2 at its corresponding position if there is no carryover.

If d(n) > 9,  there will be a carryover onto the previous digit.

The smallest number for which d(n) > 9 is 48. 48 has 10 factors.

(The factors are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48; we can easily find the number of factors, because a number (2a * 3b * 5c * …) will have (a + 1)(b+ 1)(c+ 1)… factors.  48 = 24 * 31, thus it has (4 + 1)(1 +1) = 10 factors).

Luckily, 47 is prime, and thus the pth digit when p = 47 will be greater than 2.

We will show that this is the smallest prime number for which this is possible.

One might suppose that carryover could effect the nth digit even if d(n + 1) < 10.  For example, if d(n + 2) > 10 and d(n + 1) = 9, then carryover onto the nth digit would result.

We can show that such a situation for n < 50 is not possible..

Consider the contribution to s of all the digits after the first 50 digits.

The contribution from the 51st term and all following terms is less than 2(10)-51, as stated in the problem.  (This can be easily shown by comparing the series s to a geometric series where the terms are given by (1 / 9(10)i  1 )

The contribution from each of the first 50 terms is less than (0.12)(10)-50.

Thus, the total contribution is less than 50(0.12)(10)-50 + 2(10)-51, which is less than

7(10)-49.

This cannot provide carryover onto any term before the 48th.

Thus, since 48 is the first number that can provide carryover onto the previous digit, and 47 is prime, 47 is the smallest prime number p where the pth digit is greater than 2.

USAMTS Problem 3/4/14

Find the real-numbered solutions to the equation below and demonstrate that it is unique.

Let  and a and b are both nonnegative real numbers.  (In fact, a and b must be positive real numbers; they cannot equal zero because they are both found in the denominator.)

Now we have:

, or

, or

Now,  is the arithmetic mean of (72 / a) and 18a.

The geometric mean of (72 / a) and (18a) is 36.

Thus, since both these numbers are positive, and the arithmetic mean is always greater than or equal to the geometric mean, we have

> 36

Similarly,

> 6

The only way these two positive terms can add to be 42 is if

= 36   and    = 6

Thus, solving each equation separately, we have

and

Thus, x = 4 and y = 9 is the unique solution.

USAMTS Problem 4/4/14

Two overlapping triangles could divide the plane into up to eight regions, and three overlapping triangles could divide the plane into up to twenty regions.  Find, with proof, the maximum number of regions into which six overlapping triangles could divide the plane.  Describe or draw an arrangement of six triangles that divides the plane into that many regions.

When a set of regions composed of linear sides is intersected by a line segment, new regions are created for each region this segment intersects.  If there are n points of intersection between this line segment and previously existing sides, (n  1) new regions can be formed.

If we have a set of overlapping triangles, and we create a new triangle to intersect this set, each side of this triangle can intersect at most two sides of any single triangle. (A line segment could not intersect three lines of the same triangle.)   If we have x overlapping triangles, then the first side of the new triangle can intersect up to 2x sides, thus creating

(2x  1) new regions.  The second side of the new triangle intersects 2x sides from the original triangles, plus the first side of the new triangle; thus, it can create 2x new regions.  The third side of this new triangle can intersect 2x sides from the original triangles, plus the two sides it connects with in the new triangle; thus, it can create (2x + 1) new regions.

Thus, the maximum number of new regions that can be created in a set of x overlapping triangles by introducing another triangle is   (2x  1) + 2x + (2x + 1)   or   6x.

Thus, the maximum number of possible regions created by n overlapping triangles is the sum of the maximum number possible for (n  1) regions and 6(n  1), or

where Rn is the maximum number of regions created by n overlapping triangles.

We want to find an explicit formula for finding the maximum possible number of regions created.

.

So,

We know that 1 triangle separates the plane into two regions, so R1 = 2.

So,

So, the maximum possible number of regions created by six overlapping triangles is

3(36)  3(6) + 2 = 92 regions

See attached figure for a drawing of one arrangement that yields this number of regions.

USAMTS Problem 5/4/14

Prove that if the cross-section of a cube cut by a plane is a pentagon, as shown in the figure on the right, then there are two adjacent sides of the pentagon such that the sum of the length of these two sides is greater than the sum of the lengths of the other three sides.  For ease of grading, please use the names of the points from the figure on the right in your solution.

In the cube above, the top face (the face containing AE) is parallel to the bottom face (the face containing BC), and the left face (the face containing DE) and the right face (the face containing AB) are parallel.

A, B, C, D and E are all in the same plane, so if we extend ED and CB, they will meet at a point.  Let us call this point F.

Now,

AB parallel EF

and AE parallel BF

So, AEFB is a parallelogram.

Thus,

AB = EF

and AE = BF

So,

AB + AE = EF + BF

AB + AE = (DE + DF) + (CF + BC)

AB + AE = DE + BC + (DF + CF)

Now, take triangle FCD; this is a triangle, so CD < DF + CF

AB + AE = DE + BC + (DF + CF)

Hence,

AB + AE > DE + BC + CD