Duke Math Meet 2008 Problem 8 Solution (Individual Round)

Let's try to find the solution to Duke Math Meet 2008 Problem 8. This question is from the individual round of that meet.

Problem: Duke Math Meet 2008 Problem 8

Find the last two digits of $ \sum_{k=1}^{2008} k {{2008}\choose{k}} $

Discussion:

$ (1+x)^n = \sum_{k=0}^{n} {{n}\choose{k}}x^k $

We differentiate both sides to have $ n(1+x)^{n-1} = \sum_{k=1}^{n} k {{n}\choose{k}}x^{k-1} $

Put $ n=2008 $ and $ x=1$ in the above equation to have

$ 2008(1+1)^{2007} = \sum_{k=1}^{2008} k {{2008}\choose{k}}1^{k-1} $

Thus $ \sum_{k=1}^{2008} k {{2008}\choose{k}} = 2^{2007} \times 2008 \equiv 8 \times 2^{2007} \equiv 2^{2010} $ mod 100

Now $ 2^{12} = 4096 \equiv -4 $ mod 100 . Now raising both sides to the power of 6, we have $ 2^{72} \equiv (-4)^6 \equiv 2^{12} \equiv -4 $mod 100 . Again raising both sides to the power 6 we have $ 2^{432} \equiv -4 \Rightarrow 2^{1728} \equiv 2^8 \equiv 56 $ mod 100.

Earlier we had $ 2^{72} \equiv -4 \Rightarrow 2^{216} \equiv -64 \equiv 36 $ mod 100

Hence $ 2^{1728} \times 2^{216} \equiv 2^{1944} \equiv 56 \times 36 \equiv 16 $ mod 100

Finally we know $ 2^{12} \equiv -4 \Rightarrow 2^{60} \equiv -1024 \equiv 76 $ mod 100 . Hence $ 2^{1944} \times 2^{60} \equiv 2^{2004} \equiv 16 \times 76 \equiv 1216 \equiv 16 $ mod 100

Thus $ 2^{2004} \times 2^{6} \equiv 2^{2010} \equiv 16 \times 64 \equiv 1024 \equiv 24 $ mod 100.

The two digits are 24.

Some Useful Links:

Duke Math Meet 2009 Problem 9 solution | Team Round

Try this Remainder problem from Duke Math Meet 2009 Problem 9. This problem is from the Team Round of the meet.

Problem: Duke Math Meet 2009 Problem 9

What is the remainder when $ 5^{5^{5^5}} $ is divided by 13 ?

By Fermat's Little Theorem

$ 5^{12} = 1 \mod 13 $

Now if we can find out $ 5^{5^5} \mod 12 $ we can find the answer.

By Euler's theorem $ 5^{\phi (12) } = 5^4 = 1 mod 12 $

Finally, if we can find $ 5^5 mod 4 $ we are done.

Since $ 5 \equiv 1 mod 4 \Rightarrow 5^5 \equiv 1 mod 4 \implies 5^5 = 4Q + 1 $

Thus $ 5^{5^5} = 5^{4Q +1} = 5^{4Q} \times 5 \equiv 1 \times 5 mod 12 $ (as we have previously computed $ 5^4 \equiv 1 mod 12 \Rightarrow 5^{4Q} \equiv 1 mod 12 $ )

Thus $ 5^{5^5} = 12Q' + 5 \Rightarrow 5^{5^{5^5}} = 5^{12Q' + 5 } = 5^{12Q'} \times 5^5 \equiv 5^5 mod 13 $ . (since we have previously computed $ 5^{12} \equiv 1 \mod 13 \implies 5^{12Q'} \equiv 1 mod 13 $ )

Thus $ 5^{5^{5^5}} \equiv 5^5 mod 13 $ . But $latex 5^5 = 3125 \equiv 5 mod 13 $ . Thus answer is 5.

Some Useful Links:

Number of Ordered Triples – Duke Math Meet 2009 Problem 7

Try this problem from Duke Math Meet 2009 Problem 7 based on the number of ordered triples. This problem was asked in the team round.

How many ordered triples of integers (a, b, c) are there such that $ 1 \le a, b, c \le 70 $ and $ a^2 + b^2 + c^2 $ is divisible by 28.

Any square quantity is 0 or 1 modulo 4

Now the sum of three square quantities is 0 or 1 mod 4. Since 28 is 0 mod 4, therefore none of the three squares can be 1 mod 4.

Thus a, b, c are even.

Again a square quantity is always 0, 1, 4, 2 mod 7

Since we want the three squares to add up to 0 mod 7 (28 is 0 mod 7), the possibilities are (0, 0, 0) mod 7 and (1, 4, 2) mod 7

So we have the following cases:

Case 1

a, b, c are all even multiples of 7. There are 5 of them. Since we are looking for ordered triplet there are $latex 5^3 = 125 $ of these$

Case 2

a, b, c are all even numbers. with 1, 6 mod 7, 2, 5 mod 7 and 3, 4 mod 7

1 mod 7 - 10 elements
6 mod 7 - 10 elements

Hence there are 20 numbers which are 1 or 6 mod 7. 10 of these are even.

Similarly, there are 20 numbers which are 2 or 5 mod 7 and 20 numbers which are 3 or 4 mod 7. Half of each of which we will take.

So 10 choices for each set. $ 10^3 = 1000$ choices. Now since we are taking ordered pairs, we must consider all the $ 3! = 6 $ permutations. So there are 6000 cases.

Hence answer is $ 6000 + 125 = 6125 $

Some Useful Links:

Count of Sparse Subsets - Duke Math Meet 2009 Problem 6

Try this problem from Duke Math Meet 2009 Problem 6 based on Count of Sparse Subsets. This problem was asked in the team round.

Call a set S sparse if every pair of distinct elements of S differ by more than 1. Find the number of sparse subsets (possibly empty) of {1, 2, . . . , 10}.

Suppose there are k elements in the sparse subsets. We put them in increasing order. Since any two elements differ by at least 2, we have $ a_2 \ge a_1 + 2 , a_3 \ge a_2 + 2 \ge a_1 + 4 , ... , a_5 \ge a_1 + 8 $ Hence there are at most 5 elements in the set.

To count the number of sparse sets we use the following strategy: look at the gaps

for example if there 4 elements in the subsets, after putting them in increasing order, we look at the gaps between the elements. There are 5 such gaps: $ g_1 = a_1 - 1, g_2 = a_2 - a_1 - 1 ... g_5 = 10 - a_4 $. These 5 gaps must account for the remaining 6 elements and the least value of the middle three gaps is 1.

Let $ g_2' = g_2 + 1 , g_3' =g_3 + 1 , g_4' = g_4+1 $

Thus we are looking for the number of non negative integer solutions of $ g_1 + g_2' + g_3' + g_4' + g_5 = 3 $. This is given by $latex \binom{7}{3} = 35 $

Similarly 5 element sparse sets we look at $ g_1 + g_2' + g_3' + g_4' + g_5' + g_6 = 1 $ This is given by $latex \binom{6}{1} = 6 $

Similarly for 3-element subsets we look at $ g_1 + g_2' + g_3' + g_4 = 5 $ . This is given by $latex \binom{8}{3} = 56 $

Similarly for 2-element subsets we look at $ g_1 + g_2' + g_3 = 7$ . This is given by $latex \binom{9}{2} = 36 $

Finally there are 10 single element sub set and 1 null set all of which are sparse.

Why?

Consider the statement:

'If there are two elements then they differ by at least 2.'

The above is an implication statement and it is true for singleton or null sets as 'if there are two elements' part of the statement is false (an implication statement becomes true if antecedent becomes false).

Hence the total number of sparse sets: 6 + 35 + 56 + 36 + 10 + 1 = 144

Some Useful Links:

Duke Math Meet 2009: First Relay Round

This post contains problems from the first relay round of the Duke Math Meet 2009. Try to solve these problems.

1A. Find the lowest positive angle $ \theta $ that satisfies the equation $ \sqrt {1+\cos \theta} = \sin \theta + \cos\theta $ expressed in degrees.

Discussion:

$ \sqrt {1 +\cos\theta} = \cos\theta + \sin \theta \Rightarrow \sqrt{2\cos^2 \frac{\theta}{2} } = \sqrt2{\frac{1}{\sqrt2} \cos\theta + \frac{1}{\sqrt2} \sin\theta } $

Now this gives

$ \sqrt2 \cos\frac{\theta}{2} = \sqrt2\cos(\theta - \frac{\pi}{4}) \Rightarrow \frac{\theta}{2} = \theta - \frac{\pi}{4} $ or $ \frac{\theta}{2} = -\theta + \frac{\pi}{4}$

Thus the possible values of $ \theta $ are $ 90^o $ or $ 30^o $.

Since we require the smallest positive angle hence the answer is $ 30^o $.

1B. Let n be two times the tens digit of TNYWR. Find the coefficient of the $ x^{n-1}y^{n+1} $ term in the expansion of $ (2x + \frac{y}{2} + 3)^{2n} $

Discussion:

TNYWR is 3. Hence n = 6 Thus we are required to find coefficient of $ x^5 y^7 $ term in the expansion of $ (2x + \frac{y}{2} + 3 )^{12} $

This can be easily found from trinomial expansion. The required term is $ {{12}\choose {5}}(2x)^5 {{7}\choose{7}} (\frac{y}{2})^7 = 792 \times 32 \times \frac{1}{128} = 198 $

1C. Let k be TNYWR, and let n = k/2. Find the smallest integer m greater than n such that 15
divides m and 12 divides the number of positive integer factors of m.

Discussion:

k = 198, hence n = 99.

So we have to look at multiples of 15 greater than 99. We want 12 to divide the number of positive divisors of m.

Suppose $ m = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k} $. The number positive divisors of k is $ (\alpha_1 +1 )... (\alpha_k + 1) $

The first multiple of 15 greater than 99 is $ 105 = 15 \times 7 $ . By inspection we see that m = 150.

Some Useful Links:

Area of Ellipse Problem – Duke Math Meet 2009: Problem 7

Try this problem from Duke Math Meet 2009 Problem 7 based on Area of Ellipse. This problem was asked in the individual round.

Let $ R_I , R_{II} , R_{III} , R_{IV} $ be areas of the elliptical region $ \frac{(x-10)^2}{10} + \frac {(y-31)^2}{31} \le 2009 $ that lie in the first, second, third, and fourth quadrants, respectively. Find $ R_I - R_{II} + R_{III} - R_{IV} $

Discussion:

Special Note: The answer to this problem is given as 1240. This is the wrong answer. It approximates the region $ R_I - R_{II} + R_{III} - R_{IV} $ as a rectangle. However, we provide a solution using symmetry using that assumption and that works fine. Computing area of the ellipse is a tricky business.

First, we draw an approximate picture of the ellipse. The centre is at (10, 31). Here is a figure of it.

To find $ R_{I} - R_{II} $ reflect region $ R_{II} $ about y-axis. Look at the figure. The shaded region is $ R_{I} - R_{II} $. Its width along the line through centre (y=31) is 20 by symmetry (as the centre is 10 unit away from x-axis so $ R_I $ is 20 unit 'thicker' than $ R_{II} $ . You may convince yourself about this by solving for x setting y = 31 ).

Now to find $ R_{III} - R_{IV} $ we reflect $ R_{III} $ about y-axis again. The strip (shaded in blue) is negative of $ R_{III} - R_{IV} $

Note that the blue region 'begins' 31 unit 'below' the minor axis of the ellipse. So if we go 31 unit 'above' the minor axis and take the portion of the red strip, by symmetry it will be equal to the blue strip. We have shaded it in black and red.

So if we want to find $ R_{I} - R_{II} - { - (R_{III} -R_{IV}) } $ we remove the black stripe from the red strip and get the final region whose area is $ R_I - R_{II} + R_{III} - R_{IV} $.

Here is where we apply approximation. Width of the strip is 20 and its height is (31+31) = 62. Hence if we approximate the area as a rectangle, then answer is $ 1240 (62 \times 20) $.

But note that the strip is not ACTUALLY a rectangle. So this is only an approximate answer.