Math 199  Problem Solving and Putnam Preparation
Spring 2000
Geoff
Mess, Terry Tao, Christoph
Thiele
Homework is due Tuesday June 13th! Please hand in your assignments
to any one of the three lecturers.
This course is intended for math undergraduates interested in mathematical
problem solving, and also as training for those of you who are interested
in participating in the
Putnam competition next December. This course is quite different
from the regular math courses offered at UCLA, which are focussed on a
single branch of mathematics and specific types of applications.
This course is less formal, and emphasizes problem solving, creative thought,
and exposition skills rather than learning theory or specialized techniques
for solving specific problems.
We meet weekly. At each session we discuss one or two interesting
mathematical problems. Generally, these problems require some thought
and ingenuity to solve, and usually cannot be done just by textbook application
of various recipes taught in other courses. Each week, the students
are expected to write up solutions to these mathematical problems.
Emphasis will be given not just for getting the answer correct, but for
explaining it in a clear manner. The assignments will be graded in
detail, with attention given to exposition as well as technique and correctness.
Even if you don't obtain a complete answer, please do write up any partial
progress or other thoughts on the problem; we will read them and comment
on them thoroughly.
This course is worth 2 units of course credit, and the assessment consists
of the weekly homework assignments. Students who wish to participate
for credit should fill out a Math 199 enrollment form from the Math Department
office, and present it to Geoff Mess for signing.
First homework assignment (to be discussed in the Apr 11 session, then
due at the next session on Apr 18):

Question 1: Find a way to divide a square into a finite number of acuteangled
triangles, or show that no such division is possible.

Question 2: Suppose that every point in the plane R^{2}
is colored either red, white, or blue. Show that there exists two
points in the plane which are exactly 1 inch apart and have the same color.
Second homework assignment (to be discussed in the Apr 18 session,
then due at the next session on Apr 25)

Question 1: Show that for any set of five integers, we can always choose
three of these integers whose sum is a multiple of 3.

Question 2: Let n be a positive integer. Prove that 2^{n1}
divides n! if and only if n is a power of 2 (i.e. n = 2^{k} for
some nonnegative integer k).
Third homework assignment (to be discussed in the Apr 25 session, then
due at the next session on May 2)

Question 1: Find the last digit of 2^(3^(4^5)). (Here we use the
notation x^y to denote the exponential x^{y}).

Question 2: 126^{2} = 15876 and 116^{2}=13456 are perfect
squares which end in strings of consecutive digits (876 and 3456 respectively).
What is the longest such string that you can find at the end of a perfect
square?
Fourth homework assignment (to be discussed in the May 2 session, then
due at the next session on May 9)

Question 1: Let ABC be a triangle. Let D be the point on AB such
that AD = AB/3, let E be the point on BC such that BE = BC/3, and let F
be the point on CA such that CF = CA/3. The line segments CD, AE,
and BF divide ABC into three outer triangles, three quadrilaterals, and
one inner triangle. Show that the inner triangle has area equal to
one seventh of the area of ABC.

Question 2: Define a lattice point to be any point in the plane
whose coordinates are both integers. Let ABC be a triangle whose
vertices are lattice points, but whose edges and interior do not contain
any other lattice points. Show that ABC has area exactly 1/2.
The fifth assignment is concerned with the pigeonhole principle, and
is due May 30:

Question 1: Let S be a collection of 16 distinct integers, each from 1
and 30 inclusive. Show that there must exist two distinct elements
in S which differ by exactly 3.

Question 2: Let S be a collection of 16 distinct integers, each from 1
to 30 inclusive. Show that there must exist two distinct elements
in S which are coprime. (Two numbers are coprime if they have
no common factors other than 1).

Question 3: Let S be a collection of 16 distinct integers, each from 1
to 30 inclusive. Show that there must exist two distinct elements
in S such that one divides the other.

Question 4: Let a_{1}, a_{2}, ..., a_{30} be a
sequence of thirty integers. Show that there must exist a consecutive
subsequence a_{i}, a_{i+1}, ..., a_{i+j} of this
sequence whose sum is divisible by 30.

Question 5: Let 0 < a < 1 be a real number. Show that there
must exist a natural number n such that the fractional part of (n * sqrt(2))
lies between 0 and a.

Question 6: Let 0 < a < b < 1 be real numbers. Show that
there must exist a natural number n such that the fractional part of (n
* sqrt(2)) lies between a and b.
The sixth assignment is the 1999 Canadian Mathematical Olympiad, and
is due June 13:

Question 1: Find all real solutions to the equation 4x^{2}  40[x]
+ 51 = 0. Here [x] denotes the greatest integer less than or
equal to x, e.g. [3.5] = 4.

Question 2: Let ABC be an equilateral triangle of altitude 1. A circle
with radius 1 rolls along the segment AB, with the center of the circle
always staying on the same side of AB as C. Prove that the length
of the arc of the circle which is inside the triangle ABC remains constant
as the circle rolls along AB.

Question 3: Determine all positive integers n with the property that
n = d(n)^{2}. Here d(n) denotes the number of positive divisors
of n.

Question 4: Suppose a_{1}, a_{2}, ..., a_{8}
are eight distinct integers, each from 1 to 17 inclusive. Show that
there is a positive integer k such that the equation a_{i}  a_{j}
has at least three different solutions. Also, show that the statement
of this problem fails when "a_{1}, a_{2}, ..., a_{8}
are eight distinct integers" is replaced by "a_{1}, a_{2},
..., a_{7} are seven distinct integers".

Question 5: Let x,y,z be nonnegative real numbers such that x+y+z=1.
Show that x^{2} y + y^{2} z + z^{2} x is less than
or equal to 4/27. When can x^{2} y + y^{2} z + z^{2}
x be exactly equal to 4/27?
This page can be found at http://www.math.ucla.edu/~tao/putnam