Today’s strategy is the well-known box (or pigeonhole) principle: if n+1 items are distributed among n boxes, at least one box must contain more than one item.

More generally, if kn+1 items are distributed among n boxes, at least one box must contain at least k+1 items.

Sample problem: Five points with integer coordinates are chosen on the plane. Prove that you can always choose two of these points so that the segment joining them passes through another point with integer coordinates. (The solution is at the end of the worksheet).

For the worksheet, click here.

Today’s strategy is to look for appropriate extremal objects: those that maximize or minimize some function. A common technique is to use extremality to show that an object must have some desired property. The following two problems can be solved using this technique (the solutions to the sample problems appear at the end of the worksheet).

Sample Problem 1. Let \(\Omega\) be a set of points in the plane. Each point in \(\Omega\) is a midpoint of two points in \(\Omega\). Show that \(\Omega\) is an infinite set.

Sample Problem 2. 2n points are given in the plane, no three collinear. Exactly n of these points are farms, the remaining n points are wells. It is intended to build a straight line road from each farm to one well. Show that the wells can be assigned bijectively to the farms, so that none of the roads intersect.

For the worksheet, click here.

Today’s theme is problems that involve colorings. A coloring is a way of visualizing the partition of a set into a finite number of subsets. The prototypical example is the following problem (its solution appears at the end of the worksheet).

Sample Problem. Consider an 8 × 8 chessboard, and cut two diagonally opposite corners of the board. In how many ways can you cover the 62 squares with dominoes?

Click here for the worksheet.

Today was our first session for the Fall 2019 semester!

The theme of today was the invariance principle. This idea applies when we have a situation that is changing over time, and the point is to find an invariant, that is, a quantity that stays the same.

A variation of the invariance principle is to find a quantity that perhaps does not always stay the same, but we know that it always increases (or decreases).

You can find today’s handout here.

For a list of diverse accessible Putnam problems, click here.

For the Fall 2019 semester, the Putnam Problem-Solving Seminar meetings will start on August 29th and will be held:

• Thursdays,  5:00-6:30pm
• PHSC 321

As usual, please do come even if you need to show up a bit later or leave early. Everyone is welcome, so tell your friends!

For the Fall 2018 semester, the Putnam Problem-Solving Seminar meetings will start on August 30th and will be held

• Thursdays,  5:00-6:30pm
• PHSC 313

As usual, please do come even if you need to show up a bit later or leave early. Everyone is welcome, so tell your friends!

It’s the fall semester again, which means it’s Putnam time! Our first meeting of the semester will be held:

• Thursday, August 31, 5:00-6:30pm
• PHSC 1025

As usual, please do come even if you need to show up a bit later or leave early. This is not a class and the format easily allows for people to come and go as they need.

 

We worked on some problems from the 2008 Putnam, as well as on from the 2009 Putnam.

• (A-5, 2009): The key was to get the area involved. By Pick’s theorem or a determinant argument, the area is at least 1/2; it is also equal to abc/(4r) where a, b, c are the lengths of the sides of the triangle.The conclusion follows easily.
• (A-1, 2008): Standard strategies for functional equations (see below).
• (A-2, 2008): Barbara can make sure that the determinant is zero. For example, looking at the first two columns, any time that Alan plays in one of those columns, Barbara writes the same number in the same position but on the other column. This way the final matrix will have to equal columns, and thus determinant zero.
• (B-1, 2008): We have not finished, but have some ideas. We saw how to get two points with rational coordinates on one such circle; we suspect three might be impossible and are trying to prove that if three rational points are on a circle, then the center must be rational as well.

Today’s pearls of wisdom:

• For a problem with a functional equation, substitute special values (zero, one, some numbers equal to others, etc).
• Pick’s theorem: For a polygon all o whose vertices have integer coordinates, the area is equal to: (the number of interior points with integer coordinates) + (1/2)(number of boundary points with integer coordinates) – 1. We proved this with a cool induction argument.

 

We started looking at the problems in the 2000 Putnam exam, together with a few selected ones from 2009 (handout).

• We solved problem A-1 (2009) by using a convenient arrangement of squares. We also solved a version where the assumption is made for equilateral triangles instead of squares. We are still thinking about the version for regular pentagons.
• Some ideas and strategies that some people used for other problems:
  • B-1 (2009): An inductive argument.
  • B-2 (2000): Do we know any properties of the greatest common divisor?

Today’s nuggets of wisdom:

• If a triangle has its vertices on a circle of radius \(R\), and the lengths of the sides of the triangle are \(a\), \(b\), and \(c\), then the area of the triangle is \(\frac{abc}{4R}\)
• If we have a matrix, and we add a multiple of a row to another row, the value of the determinant does not change. (Same for columns).

We started looking at problems from a new handout: worksheet-2016-10-13.pdf

• We solved problem 11 in two different ways. First we did a precise analysis of the possibilities for the number of heaps and the number of stones in each
  heap. Then we simplified the solution by using an invariant: the number of heaps plus the number of stones.
• We solved problem 6 by using the triangle inequality.
• We solved problem 1 by finding an explicit formula for the inverse. We noticed that this formula is related to a factorization of the polynomial
  \(X^m-Y^m\).
• We solved problem 9 by brute force: we considered different cases (related to the number of zeros among a,b,c), and then analyzed each of them. We
  finished by noticing that there seems to be a relation to the polynomial \((x-a)(x-b)(x-c)\). We will continue exploring this connection.
• We also discussed problems 2, 3, and 7, but didn’t make much progress.