Final
results!
12/01/04
Week
#13 Wed.
Nov. 17 – Mon. Nov. 29
Problem
13 (25 points):
We are given 3 dice, each with n faces, whose faces are numbered
identically with arbitrary integers. If the dice are tossed at random, prove
that the probability P that the sum of the numbers on the three bottom faces is
divisible by three is greater than or equal to 1/4.
Solution:
Let x,y, and z be the probabilities that a number congruent to 0,1, or 2 modulo
3 appears when a die is rolled.
To get a sum that is a multiple of 3, all three number have the same
modulus or they all have different moduli.
Thus the probability that the sum is divisible by 3 is P = x3
+ y3 + z3 + 6xyz.
We want to show that P ³
¼ given that x + y + z = 1 and x,y,z ³
0. Note
that P = (x + y + z){(x+y+z)2 – 3(yz + zx + xy)} + 9xyz = 1 –
3(yz + zx + xy) + 9xyz.
Also P ³
¼ =>
1 + 12xyz ³
4(yz + zx + xy) => 1 + 4yz(3x-1) ³
4(zx + xy) = 4x(1-x).
Without loss of generality we can assume x ³ y ³
z => x ³ 1/3 => 1 + 4yz(3x-1) ³ 1 and since 1 ³
4x(1-x) we see that 1 + 4yz(3x-1) ³
4x(1-x).
Thus P ³
¼.
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.
Seven solutions to problem #13 were submitted.
Only one person Cuong Dong received full credit for their solution.
The final results of the 2004 Problem of the Week competition are given
below. Winners
should make sure that the math office (MH 308) has their correct student ID
number. Checks
for the winners can be picked up at the beginning of the spring semester.
The Problem of the Week Competition will start up again in the Fall of
2005.
The solution to problem #12 will be available on Wed. Nov. 24.
11/17/04
Week
#11 Wed. Nov. 3 – Fri. Nov. 12
Problem
11 (15 points): Denote by an=
lcm{b1,b2,b3, … ,bn}, n ³ 1, the least common multiple of the first n
terms of a strictly increasing sequence of positive integers 0 < b1
< b2 < b3 … .
Prove that the series 1/a1 + 1/a2 + 1/a3
+ … + 1/an + … converges to a finite sum.
Solution:
For any positive integer n, at least half of the divisors of n are less than or
equal to Ö
n . Thus the number of positive
divisors of n is at most 2Ö
n . Since an is the
least common multiple of n distinct positive integers it has at least n positive
divisors. Thus 2Ö an
³
n and an ³ n2/4. Therefore, S
1/an is dominated by the convergent series S
4/n2 and is itself convergent.
Solution:
Since
the equation of the circle k is
, it follows that if a point
lies on k, so do all the points of the
form
If
, all 8 of these points are distinct. If either
or one of the numbers
equals 0, then there are exactly 4 distinct points of the form
. Since the remainder of 2004 upon division by 8 is 4, it follows that among the
lattice points on the circle k there exists a point
of the second type. If
then R is an integer, since
. If
, then
is an integer, since
, so that
, and thus
.
Note: A circle containing
exactly 2004 points does exist. It is known that the number n(r) of different
integer solutions (x, y) of the equation
, where r is a natural number,
is equal to
where p (respectively, q) is the number of different divisors of
of the form
(respectively, of the form
). If we take
, then
.
Problem
9 (13 points): A candidate
schedules a series of campaign speeches during n consecutive hours.
Speech A lasts 1 hour, Speech B lasts 2 hours, and he can also schedule
rest periods of 1 or more hours. Assuming
that no more than 3 consecutive hours of speeches can be scheduled, find a
recurrence relation for an, the number of different schedules of
speeches and rests for n consecutive hours.
How many schedules are there for a period of 24 consecutive hours?
Solution:
A schedule of n hours can 1) start with a rest followed by any allowable
schedule of n-1 hours, 2) start with Speech A followed by a rest and then any
allowable schedule of n-2 hours, 3) start with AA or B followed by a rest and
then any allowable schedule of n-3 hours, or 4) start with AAA, AB, or BA
followed by a rest and then any allowable schedule of n-4 hours.
Thus an = an-1 + an-2 +2an-3
+ 3an-4 , with the initial conditions a0 = 1, a1
= 2, a2 = 5, and a3 = 12.
Thus a24 = 135,709,072.
Problem
8 (12
points) Let DABC
be a triangle, and let AK
be the bisector of the angle ÐBAC
(so that the point
K
lies on the side BC).
Find the angles of the DABC if it is known that the center of the circle inscribed in the
DABK
and the center of the
circle circumscribed about the DABC
coincide.
Solution:
Let
us denote the common center of the two circles by O, and let a
denote the measure of the ÐBAO.
Since O
is the center of the circle inscribed in DBAK,
so AO
and BO are bisectors of the angles
BAK and ABK, respectively. Since AK is
the bisector of the angle BAC, we have
ÐBAC
= 2ÐBAK
= 4ÐBAO
= 4a.
Now, BO = AO = CO
(as radii of the circle circumscribed about the triangle
ABC), and hence the triangles BOA, BOC,
and CAO
are isosceles.
Therefore,
ÐABO = ÐBAO =
a,
ÐBCO
= ÐOBC = ÐABO = a, (ÐOBC = ÐABO
because BO is the bisector of the
angle ABC) and ÐOCA
= ÐOAC
= 3a.
Therefore, ÐABC
= 2a,
ÐBCA
= 4a.
Hence
ÐBAC
+ ÐABC
+ ÐBCA
= 4a
+ 2a
+ 4a
= 10a
= 180°,
And
so a
= 18°. Thus ÐBAC =
ÐBCA = 72°,
and ÐABC
= 36°.
Week
#7 Wed.
Oct. 6 – Fri. Oct. 15
Problem
7 (11 points):
Let N = 87654321 be written in decimal notation.
If A is the sum of the digits of N and B is the sum of the digits of A,
then what is the sum of the digits of B.
Solution:
Note that N = 87654321 £
(104)4321 so A has at most 4(4321) = 17284 decimal digits.
Thus A £
9(17284) £
180,000. Since
A has no more than 6 digits, B £
6(9) = 54. Thus
the sum of the digits of B is no more than 4 + 9 = 13.
Since 8765 º
8 + 7 + 6 + 5 º
8 º
-1 mod 9 then 87654321 º
-1 º
8 mod 9. Therefore
the sum of the digits of B is 8.
Week
#6 Wed.
Sept. 29 – Fri. Oct. 8
Solution:
Let
d
denote the greatest common divisor
(GCD) of the numbers
. Then
, where
are natural numbers. By the
conditions of the problem
, and hence d
is a divisor of 1001. Since
, so
, and therefore
. Since 1001 = 7∙11∙13, the largest divisor of 1001 not exceeding
100 is 91 = 7∙13. Thus
. Now we must show that
. This is clear since
1001
= 91∙9 + 182, and so that we can take
.
Hence the largest possible value of the GCD is 91.
Week
#5 Wed. Sept. 22 – Fri. Oct. 1
Problem
5 (9 points): Prove for any
positive integer n that 2196n – 25n – 180n
+ 13n is divisible by 2004.
Solution:
Note that 2004 can be factored into two relatively prime factors, 2004 = 167 x
12. For any integers a,b, an
- bn = (a – b)(an-1 +
an-2b + … + abn-2 + bn-1). Thus
(a-b) divides (an – bn).
Since 12 divides 2196 – 180 = 2016 = 12 x 168, then 12 divides 2196n
– 180n. Also 12
divides 25 –13 = 12 = 12 x 1, thus 12 divides – 25n + 13n
= -(25n - 13n). Also
167 divides (2196 –25) = 13 x 167 hence 167 divides 2196n – 25n.
Similarly 167 divides (180 –13) which implies that 167 divides (-180n
+ 13n) = -(180 – 13n).
Since 12 and 167 are relatively prime and both divide 2196n
– 25n – 180n + 13n then 2004 divides 2196n
– 25n – 180n + 13n.
Problem 4
(8 points) Suppose that
x
and y
are two real numbers such that
|
|
Prove that
|
|
Solution:
Suppose x
< y. Then
2x
< 2y, and hence
x
+ 2x < y + 2y. Likewise, if x
> y, then x + 2x
> y + 2y..
Therefore,
x = y, and hence clearly
x + sin x = y + sin y.
**************************************************
9/22/2004
Week
#3 Wed. Sept. 8 – Fri. Sept. 17
Problem
3 (7 points): A woman can walk up a
moving “up” escalator in ½ minute. She can walk down this moving “up”
escalator in 1 and ½ minutes. If
her walking pace is the same moving up stairs or down stairs, how long would it
take her to climb the escalator stairs if it was not moving? How long would it take her to go up the moving “up”
escalator if she stood still?
Solution:
In 3 minutes the woman can walk down 1 moving escalator and up 3 moving
escalators, covering a total of four escalator lengths, half the time moving up
and half the time moving down. This
is her walking pace, 4 escalator lengths in 3 minutes. She can thus climb the still escalator in ¾ minutes = 45
seconds. In the 1.5 minutes
required to walk down the moving “up” escalator she walks the equivalent of
2 still escalators. Therefore the
escalator must have moved up once in that time and its speed is 1 length in 1.5
minutes.
Problem
2 (6 points) An alphabet
consists of n
letters. Find (with a proof) the length of a longest word that
satisfies the following two conditions.
(a)
Any two adjacent letters of this word are distinct;
(b)
It is impossible to reduce this word, by means of crossing out any number
of letters, to a form xyxy, where
x
and y
are any two distinct letters of the alphabet.
Solution:
Let w be a word. Let us say
that a letter x is of the
first kind if it occurs in w exactly
once, and that it is of the second kind
if it occurs in w more than once. Let
us also call a word admissible if it
satisfies the conditions (a) and (b).
(i)
The two letters adjacent to a letter of the second kind must be distinct,
for otherwise the condition (b) will be violated.
(ii)
If the word contains at least two different letters, then it contains at
least one letter of the first kind. Again, if it were not the case, then the
word would not satisfy the condition (b), i.e., it would be possible to get from
it a word of the form xyxy after the
rest of the letters have been crossed out.
We will now prove, by the method of mathematical induction, that for any
admissible word w,
where m is the number of distinct
letters in w.
If m
= 1, then any admissible word w
consists of exactly one letter, due to condition (a). Hence
, and our statement is true.
Suppose now that the
statement is true for a certain
, i.e.,
for every word w
with k distinct letters in it; we have to prove that
for every word w that contains (k
+ 1) distinct letters.
Let
w contain (k +1) distinct letters. By (ii), there is a letter of the first
kind. Without loss of generality, let it be a,
and suppose that b is an adjacent
letter. If b
is of the first kind, then by crossing
b out we obtain a new
admissible word
, and since the number of distinct letters in
is k,
so
, and hence
If b is of the second kind, then either two letters adjacent
to the pair ab (or ba) are distinct, or there is only one adjacent letter, so that this
pair is located at one of the ends of the word w (for otherwise condition (b) will be violated). In either case, if
we cross this pair out, we get a new admissible word
. This word, again, has only k distinct letters, and so
. Thus
.
Therefore,
for any word with m
distinct letters, where m is any
positive integer. In fact, it is clear that this inequality holds for any word
with at most m distinct letters. Since
the alphabet contains exactly n
letters, we have proved that
for any admissible word.
On
the other hand, let the alphabet consist of the letters
.
Let w be the word
. Obviously, this word is admissible, and its length is
.
Therefore, the length of the longest admissible word is
.
Week
#1 Wed. Aug. 25 – Fri. Sept. 3
Problem
1 (5 points): Between 3:00 and
4:00, Big Ben looked at his watch and noticed that the minute hand was between 5
and 6. Later, Big Ben looked again
and noticed that the hour hand and the minute hand had exchanged places.
What time was it in the second case?
Solution: Between 3:00 and 4:00, if X is the position of the minute hand then the position of the hour hand is 15 + X/12. Between 5:00 and 6:00, if Y is the position of the minute hand then the position of the hour hand is 25 + Y/12. Since the hands have changed places, we have 15 + X/12 = Y and 25 + Y/12 = X. Solving for Y gives us that 15 + (25 + Y/12)/12 = Y -> 15(144) + 25(12) + Y = 144Y -> 2460 = 143Y -> Y = 17 and 29/143. Therefore the time in the second case was 5:17 and 29/143 minutes. Full credit was only given for the exact answer.
