Putnam preparation (Table of contents)

Pigeon-hole principle

Problem 1 Prove that in a group of at least \(2\) people there are always two people who have the same number of acquaintances in the group.

Problem 2 Show that among any \(n+2\) integers, either there are two whose difference is a multiple of \(2n\), or there are two whose sum is divisible by \(2n\).

Problem 3 Assume that \(101\) distinct points are placed in a square \(10\times 10\) such that no three of them lie on a line. Prove that we can choose three of the given points that form a triangle whose area is at most \(1\).

Problem 4 Let \(n\geq 10\) and let \(S\) be a subset of \(\{1,2,\dots, n^2\}\) that has exactly \(n\) elements. Prove that there are two non-empty disjoint subsets \(A\) and \(B\) of the set \(S\) such that the sum of elements of \(A\) is equal to the sum of elements of \(B\).

Problem 5

A set \(S\subseteq \{2,3,4,5,\dots\}\) is called composite if no two elements of \(S\) are relatively prime. Find the maximal \(k\in \mathbb N\) for which the following proposition holds:

Every composite set \(S\) with at least \(3\) elements has an element greater than or equal to \(k\cdot |S|\).

As usual, \(|S|\) denotes the number of elements in \(S\).

Problem 6

Assume that \({\bf P}=(P_n)_{n=1}^{\infty}\) is a sequence of points from \(\mathbb R^3\). Denote by \(\alpha_m({\bf P})\) the number of points with integer coordinates that are at a distance smaller than 2012 from the polygonal line \(P_1P_2\dots P_m\). Denote by \(l_m({\bf P})\) the length of the polygonal line \(P_1P_2\dots P_m\).

Prove that there exists numbers \(C\) and \(D\) such that for any sequence \({\bf P}=(P_n)_{n=1}^{\infty}\) and any positive integer \(m\) the following inequality holds: \[\alpha_m({\bf P})\leq C\cdot l_m({\bf P})+D.\]

Problem 7

Let \(n\geq 3\), and let \(B\) be a set of more than \(\frac{2^{n+1}}n\) distinct points with coordinates of the form \((\pm1,\pm 1,\cdots, \pm 1)\) in \(n\)-dimensional space. Prove that there are three distinct points in \(B\) which are the vertices of an equilateral triangle.

Problem 8

There are \(n > 1\) boxes with infinitely many coins in each of them. Each box contains either regular or fake coins. All regular coins have equal weight \(w\). All fake coins have the same weight that is different from \(w\). We don’t know whether they are heavier or lighter than the regular ones.

What is the smallest number of measurements on a digital scale that is necessary to find all boxes that have fake coins?