Summer Problem Solving Marathon Question #46

[Value = 3 points]

What is the surface area of a cube with a space diagonal of length 1? (The space diagonal of a cube is the line segment from a vertex of the cube to the most distant vertex from that vertex.)

Summer Problem Solving Marathon Question #45

(This question should have been posted Thursday. Sorry for the delay.)

[Value = 6 points]

A fair coin is tossed 12 times. What is the probability that there are no two consecutive heads in the string of tosses?

Summer Problem Solving Marathon Solution #43

Let log₈(log₂ x) = y. Then log₂ x = 8^y = 2^3y, and x = 2^23y.

We then also have log₂(log₈ x) = y, so log₈ = 2^y, and x = 8^2y = 2^3(2y).

Since log₈(log₂ x) = log₂(log₈ x), we have 2^23y = 2^3(2y). Thus 3^3y = 3(2^y), and 2^2y = 3, and 2y = log₂ 3, and y = (log₂3)/2.

Since x = 2^3(2y), log₂ x = 3(2^y), and (log₂ x)² = 9(2^2y).

We now substitute (log₂3)/2 for y in this expression. This gives 9(2^log₂3) = 9 x 3 = 27.

Summer Problem Solving Marathon Solution #42

Let x be the probability of getting heads (H) on the biased coin. Then 1-x is the probability of getting tails (T).

We first calculate the probability of getting exactly one head. There are five outcomes with exactly one head (matching the five ways of picking a location for the H in the sequence). Each of those five ways has probability x(1-x)⁴ of occurring. So p(H=1) = 5x(1-x)⁴.

Next we calculate the probability of getting exactly two heads. There are ten outcomes with exactly two heads (matching the ten ways of picking two locations for the two Hs in the sequence). Each of these ten ways has probability x²(1-x)³ of occurring. So p(H=2)=10x²(1-x)³.

Since p(H=1) = p(H=2), we have:

5x(1-x)⁴ = 10x²(1-x)³

Simplifying (given that 0 < x < 1), we have:

1 - x = 2x
x = 1/3

We now calculate p(H=3). There are ten ways of picking locations for the three heads. Each of those ten ways has probability x³(1-x)² of occurring. So our probability is:

10(1/3)³(2/3)² = 40/243

Summer Problem Solving Marathon Question #44

[Value = 5 points]

Simplify (56 + 6√43)^3/2 - (56 - 6√43)^3/2 to an integer value. No calculators allowed for this question!

Summer Problem Solving Marathon Question #43

[Value = 6 points]

Log₂(log₈ x) = log₈(log₂ x). Find (log₂ x)².

Summer Problem Solving Marathon Question #42

[Value = 4 points]

A certain biased coin has a fixed probability of coming up heads, where that probability is neither 0 nor 1. When the coin is flipped five times, the probability of getting exactly one head is the same as the probability of getting exactly two heads. What is the probability of getting exactly three heads?

Summer Problem Solving Marathon Solution #41

Adding all three equations, we obtain:

(k+2)x + (k+2)y + (k+2)z = 3k

or:

(k+2)(x+y+z) = 3k

When k = -2, this becomes 0 = -6, which is not true for any values of x, y, and z. So there is no solution to the system of equations when k = -2.

For any other value of k, we have x + y + z = 3k/(k+2). So by setting x = y = z = k/(k+2), we obtain a solution.'

Thus k = -2 is the only value for which there is no solution in x, y, and z to the system of equations.

Summer Problem Solving Marathon Solution #40

Because 3 and 5 are both odd, 3¹¹ and 5¹³ are also both odd. Thus 3¹¹ + 5¹³ is even, and is divisible by 2. So 2 is the smallest prime factor of the sum.

Summer Problem Solving Marathon Solution #39

Consider first the horizontal movement of the bug. The bug moves horizontally on each odd-numbered move, with the horizontal movements alternating positive and negative directions. On the first move, the bug moves 1 unit horizontally, on the third -1/4 horizontally, on the fifth 1/16 horizontally, on the seventh -1/64 horizontally, and so on.

Combining successive positive and negative movements, we have movement of 3/4, and then 3/64, and so on. This is an infinite geometric sequence with initial term 3/4 and common ration 1/16. Its sum is thus (3/4)/(1 - 1/16) = (3/4)/(15/16) = 4/5.

Next consider the vertical movement of the bug. The bug moves vertically on each even-numbered move, with the vertical movement alternating positive and negative directions. On the second move, the bug moves 1/2 unit vertically, on the fourth -1/8, on the sixth 1/32, on the eighth -1/128, and so on.

Combining successive positive and negative movements, we have movements of 3/8, and then 3/128, and so on. This is an infinite geometric sequence with initial terms 3/8 and common ratio 1/16. Its sum is thus (3/8)/(1 - 1/16) = (3/8)/(15/16) = 2/5.

In the limit, then, the bug approaches the point (4/5, 2/5).

Summer Problem Solving Marathon Question #41

[Value = 5 points]

Find the set of all values of k such that the following system of equations has no solutions in x, y, and z:

kx + y + z = k
x + ky + z = k
x + y + kz = k

Summer Problem Solving Marathon Question #40

[Value = 1 point]

What is the smallest prime factor of 3¹¹ + 5¹³?

Summer Problem Solving Marathon Solution #38

Let x + iy be an arbitrary root of the polynomial. Then the reciprocal of that root is 1/(x + iy). We then convert the denominator to a real number by multiplying by the complex conjugate x - iy, to obtain:

(x - iy)/((x + iy)(x - iy)) = (x - iy)/(x² + y²)

But because the root is on the circle centered at 0 + 0i with radius 1, we have, by the Pythagorean theorem, x² + y² = 1. So the reciprocal of the root is x - iy.

But this is the complex conjugate of the original root. Complex roots of polynomials with real-valued coefficients always comes in pairs by complex conjugates, so the reciprocal of the original root is another root of the polynomial.

Thus the reciprocals of the roots of the polynomial are just the roots of the polynomial. We thus want the sum of the roots of the polynomial. But the sum of the roots of any polynomial with a leading coefficient of 1 is the negative of the coefficient of the next-to-largest power of the variable. Hence the sum of the roots, which is also the sum of the reciprocals of the roots, is -a.

Summer Problem Solving Marathon Solution #37

FLOOR(log₂N) will always be equal to the exponent of the largest power of 2 less than or equal to N. So:

FLOOR(log₂N) = 0 for N = 1
FLOOR(log₂N) = 1 for 2 ≤ N ≤ 3
FLOOR(log₂N) = 2 for 4 ≤ N ≤ 7
FLOOR(log₂N) = 3 for 8 ≤ N ≤ 15
FLOOR(log₂N) = 4 for 16 ≤ N ≤ 31
FLOOR(log₂N) = 5 for 32 ≤ N ≤ 63
FLOOR(log₂N) = 6 for 64 ≤ N ≤ 127
FLOOR(log₂N) = 7 for 128 ≤ N ≤ 255
FLOOR(log₂N) = 8 for 256 ≤ N ≤ 511
FLOOR(log₂N) = 9 for 512 ≤ N ≤ 1023
FLOOR(log₂N) = 10 for N = 1024

So the total we want is 2*1 + 4*2 + 8*3 + 16*4 + 32*5 + 64*6 + 128*7 + 256*8 + 512*9 + 10 = 8204.

Summer Problem Solving Marathon Question #39

[Value = 4 points]

A bug is at the origin of the Cartesian coordinate plane. It travels one unit right, to the point (1,0). It then makes a 90 degree turn counterclockwise, and travels .5 units to (1,.5). It continues in this manner -- making 90 degree turns counterclockwise, and each time travelling half as far as on the previous move. In the limit, what point does the bug approach?

Summer Problem Solving Marathon Question #38

[Value = 5 points]

Suppose that z⁴ + az³ + bz² + cz + d is a fourth-degree polynomial with real-valued coefficients. Suppose also that each root of this polynomial is a complex number lying on the circle in the complex plane centered at 0 + 0i and with radius 1. What is the sum of the reciprocals of the roots of the polynomial?

Summer Problem Solving Marathon Question #37

[Value = 6 points]

Let FLOOR(x) be the greatest integer that is less than or equal to x. What is the sum from N = 1 to N = 1024 of FLOOR(log₂ N)?

Summer Problem Solving Marathon Solution #36

The least common multiple of 6 and 8 is 24. Every multiple of 24 thus has a remainder of 0 when divided by 6 and when divided by 8.

For similar reasons, numbers that are 1 to 5 more than a multiple of 24 have remainders of 1 to 5 when divided by either 6 or 8.

We thus find numbers that are within 5 of a multiple of 24, between 101 and 199. There are four multiples of 24 in that range -- 120, 144, 168, and 192. That gives us 24 numbers with the same remainder upon division by 6 or 8. In addition, 101 is 5 more than 96, a multiple of 24. It thus works as well. This gives a total of 25 numbers.

Summer Problem Solving Marathon Solution #35

The volume of a sphere is (4/3)π r³, so the volume of the hemisphere of ice cream is (2/3)π 2³ = (16/3)π.

The volume of a cone is (1/3)hB, where B is the area of the circular base of the cone. Here the height is 8, and the circular base has radius 2 and hence area 4π. So the volume of the cone is (32/3)π.

Thus the total volume of ice cream is (16/3)π + (32/3)π = (48/3)π = 16π.

Summer Problem Solving Marathon Solution #34

When a right triangle is inscribed in a circle, its hypotenuse is a diameter of the circle. Thus the hypotenuse of the triangle is 14. Since the triangle is a 3:4:5 right triangle, its legs are then 42/5 and 56/5. The area of the triangle is then 1/2(42/5)(56/5) = 1176/25 = 47.04.

Summer Problem Solving Marathon Solution #33

For any choice of n, we can write 2ⁿ in the form nk + m, for some k and some m < n. (That is, we write 2ⁿ as some multiple of n, plus a remainder on division by n.)

We then rewrite 2⁽²ⁿ⁾ as 2^{nk + m} = 2^nk2^m.

We are now interested in the remainder of this when divided by 2ⁿ - 1. Since m < n, the remainder of 2^m when divided by 2ⁿ -1 is 2^m. 2^nk can be rewritten as (2ⁿ)^k. But the remainder of 2ⁿ when divided by 2ⁿ -1 is clearly 1, so the remainder of (2ⁿ)^k when divided by 2ⁿ -1 is 1^k = 1.

Thus the remainder of 2⁽²ⁿ⁾ when divided by 2ⁿ -1 is 2^m. We want the remainder not to be a power of 4, which means we want m to be odd.

We are thus looking for n such that 2ⁿ, when divided by n, produces an odd remainder. Examination of cases then shows that 25 is the first value of n that works.

Summer Problem Solving Marathon Question #36

[Value = 3 points]

How many integers n, 100 < n < 200, have the same remainder when divided by 6 and when divided by 8?

Summer Problem Solving Marathon Question #35

[Value = 3 points]

The interior of a right circular cone is 8 inches tall with a 2 inch radius at the opening. The interior of the cone is filled with ice cream, and the cone has a hemisphere of ice cream exactly covering the opening of the cone. What is the volume of the ice cream?

Summer Problem Solving Marathon Solution #32

Given any S meeting the conditions, let s be the number of elements in S, and let N be the sum of all the elements in S.

Given any n∈S, the mean of the elements in S other than n is an integer. There are s-1 other elements in S, and their sum is N - n. So s-1 is a factor of N-n. Thus N and n are congruent mod s-1 (that is, they have the same remainder when divided by s-1).

Since 1∈S, N and 1 are congruent mod s-1, and in fact all elements of S are congruent to 1 mod s-1. Since 2002∈S, we know that 2002 is congruent to 1 mod s-1, so 2001 is a multiple of s-1. Since 2001 = 3 x 23 x 29, the possible values for s are 4, 24, 30, 70, 88, 668, and 2002.

If we list the numbers that are congruent to 1 mod s-1, we get 1, s, 2s-1, 3s-2, ... . The s^th such number is 1 + (s-1)(s-1) = s² - 2s + 2. So the largest element of S must be of size at least s² - 2s + 2. Since the largest element is 2002, this rules out 70, 88, 668, and 2002 as values of s.

Thus the largest possible value of s is 30. It remains to see that this value of s can be made to work. We will need a set of 30 elements, each of which is congruent to 1 mod 29. There are many sets meeting this constraint, including {1, 30, 59, 88, ..., 813, 2002}.

Summer Problem Solving Marathon Question #34

[Value = 2 points]

A right triangle similar to a 3:4:5 right triangle is inscribed in a circle of radius 7. What is the area of the triangle?

Summer Problem Solving Marathon Question #33

[Value = 10 points]

Let N be

(a) the smallest integer n > 1 such that when 2⁽²ⁿ⁾ is divided by 2ⁿ-1, the remainder is not a power of 4

or

(b) 0, if there is no such n.

What is N?

Summer Problem Solving Marathon Question #32

[Value = 9 points]

Let S be a set of positive integers, such that 1 ∈ S, 2002 ∈ S, and for all n ∈ S, n < 2003.

Suppose S has the following feature: for any n ∈ S, the mean of the elements of S - {n} is an integer.

What is the greatest number of elements S could have?

Summer Problem Solving Marathon Solution #31

The length of CE is 2, so CDE has the same length base as ABC. Since D is the midpoint of AC, the perpendicular distance from D to BC is half that of the perpendicular distance from A to BC. Thus the height of CDE is half that of ABC.

CDE thus has the same base as ABC and half the height of ABC. Its area is thus half that of ABC.

The area of an equilateral triangle of side length s is (s²√3)/4. So the area of ABC is √3, and the area of CDE is (√3)/2.

Summer Problem Solving Marathon Solution #30

Diagonal AC is the hypotenuse of right triangle ABC, with legs 18 and 21. So AC is √(18² + 21²) = &radic(324 + 441) = √765.

AD is then the hypotenuse of right triangle ACD, with legs 14 and √765. AD is thus √(14² + 765) = √(196 + 765) = √961 = 31.

The perimeter of ABCD is thus 18 + 21 + 14 + 31 = 84.

Summer Problem Solving Marathon Solution #29

First we determine the length of the longest possible growing path. We do this by enumerating the distances between points. Two points in the grid can be separated by 0 to 3 units horizontally and 0 to 3 units vertically. Using the Pythagorean Theorem, that gives us the following possible distances:

√1: 0,1 and 1,0 separation
√2: 1,1 separation
√4: 0,2 and 2,0 separation
√5: 1,2 and 2,1 separation
√8: 2,2 separation
√9: 0,3 and 3,0 separation
√10: 1,3 and 3,1 separation
√13: 2,3 and 3,2 separation
√18: 3,3 separation

That's a total of 9 different distances, so the longest possible growing path would be of length 10.

Next we check to see if a length 10 path is possible, and (if it is possible) how many such paths there are. Since the movement options are more constrained when the distances are long than when they are short, we construct the path in reverse.

First we need a length √18 gap. This is possible only by moving from one corner dot to the opposite corner dot. For convenience, we label the dots (x,y), where x and y both range from 1 to 4. Then our path can start:

(1,1), (4,4)
(4,4), (1,1)
(1,4), (4,1)
(4,1), (1,4)

So there are four choices for the first pair of elements in the path.

Since the diagram is symmetric, these four choices will proceed in the same way. For convenience, we focus on the case (1,1), (4,4). From (4,4) we need a gap of √13. This requires moving 3 units in one direction and 2 in the other. There are two points that meet this requirement: (2,1) and (1,2). Symmetry is still preserved, so we focus on the case (2,1).

Next we need a gap of √10. This requires a movement of 3 units in one direction and 1 in the other. There are two points meeting this condition: (1,4) and (3,4).

However, (1,4) will not work. We next need a gap of distance √9, which requires a separation of 3 in one direction and 1 in the other. The points meeting this constraint are (1,1) and (4,4), but both of these are already in the path.

So we must proceed with (3,4). The only point of distance √9 from (3,4) is (3,1), so this move is forced. From here, we need a gap of distance √8, which requires a separation of 2 units in both directions. The only point meeting this constraint is (1,3), so this move is also forced.

Next we need a distance of √5, with separations of 2 and 1. (2,1), (3,2), and (3,4) all meet this constraint, but only (3,2) is unused, so this move is also forced.

Next we need a distance of &rdic;4, with separations of 2 and 0. (3,4) and (1,2) both meet this constraint, but only (1,2) is unused, so this move is also forced.

Next we need a distance of √2, with a separation of 1 unit in both directions. (2,1) and (2,3) meet this constraint, but only (2,3) is unused, so this move is also forced.

Finally we need a distance of √1, which requires a move of a single unit horizontally or vertically. There are four points meeting this constraint, but (3,1) is already in the path. The other three are available.

Looking back, we had 4 choices for the first move, 2 for the second, and 3 for the final. All other moves were forced. So there are a total of 4 x 2 x 3 = 24 paths of length 10.

The desired answer is then 10 x 24 = 240.

Summer Problem Solving Marathon Question #31

[Value = 4 points]

ABC is an equilateral triangle with side length 2. D is the midpoint of AC. Point E is chosen so that C is the midpoint of BE. What is the area of the triangle CDE?

Summer Problem Solving Marathon Solution #28

Working from right to left, we find that the first place with an obvious error is 4 + 2 = 1 in the 10,000 place. Assuming the previous parts are correct, we should have carried 1 from the previous place. So we have two possibilities:

(1) The 1 is correct, and the sum should be 11. Then either 4 needs to be replaced by 8, or 2 needs to be replaced by 6. However, replacing 4 with 8 creates an error in the hundreds place, so this possibility can be ignored.

(2) The 1 is incorrect. Then the 4 and 2 are correct, so 1 needs to be replaced with 7. But replacing 1 with 7 creates an error in the tens place.

So the only option is that 2 is replaced with 6. Making this substitution throughout, we find that the result is a correct addition. So the answer is 2 + 6 - 8.

Summer Problem Solving Maraton Question #30

[Value = 4 points]

Let ABCD be a quadrilateral in which AB is of length 18, BC is of length 21, and CD is of length 14. Let angle ABC be right, and let the diagonal AC be perpendicular to CD. What is the perimeter of ABCD?

Summer Problem Solving Marathon Solution #27

There are eight triangles of minimal size in the diagram. For convenience, number these 1 through 8, reading left to right on the top half of the square and then left to right on the bottom half of the square.

There are four triangles each made up of two of the smallest triangles -- one made from triangles 2 and 3, one made from 4 and 8, one made from 6 and 7, and one made from 1 and 5.

There are no triangles of size 3. There are four triangles of size 4 -- one made of triangles -- one made from triangles 1, 2, 3, and 5; one made from triangles 2, 3, 4, and 8; one made from triangles 4, 6, 7, and 8; and one made from triangles 1, 5, 6, and 7.

There are no triangles of any other size. Thus there are a total of 8 + 4 + 4 = 16 triangles in the diagram.

Summer Problem Solving Marathon Question #29

[Value = 6 points]

Consider a 4 x 4 square array of points, in which points immediately adjacent horizontally or vertically are 1 unit apart in distance.

A growing path is a non-repeating sequence of distinct points in the array, in which the distances between consectuive points in the path is strictly increasing.

Let x be the length of the longest possible growing path, and let y be the number of growing paths of that length. What is xy?

Summer Problem Solving Marathon Question #28

[Value = 2 points]

The following addition is incorrect:

742586 + 829430 = 1212016

However, it can be made correct by uniformly one of the digits in the problem throughout with another digit. What is the sum of the digit to be replaced and the digit that replaces it?

Summer Problem Solving Marathon Question #27

[Value = 1 point]

Let ABCD be a square. Draw in the diagonals AC and BD. Let E be the midpoint of AB, F be the midpoint of BC, G be the midpoint of CD, and H be the midpoint of DA. Draw in the line segments EG and FH.

How many triangles are there in the resulting diagram?

Summer Problem Solving Marathon Solution #26

We solve the problem by casework on the size of B. For convenience, let S = {1,2,3,4,5,6}.

If the size of B is zero, then A is definitely a subset of S - B = S. There are 2⁶ = 64 subsets of S, so there is a 1/64 chance that the size of B is zero. This gives us a 1/64 chance of success from this option.

The case when the size of B is six is similar -- in this case, A is definitely a subset of S. And there is a 1/64 chance that the size of B is 6. More generally, we will get the same results for size of B = 1 and size of B = 5, and for size of B = 2 and size of B = 4.

So far we have 1/64 + 1/64 chance of success, from the cases size B = 0 and size B = 6. Now consider the case when the size of B = 1. There are 6 subsets of size 1, so the chance of choosing such a subset is 6/64. If the size of B is 1, then there are two choice of A that are subsets of B. S - B is then of size 5, so there are 32 choices of A that are subsets of S - B. That makes a total of 32 + 2 - 34. However, we have counted the empty set twice, so in fact there are 33 choices of A. So we have a 6/64 chance of picking B of size 1, and then a 33/64 chance of picking A that works. This gives us a (33 x 6)/64² = 198/64² chance of success. Since the case when size B = 5 is the same, we double this to get 396/64².

Next we consider the case when the size of B is 2. There are 6 choose 2 = 15 ways of picking such a subset. There are then 4 choices of A that are subsets of B, and 16 choices of A that are subsets of S - B, for a total of 20. Again, we have double-counted the empty set, so we subtract 1 to get 19. So the chance of success when size B = 2 is (15 x 19)/64² = 285/64². Again we double this for the case size B = 4, to get 570/64².

Finally, we consider the case when the size of B is 3. There are 6 choose 3 = 20 ways of picking such a subset. There are then 8 choices of A that are subsets of B, and 8 choices of A that are subsets of S - B, for a total of 16. Subtracting the double-counted empty set, we get 15 choices of A. So the probability of success here is (20 x 15)/64² = 300/64².

Adding up the cases, we have (64 + 64 + 396 + 570 + 300)/64² = 1394/2¹² = 697/2¹¹ = 697/2048.

Summer Problem Solving Marathon Solution #25

The base of triangle AEF is AE, which is 3/4 the length of AB. Since F is the midpoint of BC, the height of triangle AEF is 1/2 the height of triangle ABC. So the area of AEF is (3/4)(1/2) = 3/8 the area of triangle ABC. Thus the area of AEF is (3/8)96 = 36.

Summer Problem Solving Marathon Solution #24

The first perpendicular is drawn from point C to point D. The second is drawn from point D to point E. Let points F, G, H, and so on be the ending points of the further perpendiculars.

CDE forms a right triangle, as does DEF. Furthermore, CD is parallel to EF (because both meet OB at a right angle). Thus the triangles CDE and DEF are similar. In fact, we form an infinite sequence of similar triangles -- CDE, DEF, EFG, FGH, and so on.

CD is the hypotenuse of CDE, and DE is the hypotenuse of DEF. CD is of length a, and DE is of length b. So the ratio of similarity between DEF and CDE is b/a. Side EF of DEF corresponds to side DE of CDE. So EF is of length b(b/a) = b²/a.

EF is the hypotenuse of EFG, and DE is the hypotenuse of DEF. So the ration of similarity between EFG and DEF is (b²/a)/b = b/a. In fact, we can easily see that the ratio of similarity between consecutive similar triangles in our sequence is always b/a. So side FG is EF(b/a) = (b²/a)(b/a) = b³/a².

Generalizing, we get a sequence of lengths:

a, b, b²/a, b³/a², b⁴/a³, ...

This is an infinite sequence with first term a and ratio b/a. Its sum is then:

a/(1 - b/a) = a((a-b)/a) = a²/(a-b)

Summer Problem Solving Marathon Question #26

[Value = 4 points]

Two subsets A and B are chosen at random from the set {1,2,3,4,5,6}. What is the probability that either A is a subset of B, or A is a subset of {1,2,3,4,5,6} - B?