Berkeley Math Circle - Monthly Contests - Problems (1999-00)
Berkeley Math Circle - Monthly Contests - Problems (1999-00)
Berkeley Math Circle - Monthly Contests - Problems (1999-00)
DUE 10/10/99
1. Let k and n be positive integers such that k < 2n+1 − 1. Prove that there is
a sum of exactly n powers of 2 that is divisible by k. (Example: if k = 9 and
n = 4, then 2 + 4 + 16 + 32 is divisible by 9.)
2. Ten tourists visiting a tropical island are captured by one of the natives, who
happens to be a cannibal. The cannibal explains to them that it is the custom
on his island to give prisoners a test before eating them. Tomorrow he will
line them up in single file, and he will place a black or white hat on each of
them, so that each tourist can see only the colors of the hats of the tourists
ahead in the line. Then, starting from the rear of the line, the cannibal will
ask each tourist to guess the color of his hat, based on the colors of the hats
ahead, and based on any earlier guesses that were made by tourists behind
him. (The tourists are not allowed to signal each other in any other way.) If
a tourist names the wrong color, the cannibal silently eats that tourist before
moving on to the next. At the end, any uneaten tourists are freed. Show that
if the tourists are allowed to plan a strategy the night before they are tested,
they can guarantee that at least nine of them will escape.
3. Let n be an integer greater than 2. Positive real numbers x and y satisfy
xn = x + 1 and y n+1 = y 3 + 1. Prove that x < y.
4. Let z = cos 2π/n + i sin 2π/n where n is a positive odd integer. Prove that
1 1 1 1 n
+ + + ··· + = .
1+z 1 + z2 1 + z3 1 + zn 2
5. An apple is in the shape of a ball of radius 31mm. A worm gets into the
apple and digs a tunnel of total length 61mm, and then leaves the apple.
(The tunnel need not be a straight line.) Prove that one can cut the apple
with a straight slice through the center so that one of the two halves is not
rotten.
Please write solutions to different problems on separate pages. At the top of each
page, write your name, school, city, contest number, and problem number. Please go
to http://www.math.berkeley.edu/~stankova/MathCircle/Joyce/index2.html
for more information about the contest.
Berkeley
c Math Circle
Please write solutions to different problems on separate pages. At the top of each page,
write your name, school, city, contest number, and problem number. Remember that these
problems are not to be discussed with anyone until after the due date. Please go to
http://www.math.berkeley.edu/~stankova/MathCircle/Joyce/index2.html
for more information about the contest.
Berkeley
c Math Circle
1. Given are n+1 real linear equations in n variables (of the form a1 x1 +a2 x2 +· · ·+an xn =
a). Prove that each = sign can be replaced with either ≤ or ≥ so that the resulting n+1
inequalities have the following property: for every choice of real numbers x1 , x2 , . . . , xn ,
at least one inequality is true.
2. Let m, n be positive integers. Suppose that a given rectangle can be tiled (without
overlaps) by a combination of horizontal 1 × m strips and vertical n × 1 strips. Show
that it can be tiled using just one of the two types.
3. The set S is a finite subset of [0, 1] with the following property: for all x ∈ S, there
exist a, b ∈ S ∪ {0, 1} with a, b 6= x such that x = (a + b)/2. Prove that all the numbers
in S are rational.
4. Certain cities are connected by roads connecting pairs of them. The roads intersect
only at the cities. A subset of the roads is called important if destroying those roads
would make it so that there are two cities such that it is impossible to go from the first
to the second. A subset S of the roads is called strategic if it is important and if no
proper subset of S is important. Let S and T be distinct strategic sets of roads. Let U
be the set of roads that are in either S or T , but not both. Prove that U is important.
5. Let ABCDEF be inscribed in circle k so that AB = CD = EF . Assume that diagonals
AD, BE, CF intersect in point Q, and let P = AD ∩CE. Prove CP/P E = AC 2 /CE 2 .
Please write solutions to different problems on separate pages. At the top of each page,
write your name, school, city, contest number, and problem number. Remember that these
problems are not to be discussed with anyone until after the due date. Please go to
http://www.math.berkeley.edu/~stankova/MathCircle/Joyce/index2.html
for more information about the contest.
Berkeley
c Math Circle
1. Let g1 (x), g2 (x), . . . , g5 (x) be polynomials with integer coefficients. Suppose that their
product f (x) = g1 (x)g2 (x)g3 (x)g4 (x)g5 (x) satisfies f (1999) = 2000. Prove that for
some i ∈ {1, 2, 3, 4, 5}, the sum of the coefficients of gi (x) is odd.
2. Let d be a fixed positive integer. Prove that there exists a unique polynomial S(n) such
for every integer n ≥ 0,
Xn
S(n) = k d = 0d + 1d + · · · + nd .
k=0
(Hint: solve for the coefficients of a polynomial S(n) that satisfies S(n) − S(n − 1) =
something.) Also prove that S(n) can be expressed in the form
c0 + c1 (2n + 1) + c2 (2n + 1)2 + · · · + cd+1 (2n + 1)d+1 ,
where the ci are rational numbers such that ci ci+1 = 0 for i = 0, 1, . . . , d.
3. On the sides of a convex quadrilateral ABCD, construct squares externally. Prove that
the quadrilateral with vertices at the centers of the squares has equal and perpendicular
diagonals.
4. Let P (x) be a polynomial with integer coefficients. Let a0 = 0 and for i ≥ 0 define
ai+1 = P (ai ). Prove that gcd(am , an ) = agcd(m,n) for any integers m, n ≥ 1.
5. Acute triangle ABC is made of solid metal, and it is on top of a wooden table. Points
P on AB and Q on AC are such that the perpendicular to AB through P intersects the
perpendicular to AC through Q inside the triangle. Nails are hammered into the table
at P and Q. (The nails do not go through the triangle, but are at its edges, bounding
the triangle.) Prove that there is a unique position R on BC such that if a nail is
hammered into the table at R, the triangle will no longer be able to move (within the
plane of the table).
Please write solutions to different problems on separate pages. At the top of each page,
write your name, school, city, contest number, and problem number. Remember that these
problems are not to be discussed with anyone until after the due date. Please go to
http://www.math.berkeley.edu/~stankova/MathCircle/Joyce/index2.html
for more information about the contest.
Berkeley
c Math Circle
(1) Equilateral triangle ABC is inscribed in a circle. Let D be the midpoint of AB,
−−→
and let E be the midpoint of AC. The ray DE meets the circle at P . Prove that
DE 2 = DP · P E.
(2) Prove that there are infinitely many terms in the arithmetic progression
8, 21, 34, 47, . . .
which consist entirely of 9’s.
(3) Let p(x) be a polynomial of degree exactly 3, with real coefficients. For each real
number a, let qa (x) be the unique polynomial of degree 2 or less such that p(x)−qa (x)
is divisible by (x − a)3 . Prove that for a 6= b, the graphs of qa (x) and qb (x) do not
intersect. Can you find a generalization to polynomials p(x) of odd degree?
(4) Find the minimum of the function f (x, y)
p p p
f (x, y) = (x + 1)2 + (2y + 1)2 + (2x + 1)2 + (3y + 1)2 + (3x − 4)2 + (5y − 6)2 ,
defined for all real x, y > 0.
(5) Let O be the center of a circle k. Points A, B, C, D, E, F on k are such that triangles
OAB, OCD, OEF are equilateral. Let L, M , N be the midpoints of BC, DE, F A,
respectively. Prove that triangle LM N also is equilateral.
Please write solutions to different problems on separate pages. At the top of each page,
write your name, school, city, contest number, and problem number. Remember that these
problems are not to be discussed with anyone until after the due date. Please go to
http://www.math.berkeley.edu/~stankova/MathCircle/Joyce/index2.html
for more information about the contest.
Berkeley
c Math Circle