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 acute-angled triangles, or show that no such division is possible.
• Question 2: Suppose that every point in the plane R2 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 2n-1 divides n! if and only if n is a power of 2 (i.e. n = 2k for some non-negative 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 xy).
• Question 2: 1262 = 15876 and 1162=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 co-ordinates 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 a1, a2, ..., a30 be a sequence of thirty integers.  Show that there must exist a consecutive subsequence ai, ai+1, ..., ai+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 4x2 - 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 a1, a2, ..., a8 are eight distinct integers, each from 1 to 17 inclusive.  Show that there is a positive integer k such that the equation ai - aj has at least three different solutions.  Also, show that the statement of this problem fails when "a1, a2, ..., a8 are eight distinct integers" is replaced by "a1, a2, ..., a7 are seven distinct integers".
• Question 5: Let x,y,z be non-negative real numbers such that x+y+z=1.  Show that x2 y + y2 z + z2 x is less than or equal to 4/27.  When can x2 y + y2 z + z2 x be exactly equal to 4/27?