Final
Problem!!
11/20/06
Week #13 Mon. Nov. 20 - Fri. Dec. 1
Problem 13 (25 points) In a
certain competition, a player scores either M or N points at the end of each
round, were M and N are given positive integers. The player notices that her
cumulative score can take any positive integer value except for those in a
finite set P, where |P| =1003. If 60 is
not in P, find M and N.
Solution: For relatively prime integers M,N, it can be shown
that the number of integers not expressible as a linear combination M and N is
(M-1)(N-1)/2. Since (M-1)(N-1) = 2006 =
(2)(17)(59) there are 3 possibilities {M,N} = {2,2007}, {3,1004}, and
{18,119}. Since 60 is not in P then {2,2007}
and {3,1004} are the only solutions.
(The problem was originally intended to state that 60 is in P and then
there would have been a unique solution {18,119}).
11/06/06
Week
#11 Mon. Nov. 6 - Wed. Nov. 15
Problem
11 (15 points) Show that there do not exist positive real numbers x, y, and z,
which satisfy the following system of equations (where a ^ b represents a to
the bth power).
(x + y + z) ^ x =
6/7
(x + y + z) ^ y = 7/8
(x + y + z) ^ z = 8/9.
Solution:
Multiplying the 3 equations we get (x+y+z) ^ (x+y+z) = 6/9 = 2/3. However, the derivative of the function f(a)
= a ^ a is (a ^ a)(ln a + 1), so its minimum occurs at a = 1/e. The minimum is (1/e) ^ (1/e) > 2/3 so no
values of x,y,z satisfying the given equation exist.
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 #11 were
submitted. Cuong Dong, Siddhartha
Kanungo, Sylvie Sundsbarm and Ryan Flarity all received full credit for their
solutions. In the undergraduate
division Cuong Dong, is in 1st, Siddhartha Kanungo is in 2nd, and Paul
Craciuniou is in 3rd, in the graduate division, Ryan Flarity is in 1st,
Ivan Zaigralin is in 2nd, and Helene Payne is in 3rd, in
the SJMC division Sahana Vasudevan is in 1st.
10/30/06
Week #10
Mon. Oct. 30 - Wed. Nov. 8
Problem
10 (14 points) Is it possible to inscribe a triangle with angles of 45 degrees,
60 degrees, and 75 degrees in a unit circle (x ^2 + y ^ 2 = 1) so that each
vertex of the triangle has rational coordinates?
Solution:
It is not possible. More generally, no
triangle with a 60 degree angle can be inscribed in the unit circle so all the
vertices have rational coordinates.
Otherwise, let P1P2 be the side of the triangle opposite the 60 degree
angle, and suppose Pi has rational coordinates (xi,yi), for i = 1,2. Since P1P2 subtends a central angle of 120
degrees in a unit circle we have dist(P1,P2) = (3) ^ .5, or (x1 - x2) ^ 2 + (y1
- y2) ^ 2 = 3. We may express the
rational numbers x1 - x2, y1 - y2 as x/n, y/n respectively, where x, y, n are
integers with no common divisor > 1.
Then x ^ 2 + y ^ 2 = 3(n ^ 2), and so 3 | x ^ 2 + y ^ 2. Thus 3 | x and 3 | y . This in turn implies 3 ^ 2 | x ^ 2 + y ^ 2
or 3 | n. But 3 | x, y, n contradicts
the assumption that x,y, and n had no common divisor > 1.
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 . Three solutions to problem #10 were
submitted. Cuong Dong, Siddhartha
Kanungo, and Ryan Flarity received full credit for their solutions. In the undergraduate division Cuong Dong, is
in 1st, Siddhartha Kanungo is in 2nd, and Paul Craciuniou is in 3rd,
in the graduate division, Ivan Zaigralin is in 1st, Ryan Flarity is
in 2nd, and Helene Payne is in 3rd, in the SJMC division
Sahana Vasudevan is in 1st.
10/23/06
Week #9 Mon. Oct. 23 - Wed. Nov. 1
Problem 9
(13 points) For all positive integers m,n show that
[(3m)!(3n)!]/[m!n!(m+n)!(n+m)!] is always an integer.
Solution: (by Cuong Dong) Let [x] represent the greatest integer less than or equal to
x. For every prime p we need to show
that the number of p's in (3n)!(3m)! is at least as large as the number of p's
in n!m!(m+n)!(n+m)!. For any integer q,
the number of p's in q! is [q/p] + [q/p^2] + [q/p^3] + ... . For every pair of reals a,b it suffices to
show that [3a] + [3b] >= [a] +[b] + 2[a + b]. Let u and v be the fractional parts of a and b respectively, thus
a = [a] +u and b = [b] +v. It suffices
to show that [3u] + [3v] >= 2[u + v].
There are two possibilities [u + v] = 0 and [u + v] = 1. In the first case it is clear that [3u] +
[3v] > = 0. If [u + v] = 1 then 3u +
3v >= 3, [3u+3v] >= 2 = 2[u+v].
Thus the result holds.
10/17/06
Week #8 Mon. Oct. 16 - Wed. Oct. 25
Problem 8
(12 points) A certain island has x red, y blue, and z yellow chameleons, where
x,y,z are positive integers. Whenever
two chameleons that are different colors meet, they can both change their color
to the third color. For which triples
(x,y,z) of positive integers could all the chameleons ever end up being the
same color.
Solution: The chameleons could all become the same
color if and only if two of x,y,z are congruent modulo 3. If x,y, and z are all different modulo 3,
this will never change as color exchanges occur, and they could never all be
the same color. If say x and y are
equal modulo 3, the chameleons could all become one color, as we now show. If x >= y, do the following (x-y)/3
times: Change a (red,blue) pair to yellow, and then a (red,yellow) pair to
blue. We will then have
(red,yellow,blue) = (x - 2(x-y)/3, y + (x - y)/3, z + (x-y)/3) = (x/3 + 2y/3,
x/3 + 2y/3, z + (x-y)/3). Now red =
blue and we can change all the chameleons to yellow.
10/25/06
Week #7 Mon. Oct. 9 - Wed. Oct. 18
Problem 7 (11 points) Let n^4 represent the 4th power of n. Determine all non-negative integral solutions of (n1, n2, n3, ... , n14), if any, of the Diophantine equation
(n1)^4 + (n2)^4 + ... + (n14)^4 = 1,599.
Solution: There are no
solutions. For any even integer n, n ^
4 is congruent to 0 mod 16, and for any odd integer n, n ^ 4 is congruent to 1
mod 16. Thus (n1)^4 +
(n2)^4 + ... + (n14)^4 is congruent to
either 0,1,2, ... , or 14 mod 16 while 1599 is congruent to 15 mod 16. Thus the two values cannot be equal.
10/17/06
Week #6 Mon. Oct. 2 – Wed. Oct. 11
Problem 6 (10 points) Does there exist a continuous function f: R -> R such that the image of every rational number is irrational and the image of every irrational is rational.
Solution: No. Otherwise, since f(Q) is countable and f(R -
Q) C Q is countable, the range of f would be countable. But by the Intermediate Value Theorem, the
range of a continuous function taking on two or more values, must also take on
every value in between, so its range is uncountable. Since f takes on at least one rational value and one irrational
value, its range is uncountable contradicting the assumption. Thus no such function f can exist.
Week #5 Mon. Sept.
26 – Wed. Oct. 4
Problem 5 (9 points) If P(x) denotes a polynomial of degree
n such that P(k) = k/(k+1) for k = 0, 1, 2, ..., n, determine P(n+1).
Solution:
Let Q(x) = (x+1)P(x) - x. Since Q(x) is a polynomial of degree n+1 which
vanishes for x = 0, 1, 2, ... , n, we must have Q(x) = (x + 1))P(x) - x =
Ax(x-1)(x-2) ... (x-n), for some constant A.
By setting x = -1 we see that 1 = A[(n+1)!](-1)^(n+1). Thus P(x) = (x + (-1)^(n+1) [x(x-1)(x-2) ...
(x-n)]/(n+1)!)/(x+1), which means P(n+1) = 1 or n/(n+2), depending on whether n
is odd or even.
10/03/06
Week
#4 Mon. Sept. 19 – Wed. Sept. 27
Solution: Let S denote the rate of snowfall in inches per hour, let c denote the rate of snow removal, in inch-miles per hour, with the snowfall starting h hours before noon. At time t hours after noon, the depth of the snow is s(h + t), and the rate of advance is v_t proportional to c/s(h+t), for some constant c. Then the distance from the town at time t hours will be d_t, which equals the integral of v_t with respect to t from 0 to t. Thus d_t = [c/s](ln(h+t) - ln(h)). Since we are told d_2 = 2 and d_4 = 3, we have 3 = d_4 = [c/s](ln(h+4)-ln(h)) = [c/s]ln(1+4/h) and 2 = d_2 = [c/s](ln(h+2)-ln(h)) = [c/s]ln(1+2/h). Then ln(1+4/h) = 3/2ln(1+2/h), or (1+4/h)^2 = (1+2/h)^3. Setting y = 2/h > 0, we obtain y(y^2 - y - 1) = 0, and thus y = [1 + 5^(1/2)]/2. So h = 2/y = 4/(1 + 5^(1/2)) = 5^(1/2) - 1. Thus it started snowing 5^(1/2) - 1 (approximately 75 minutes before noon.
9/25/06
Week
#3 Mon. Sept. 11 – Wed. Sept. 20
Problem 3 (7 points) Given a set of 1004 integers between 1 and 2006
(inclusive), show that at least one member of the set must divide another
member of the set.
Solution: Let S be a set of 1004 integers chosen from
{1,2,3, ...,2006}. Every integer in S
can be represented uniquely as an odd number times a power of 2. The odd number can only take on one of 1003
possible values {1,3,5, ... ,2005}.
Thus there are two integers i1, i2 in S that are of the form i1 = (2 ^
j1) o, i2 = (2 ^ j2) o, for the same odd integer o. Of these two integers either i1 | i2, if j1
< j2 or i2 | i1, if j2 < j1.
9/18/06
Week #2
Tues. Sept. 5 – Wed. Sept. 13
Problem 2 (6 points) There is a plane with n > 1 seats, and lined up to
board are n passengers, each of whom has an assigned seat. The first passenger,
who has amnesia and cannot remember his assigned seat, sits in a random seat.
Thereafter, as each person in line boards the plane, they look to see if their
assigned seat is available. If it is, they sit in it. If it is not, they sit in
a random open seat. What is the probability that the last person to board sits
in his/her assigned seat?
Solution: Let An be
the probability for n passengers and let P1, P2, ... ,Pn denote the passengers
in line from first to last. If P1 sits
in the seat assigned to Pj then 1) if j = 1, then Pn sits in their assigned
seat with probability 1, 2) if j = n, then Pn sits in their assigned seat with
probability 0, 3) 1 < j < n, then P2, P3, ... ,Pj-1 all sit in their
assigned seats and Pj selects a seat at random so Pn will sit in their assigned
seat with probability An-j+1. Since j
is randomly chosen in {1,2, ... ,n} then An = (1 + An-1 + An-2 + ... + A2 +
0)/n. Thus An = 1/2 for all n >
1.
8/15/06
Week #1 Wed. Aug. 23
– Wed. Sept. 6
Problem 1 (5 points):
The combined ages of Mary and Ann are sixty years, and Mary is twice as
old as Ann was when Mary was half as old as Ann will be when Ann is three times
as old as Mary was when Mary was three times as old as Ann. How old is Mary?
Solution: Working
backwards,
1) when Mary was 3 times as old as Ann
Mary's age = 3d, Ann's age = d
2) when Ann is 3 times as old as Mary was
Mary's age = 11d, Ann's age = 9d
3) when Mary was half as old as Ann will be
Mary's age = 4.5d, Ann's age = 2.5d
4) Mary is twice as old as Ann was
(present ages) Mary's age = 5d, Ann's age = 3d
5d + 3d = 60, so d = 7.5 years, and Mary's age is 37.5
years.