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?