10/30/07 

Week #10  Mon. Oct. 22 - Fri. Oct. 26  

Problem 10 (14 points) 

A regular n-gon, with vertices v1,v2, ... , vn, is inscribed in a circle of radius 1.  Vertex v1 of the n-gon is then joined by a line segment to each of the other n-1 vertices.  Show that the product of the lengths of these line segments |v1 v2| |v1 v3| ... |v1 vn| is equal to n.  

Solution: Place the circle in the complex plane with its center at the origin and v1 at (1,0). Let a = e^2pi/n , so that the other vertices of the n-gon are at a, a² , ... ,a^n-1. If l_j = |1 - a^j|, the product of the lengths of the segments is l₁*l₂* ... *l_n-1 = |1 - a¹| |1 - a²| ... |1 - a^n-1| = (1 - a¹) (1 - a²) ... (1 - a^n-1), where the last equality follows from the fact that the product is real, since (1 - a^k) and (1 - a^n-k) are complex conjugates. Consider the function f(z) = zⁿ - 1 = (z - 1)(z^n-1 + ... + z + 1) = (z-1)(z - a)(z - a²) ... (z - a^n-1). Thus (z - a)(z - a²) ... (z - a^n-1) = z^n-1 + ... + z + 1 holds for all z Î C. Setting z = 1 gives (1-a)(1-a²) ... (1-a^n-1) = 1 + 1 + ... + 1 = n as asserted.

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 . Four solutions to problem #10 were submitted. Cuong Dong, Siddhartha Kanungo, Michael Pejic, and Ryan Flarity, all received full credit for their solutions.

10/25/07 

Week #9  Mon. Oct. 22 - Fri. Oct. 26  

Problem 9 (13 points) 

Suppose that 2007 points are chosen at random in a square that is 20 inches x 20 inches.  Show that it is always possible to choose three of the points, which form a triangle (possibly degenerate) whose perimeter is less than 3.  

Solution: Subdivide the square into 900 2/3 x 2/3 squares. Since 2007 > 2 x 900 then some square contains at least 3 of the 2007 points. The diameter of the 2/3 x 2/3 square is 2/3 Ö2 < .95. The perimeter of the triangle formed by 3 points in this square is less than 3 x .95 < 3.

10/17/07 

Week #8  Mon. Oct. 15 - Fri. Oct. 20  

Problem 8 (12 points) 

Let S be any set of 7 different integers chosen at random.  Show that S always has a subset of 4 integers whose sum is divisible by 4.  

Solution: From the seven integers select any three. Two of these say x1, x2 have an even sum. Remove x1, x2 from the set. From the remaining 5, select any three, and let y1,y2 be two of these with an even sum. Remove y1,y2, leaving three remaining integers. Then two of the last three z1, z2 have an even sum. Two of x1+x2, y1+y2, z1+z2 must have the same remainder mod 4 and the sum of these four integers will be divisible by 4.

Week #6  Mon. Oct. 1 - Fri. Oct. 5  

Problem 6 (10 points) 

Determine the smallest positive integer of the form 33^a - 7^b, where a and b are positive integers.

Solution: The value 26 is obtained when a = b = 1. We will show that 26 is the smallest. Note that 33 º 1 (mod 16) so 33^a º 1 (mod 16) for any positive integer a. Also note that 7^b º 7 or 1 (mod 16) so 33^a - 7^b º 0 or 10 (mod 16). So the only possible minimum values are 10,16, or 26. But 33 º 0 (mod 3) and 7 º 1 (mod 3), therefore 33^a - 7^b º 2 (mod 3). Thus leaves 26 as the only possible minimum value.

10/10/07

Corrected Version! 9/28/07  

Week #5  Mon. Sept. 24 - Fri. Sept. 28  

Problem 5 (9 points) 

Let f(n) be a function defined for all positive integers n which takes on only nonnegative integer values. In addition, suppose that

f(m + n) - f(m) - f(n) = 0 or 1 for all positive integers m,n. If f(2) = 0, f(3) > 0 and

f(9999) = 3333, determine f(2007).  

Solution: f(3) > 0 but f(3) = f(2) + f(1) + 0 or 1 so f(3) = 1. Also f(3n) ³ nf(3) = n since f(n+m) ³ f(n) + f(m) for all positive integers m,n. Since f(9999) = 3333, if f(3m) > m for some m < 3333, then this implies that f(9999) > 3333. Thus f(3m) = m for all m < 3333. Therefore f(2007) = 2007/3 = 669.

10/02/07

Week #4  Mon. Sept. 17 - Fri. Sept. 21  

Problem 4 (8 points) 

Two players play a game by taking turns rolling a fair n-sided die (each number 1,2, ... ,n is equally likely to occur).  On each roll a player who fails to roll a number higher than every previous number that has appeared, loses the game.  What is the probability that the second player wins the game?   

Solution: After k rolls, the probability that the game continues will be C(n,k)/n^k. The probability that player 2 wins on roll k (k odd) is given by C(n,k-1)/n^k-1 - C(n,k)/n^k. The total probability that player 2 wins is S_{k odd} C(n,k-1)/n^k-1 - C(n,k)/n^k =

S_{0 £ k £ n} C(n,k)(-1/n)^k = (1 - 1/n)ⁿ

09/25/07

Week #3  Mon. Sept. 10 - Fri. Sept. 14  

Problem 3 (7 points) 

Let f(x) = exp(x²).  Find an open interval I and a non-zero function g(x) on I such that (fg)' = f'g' on I, or prove that they do not exist.  

Solution: If [exp(x²)g(x)]' = 2xexp(x²)g'(x) = 2xexp(x²)g(x) + exp(x²)g'x) then

(2x-1)exp(x²)g'(x) = 2xexp(x²)g(x) Þ g'(x)/g(x) = 2x/(2x-1) Þ g(x) = k(2x-1)^1/2 for x > 1/2. Thus g(x) = (2x-1)^1/2 on (1/2,¥) satisfies the conditions of the problem.

09/18/07

Week #2  Mon. Sept. 3 - Fri. Sept. 7  

Problem 2 (6 points) 

A spherical ball is placed on the interior of the surface (paraboloid) defined by the equation z = x² + y².  The ball is then rolled toward the vertex of the paraboloid (0,0,0). What is the largest diameter of a ball that will be able to reach the vertex without getting stuck?

Solution: A circle through the origin with center on the positive y-axis has equation x² + (y-r)² = r², r > 0. It intersects the parabola y = x² at points x for which x² + (x²-r)² = r², or x²(x² - (2r-1)) = 0. So there will be three distinct intersection points and the ball will get stuck if 2r-1 > 0, or r > 1/2. Thus if r £ 1/2, the only intersection will be the point of tangency at the bottom, and the ball will roll all the way down.

09/11/07

Week #1  Mon. Aug. 27 - Fri. Aug. 31  

Problem 1 (5 points) Let d(0), d(1), d(2), ... be a sequence of decimal integers defined as follows: d(0) = 0; d(1) = 1; and for n > 1, d(n+2) is obtained by writing the digits of d(n+1) immediately followed by those of d(n).  Thus d(2) = 10, d(3) = 101, d(4) = 10110, and so on.  For which values of n is d(n) divisible by 11.  

Answer: The decimal integer a_n is divisible by 11, when n º 1 (mod 6). Recall that if n = d_md_m-1...d₁d₀, where the d_i are decimal digits, then the remainder of n divided by 11 is f(n) = (d₀ + d₂ + ... ) - (d₁ + d₃ + ... ). It is easy to show that a_n has an odd number of digits unless n is a multiple of 3. Hence f(a_n) = -f(a_n-1) + f(a_n-2) unless n º 2 (mod 3) when f(a_n) = f(a_n-1) + f(a_n-2). A simple induction shows that f(a_n) = 1 for n = 0, 2, 5 (mod 6), -1 for n = 3 (mod 6), 2 for n = 4 (mod 6), and 0 for n = 1 (mod 6).