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
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us