2005  Problem of the Week Competition: Solutions  

Final Results!!!                                                    12/8/05

Week #13  Mon. Nov. 21 – Fri. Dec. 2 

 

 Problem 13 (25 points):  The vertices of a 10-dimensional cube are represented by the set of 1024 binary sequences of length 10 (each digit is either 0 or 1).  Let S be any subset of at least 205 binary sequences (vertices).  Show that S will always contain an equilateral triangle.  

Solution

Let X represent the vertices of the cube and let S be a subset of X containing 205 vertices.  For each point P in S let XP be the set of 10 points that differ from P in just one coordinate. Each set XP contains 10 vertices and there are 205 such sets.  Since 10*205 > 2*1024 there is one point of X, which is contained in three of the sets XP1, XP2,  and XP3.  The corresponding points P1, P2, P3 differ from each other in two coordinates and thus form an equilateral triangle.

Copies of this solution are available from the shelves in front of the Math office, MH 308, or from Professor Jackson’s webpage www.math.sjsu.edu/~jackson.  One solution to problem #13 was submitted. 

 Final Results: In the undergraduate division Cuong Dong finished 1st, Andrew Macheret was 2nd, and Johan Johansson was 3rd.  In the graduate division Weidong Shao finished 1st, Matthew Low was 2nd, and Helene Payne was 3rd.  In the SJMC division Powell Akagawa finished 1st and Bowei Liu was 2nd.  The 1st place finishers will receive checks for $50, the 2nd place finishers will receive checks for $30, and the 3rd place finishers will receive checks for $20.  Stop by the math office to make sure that we have your correct student ID number.  Your checks can be picked up after Feb. 1.  

                                                                                      11/21/05

Week #11    Mon. Nov. 7 – Fri. Nov. 11

 Problem #11 (15 points): A sequence (of real numbers) of length  is simply an -tuple . A subsequence of  of length  is an -tuple of the form  for some integers . Such a subsequence is monotone if either  or else .

 (1) Show if  is a positive integer and  is a sequence of length , then  has a monotone subsequence of length .

 (2) Show (by specific example) that if instead  has length , it is possible that the longest monotone subsequence of  has length .

 (3) For all positive integers , let  be the largest integer  such that every sequence of length  has a monotone subsequence of length . Show that  for all , where  denotes the ceiling function.

 solution: (1) Let  be any sequence of length . A subsequence  is increasing if , and is decreasing if .

For each , let  be the maximum length  of any increasing subsequence  of  with , and  the maximum length  of any decreasing subsequence  of  with . Let  be the map sending each  to the pair . We claim that  is one-to-one. To see this, suppose . If  then for any increasing subsequence  with , the (longer) subsequence  is also increasing, and so we must have . And if  then for any decreasing subsequence  with , the (longer) subsequence  is also decreasing, and so we must have . Thus  in any case, which shows that  is one-to-one.

            Now to show  has a monotone subsequence of length , we suppose not and obtain a contradiction. If  has no monotone subsequence of length , then we must have  for all . Thus  may be viewed as a map , and since , this map cannot be one-to-one, which contradicts what was shown above. Thus  has a monotone subsequence of length , as required.

(2)  For the case where  we let ,

 

 
which is “graphed” on the right. In general (i.e. for any

positive integer ), let  where, for all

, we have . Then any

increasing subsequence of  contains at most one term

 with any one value of  and hence has length ,

and any decreasing subsequence of  contains no two terms

 with different values of  and hence has length .

 (3)  First, it is clear that if  then , for if every -term sequence has

an -term monotone subsequence, then certainly every -term sequence has one also. The formula  holds if . Now assume . We have , and so , for a (unique) positive integer , and in fact . By part (1) we have , and by part (2) (with  in place of ) we have . So we have , and it follows that .

Week #10  Mon. Nov. 7 – Fri. Nov. 11                  

 Problem 10 (14 points):  Let a,b,c, and d be a set of 4 real numbers such that a + b + c + d = 0.  Show that the sum of their cubes is 0 (a3 + b3 + c3 + d3 = 0) if and only if the sum of their fifth powers is equal to 0 (a5 + b5 + c5 + d5 = 0). 

Solution:  a+b+c+d = 0   =>  a + b = -(c+d) =>

1) (a+b)2 = (c+d)2 => a2 + b2 + c2 + d2 = 2[(a+b)2 – ab – cd] and

2) (a+b)3 = -(c+d)3 => a3 + b3 + c3 + d3 = - 3cd(c+d) - 3ab(a+b) =

3(cd - ab)(a+b) and

3) (a+b)5 = -(c+d)5   =>

a5+b5+c5+d5 = 5ab(a3+b3)+10a2b2(a+b)+ 5cd(c3+d3)+10c2d2(c+d) = 5ab(a+b)(a2+b2–ab) + 5cd(c+d)(c2+d2–cd) = 

5(a+b)(cd – ab)[(a + b)2 – ab – cd] =

5(a+b)(cd – ab)[a2 + b2 + c2 + d2]/2

Thus a3 + b3 + c3 + d3 = 0 => (a+b) = 0 or cd – ab = 0 =>

a5+b5+c5+d5 = 0 and a5+b5+c5+d5 = 0 =>

(a+b) = 0 or cd – ab = 0 or a2+b2+c2+d2 = 0 => a3 + b3 + c3 + d3 = 0

 Copies of this solution are available from the shelves in front of the Math office, MH 308, or from Professor Jackson’s webpage www.math.sjsu.edu/~jackson .  Two solutions to problem #10 were submitted.  Cuong Dong and Weidong Shao received full credit for their solutions.  In the undergraduate division Cuong Dong is 1st, Weidong Shao is first in the graduate division and Powell Akagawa is first in the San Jose Math Circle division.   

                                                                  10/5/05

Week #7  Wed. Oct. 5 – Fri. Oct. 14 

Problem 7 (11 points):  Prove that there exists an integer A such that for every pair of positive integers n,m such that n,m > A, there is a tiling of an n x m rectangle using only 3 x 5 and 4 x 7 rectangles.       

Solution: For any integer n > 7 (2*4-1) there exist positive integers a,b such that n = 3a + 5b.  For any n > 7, a 15 x n rectangle R can be covered by a 3 x 15 rectangles and b 5 x 15 rectangles.  A 3 x 15 rectangle can be covered by 3 3 x 5 rectangles and a 5 x 15 rectangle can be covered by 5 3 x 5 rectangles, thus R can be covered by 3 x 5 rectangles.  Similarly for any n > 17 (3*6-1), a 28 x n rectangle R can be covered by 4 x 7 rectangles.  Thus for any integers m > 377 (14*27-1) and n > 17 an m x n rectangle R can be covered by 15 x n and 28 x n rectangles, which implies that R can be covered by 3 x 5 and 4 x 7 rectangles.  Therefore if m,n > A = 377 then an m x n rectangle R can be covered by 3 x 5 and 4 x 7 rectangles. 

10/10/05

Week #5  Mon. Sept. 26 – Fri. Sept. 30

Problem 5  (9 points): Let T  be any plane triangle. Construct squares on the edges of T  (external to T ), call these the squares at level 1, and let A1  denote the sum of their areas. Next form the convex hull of the construction so far by adding 3 new line segments (shown as dotted lines), construct squares on these new segments (external to the construction so far), call these the squares at level 2, and let A2  denote the sum of their areas. Prove that the ratio A1/A2  does not depend on T , and determine its value. 

Solution:  Let the side lengths of T  be a , b , and c , and let the respective angle measures opposite these sides be , , and . Let the angles opposite these in the construction have measures , , and , and let the (dotted) lines these angles subtend have respective lengths , , and  (as shown on back), so  and . Then . By the law of cosines, and the fact that supplementary angles have opposite cosines, we have

         

         

         

which implies that   , and also

         

         

         

which implies that     , and so .

 

Week #4  Wed. Sept. 21 – Fri. Sept. 30                  

 Problem 4 (9 points):  Evaluate the limit as n goes to infinity (find the exact value) of the sum 1/(2n+1) + 1/(2n+2) + … + 1/4n . 

 Solution:  We have the limit of the sum 1/(2n+1) + 1/(2n+2) + … + 1/(4n) which is equal to the sum from k = 1 to 2n of  [1/(2+k/n)]/n which is a Riemann sum of the integral from 2 to 4 of dx/x which approaches ln 4 - ln 2 = ln 2 as n goes to infinity. 

Problem #3 (7 points) for the week of September 12, 2005

 Problem:  Let n be a positive integer, and let p be a prime number.  Prove that  implies .

Solution:

If , then the only multiple of p less than n are p, 2p, 3p, …. (p-1)p.  So the exponent p in n! is   p-1.  Hence,  does not divide n!. 

Therefore, if  divides n!, then .  But if , then  divides n!.  In particular,  implies .

9/19/05

Week #2  Mon. Sept. 5 – Fri. Sept. 9

 

Problem 2  (6 points):  There were 5 married couples at a party. One man there asked all 9 of the others there the following question: Before tonight, not counting your spouse, how many of the people here had you met? Surprisingly, he received 9 different answers, no two of the answers he received were the same. What was his wife’s answer?

 

Solution:  We’ll call his wife Mary, and show that Mary’s answer must have been 4. What is unique about Mary is that she’s the only one whose spouse didn’t also give an answer.

   There were 9 answers given, each a number between 0 and 8, and since there were no duplications, each value from 0 to 8 occurred exactly once. Mary couldn’t have answered 8, or else she would have met everyone and no one could have answered 0. In fact, 8 and 0 (i.e. the people who answered 8 and 0) must be married, since everyone had met 8 and only 8’s spouse wouldn’t have counted that.

   Mary couldn’t have answered 7, or else everyone except 0 would have met Mary and 8, so no one could have answered 1. In fact, 7 and 1 must be married, since everyone but 0 had met 8 and 7 and only 7’s spouse wouldn’t have counted meeting 7.

   Mary couldn’t have answered 6. In fact 6 and 2 must be married since everyone but 0 and 1 had met 8, 7, and 6, and only 6’s spouse wouldn’t have counted meeting 6.

   Finally, Mary couldn’t have answered 5. In fact 5 and 3 must be married since everyone but 0, 1, and 2 had met 8, 7, 6, and 5, and only 5’s spouse wouldn’t have counted meeting 5.

   So the only answer left for Mary (the only person whose spouse didn’t also answer) is 4.

                                                                            9/14/05

Week #1  Wed. Aug. 24 – Fri. Sept. 2                  

Problem 1 (5 points):  How many 4-tuples of positive integers {a,b,c,d} are there for which the lowest common multiple of any three integers in the 4-tuple is 3n5m?     

Solution:  Answer: (6m2 + 4m + 1)(6n2 + 4n + 1).  Each of a, b, c, d must be of the form 3h5k with h ≤ m, k ≤ n. We can consider h and k separately. At least two of a, b, c, d must have h = m. So there are three cases: (1) all of a, b, c, d have h = m (1 possibility); (2) three of a, b, c, d have h = m and the other has 0 ≤ h < m (4m possibilities); (3) two of a, b, c, d have h = m and the other two have 0 ≤ h < m (6m2 possibilities). So, in all, there are 6m2 + 4m + 1 possibilities for h. Similarly, there are 6n2 + 4n + 1 possibilities for k. Each of the possibilities for h can be combined with each of the possibilities for k, so in all there are (6m2 + 4m + 1)(6n2 + 4n + 1) possible 4-tuples.