# Homework 3: 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?

2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax