SJSU Math Problem of the Week Competition

Fall 2008 Solutions

Final Problem! 

Week #13  Mon. Nov. 17 - Fri. Nov. 21

Problem 13 (25 points) 

Let n1 < n2 < n3 < ... be an infinite sequence of positive integers.  Prove there exists either an infinite subsequence in which no integer divides another, or an infinite subsequence where each integer is a multiple of the preceding one.  

Solution: Let S denote the set of integers in the sequence which divide no other integer in the sequence. If S is infinite, then S forms the required subsequence. Otherwise, if S is finite, delete S and any divisors of an element in S from the sequence, leaving an infinite subset, S' of the original sequence. Note that each element in S' divides at least one other element in S'. It is now easy to select an infinite subsequence b_1 < b_2 < b_3 < ... of S' in which each element after b1 is a multiple of the preceding one: Let b1 be the first element in S', and if b_k in S' has been chosen, let b_(k+1) be the first multiple of b_k in S' (necessarily greater than b_k).

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Two solutions to problem #13 were submitted. The final results of the 2008 Problem of the week competition have now been posted.

Week #12  

Mon. Nov. 10 - Fri. Nov. 14

Problem 12 (20 points) 

Suppose the points in the xy-plane are partitioned into three subsets.  Given any d > 0, show that there exist two points which belong to the same partition subset and which are, distance d apart. 

Solution: Consider the following 7-point configuration. Triangles ABC and BCD are equilateral triangles with each side of length d. Similarly triangles AEF and EFG are also equilateral with sides of length d. The points can be chosen so that D and G are distance d apart as shown below. Considered as a graph it can easily be shown that this figure has chromatic number 4. Thus any partition of the plane into 3 subsets will give a 3-coloring of the figure. Since the figure has chromatic number 4, one subset of the partition contains two or more points from this figure which are adjacent (distance d apart). QED

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Five solutions to problem #11 were submitted.  Phuong Ho received full credit for his solution.  Solutions to problem #13 should be submitted to the Math office by Mon. Dec. 1.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Week #11  Mon. Nov. 3 - Fri. Nov. 7

Problem 11 (15 points) 

A quadrilateral ABCD with diagonals AC and BD meeting at point E in the interior is shown below.  Assume that angle BDA is 80 degrees, angle CDB is 20 degrees, angle DCA is 50 degrees and angle BCA is also 50 degrees.  What is the measure of angle CAB. Hint: It's not just angle-chasing. 

Solution: Note that angle CBD is 60 degrees and angle CAD is 30 degrees.  Draw the angle bisectors of triangle BCD, which meet at incenter I on segment CE.  Since angle EBI and angle EAD are both 30 degrees, then triangles EBI and EAD are similar.  Therefore, triangles EAB and EDI are also similar.  Thus angles CAB, EAB, and EDI are all 10 degrees.   

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Five solutions to problem #11 were submitted.  Phuong Ho and Colin Blower both received full credit for their solutions.  Solutions to problem #12 should be submitted to the Math office by Wed. Nov. 19.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Week #10  Mon. Oct. 27 - Fri. Oct. 31

Problem 10 (14 points) 

2008problem10.pdf

Solution: 2008solution10.pdf

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Two solutions to problem #10 were submitted.  Zachi Baharav and Hien Vu both received full credit for their solutions.  Solutions to problem #11 should be submitted to the Math office by Wed. Nov. 12.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Week #9  Mon. Oct. 20 - Fri. Oct. 24

Problem 9 (13 points)  How many of the positive factors of the number 729,000,000 are not a perfect square and not a perfect cube? 

Solution: Since 729,000,000 = (2^6)*(3^6)*(5^6). Every factor has the form

(2^i)*(3^j)*(5^k) for i,j,k in {0,1,2,3,4,5,6} so there are 7*7*7 = 343 factors.  For a factor that is a perfect square i,j,k are in {0,2,4,6} so there are 4*4*4 = 64 factors that are squares,  For a factor that is a perfect cube i,j,k are in {0,3,6} so there are 3*3*3 = 27 perfect squares.  For a factor that is both a perfect square and a perfect cube i,j,k are in {0,6} so there are 2*2*2 = 8 such factors.  The number of factors that are not a perfect square and not a perfect cube is 343 - 64 - 27 + 8 = 260. 

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Seven solutions to problem #9 were submitted.  Zachi Baharav, Colin Blower, Sahana Vasudevan, Nikhil Buduma, all received full credit for their solutions.  Solutions to problem #10 should be submitted to the Math office by Wed. Nov. 5.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Week #8  Mon. Oct. 13 - Fri. Oct. 17

Problem 8 (12 points)  Find an expression for the continued radical

C = (m + (m + (m + ... )^.5)^.5)^.5 in terms of m that does not involve a continued radical.  Then determine all positive integers m so that C is a positive integer.  Here n^.5 denotes the square root of n.

Solution: By squaring both sides we get C^2 = m + (m + (m + (m + ... )^.5)^.5)^.5, or

C^2 - C - m = 0, with positive solution C = [1 + (1+4m)^.5]/2.  In order to have C a positive integer, we must have 1 + 4m = k^2, where k is an odd integer.  This implies m = (k^2-1)/4 = [(k-1)/2][(k+1)/2].  This means that m = 2,6,12, ... must be the product of two consecutive positive integers. 

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Two solutions to problem #8 were submitted.  Zachi Baharav and Phuong Ho both received full credit for their solutions.  Solutions to problem #9 should be submitted to the Math office by Wed. Oct. 29.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Week #7  Mon. Oct. 6 - Fri. Oct. 10  

Problem 7  (11 points)  In triangle ABC, the length of side CB is a, the length of side CA is b, and the measure of the angle ACB between these sides is 120 degrees.  The bisector of angle ACB is drawn and its intersection point with the opposite side AB is labeled D.  Express the length of CD in terms of a and b.

Solution: Let d denote the length of CD, and let e be the measure of angle ACB.  Since the area of triangle ABC is the sum of the areas of triangles ACD and CDB, we have a*b*sin e = a*d*sin(e/2) + b*d*sin(e/2) = d(a+b)sin e/2 and since sin e = 2*sin (e/2)*cos(e/2) it follows that 2*a*b*sin(e/2)*cos(e/2) = d(a+b)*sin(e/2) which implies [cos(e/2)]/d = (a+b)/(2ab) and since e = 120 degrees and e/2 = 60 degrees then 1/d = (a+b)/(ab) and thus d = (ab)/(a+b).

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Two solutions to problem #7 were submitted.  Zachi Baharav and Phuong Ho both received full credit for their solutions.  Solutions to problem #8 should be submitted to the Math office by Wed. Oct. 22.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page. 

Problem 6  (10 points)  Let H_n = 1/1 + 1/2 + 1/3 + ... + 1/n be the nth Harmonic number.  For which x > 1 does the sum 1/(x^{H_1}) + 1/(x^{H_2}) +... + 1/(x^{H_n}) converge as n goes to infinity (where x^y represents the yth power of x). 

Solution: It is well known (and easy to show) that if H_n = 1 + 1/2 + ... + 1/n, then

ln n < H_n < 1 + ln n.  So [1/(1^ln x) + 1/(2^ln x) + ... + 1/(n^ln x) + ...)/x =

[1/(x^ln 1) + 1/(x^ln 2) + ... + 1/(x^ln n) + ...)/x =

[1/(x^(1+ln 1)) + 1/(x^(1+ln 2)) + ... + 1/(x^(1+ln n)) + ...) <

[1/(x^(H_1)) + 1/(x^(H_2)) + ... + 1/(x^(H_n)) + ...) <

[1/(x^(ln 1)) + 1/(x^(ln 2)) + ... + 1/(x^(ln n)) + ...) =

[1/(1^ln x) + 1/(2^ln x) + ... + 1/(n^ln x) + ...)

Thus if ln x > 1 (x > e), then we get convergence by the right inequality.  On the other hand if ln x <= 1 (x <= e), then we get divergence by the left inequality.  Hence the sum 1/(x^{H_1}) + 1/(x^{H_2}) +... + 1/(x^{H_n}) converges if and only if x > e. 

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  One solution to problem #6 was submitted. Zachi Baharav received full credit for his solution. Solutions to problem #7 should be submitted to the Math office by Wed. Oct. 15.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page.   

Week #5  Mon. Sept. 22 - Fri. Sept. 26  

Problem 5  (9 points)  Let a,b, and c be real numbers satisfying a^2 + b^2 + c^2 = 1.  Prove the inequalities -1/2 <= ab + bc + ca <= 1.  (where x^2 represents the square of x and <= represents less than or equal to). 

Solution:  i) (a + b + c)^2 >= 0 ->

                  a^2 + b^2 + c^2 + 2(ab + bc + ca) >= 0 ->

                  ab + bc + ca >= -1/2

               ii) (a-b)^2 + (b-c)^2 + (c-a)^2 >= 0 ->

                   2(a^2 + b^2 + c^2) -2(ab + bc + ca) >= 0 ->

                   1 >= ab + bc + ca. 

Week #4  Mon. Sept. 15 - Fri. Sept. 19  

Problem 4  (8 points)  Two players play a game on a 5 x 5 checkerboard.  In turn, each player places a 1 x 2 domino so that it exactly covers two uncovered squares of the checkerboard.  The last player able to place a domino wins the game.  Determine (with justification) the length of the shortest possible game. 

Solution:  Label the squares of the board as A1,A2,...,A5,B1,B2,...,B5,...,E1,E2, ...,E5.  A game ending after 9 turns consists of placing dominos on the following pairs of squares (A2,A3),(A5,B5),(B1,B2),(B4,C4), (C2,C3),(D1,E1),(D2,D3), (D5,E5),(E3,E4).  Since no two adjacent squares remain the game must end.  At the end of a game at least two dominos must intersect each of the four 2 x 2 corner blocks ({A1,A2,B1,B2},...,{D4,D5,E4,E5}) and since no single domino can cover a square in two corner blocks every ending position contains at least 8 dominos.  None of these 8 dominos can cover the center square C3 so for an ending position with 8 dominos, every square adjacent to C3 must be covered and these four dominos would cover the 8 squares around the center

{B2,B3,B4,C4,D4,D3,D2,C2}.  The 16 remaining squares on the outer edge of the board would be impossible to cover with 4 dominos without leaving two adjacent squares.  Thus no ending position with 8 dominos can exist.    

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Four solutions to problem #4 were submitted. David Alves received full credit for his solution. Solutions to problem #5 should be submitted to the Math office by Wed. Oct. 1.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page.   

Week #3  Tues. Sept. 8 - Fri. Sept. 12  

Problem 3  (7 points)  Given any set S of ten distinct positive integers less than 100, prove that there are two disjoint subsets X,Y of S such that the sum of the elements of X is equal to the sum of the elements of Y.   

Solution:  There are 10^10 - 1 = 1023 nonempty subsets of S.  The sums of their elements can range from 1 to 90+91+92+93+94+95+96+97+98+99 = 945.  Thus there are two nonempty subsets X,Y of S such that the sum of the elements of X is equal to the sum of the elements of Y.  By removing from X and Y the elements that the two subsets have in common we obtain two disjoint subsets X' and Y' which have the same property.

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Four solutions to problem #3 were submitted. Colin Blower and Phuong Ho both received full credit for their solutions. Solutions to problem #4 should be submitted to the Math office by Wed. Sept. 24.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page.   

Week #2  Tues. Sept. 2 - Fri. Sept. 5  

Problem 2 (6 points) Find the limit as n goes to infinity of

{[(1 + 1/n)^n]/e}^n (where x^n represents x to the nth power).   

Solution:  We have ln lim {[(1 + 1/n)^n]/e}^n

            = lim ln {[(1 + 1/n)^n]/e}^n

            = lim [ln (1 + 1/n) - 1/n]/(1/n^2)

            = lim [(1/(1 + 1/n)(-1/n^2)-(-1/n^2)]/(-2/n^3)

            = lim [n/(n+1) - 1]/(2/n) = (-1/2) lim n/(n+1)

which approaches -1/2 as n goes to infinity. 

Thus lim {[(1 + 1/n)^n]/e}^n = e ^ (-1/2). 

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Four solutions to problem #2 were submitted. Zachi Baharav received full credit for his solution. Solutions to problem #3 should be submitted to the Math office by Wed. Sept. 17.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page.   

Week #1  Mon. Aug. 25 - Fri. Aug. 29  

Problem 1 (5 points) For any n >= 0, show that

157^(2n+1) + 1098^(2n+1) + 46^(2n+1) + 707^(2n+1)

is always divisible by 2008 (where a^b represents a to the bth power). 

Solution: Note that 2008 = 8 * 251 and (8,251) = 1, so it suffices to show that for all n >= 1, f(n) = 157^(2n+1) + 1098^(2n+1) + 46^(2n+1) + 707^(2n+1), 8 | f(n) and 251 | f(n). We see that a^(2n+1) + b^(2n+1) = (a+b)(a^(2n) - a^(2n-1)*b + a^(2n-2)*b^2 - ... + b^(2n)) so (a+b) | (a^(2n+1) + b^(2n+1)). Therefore 1144 | 1098^(2n+1) + 46^(2n+1) and 864 | 157^(2n+1) + 707^(2n+1). Since 8 | 1144 and 8 | 864 then 8 | f(n), for all n >= 1. Also 1255 | 1098^(2n+1) + 157^(2n+1) and 753 | 46^(2n+1) + 707^(2n+1). Since 251 | 1255 and 251 | 753 then 251 | f(n), for all n >= 1. Therefore 2008 | f(n), for all n >= 1.

Copies of this solution are available from the shelves in front of the Math office, MH 308, or online from Professor Jackson's web page at http://www.math.sjsu.edu/~jackson.  Two solutions to problem #1 were submitted. Phuong Ho received full credit for his solution. Solutions to problem #2 should be submitted to the Math office by Wed. Sept. 3.  Remember that a correct solution should also contain an explanation of the answer.  Make sure that your name, student ID number, and the division you are participating in (undergraduate or graduate or SJMC) are printed legibly at the top of the page.