## Homework 3: Pigeon-hole principle Problem 1 Assume that there are \( n \) people in the group. The number of acquaintances that each person could have belongs to the set \( \{0,1,2,3,\dots, n-1\} \). Let us consider the following two cases: **Case 1**: There is a person with \( 0 \) acquaintances. In this case no person can have \( n-1 \) acquaintances. This means that the number of possible friends that each person could have is from the set \( \{0,1,2,\dots, n-2\} \). This set has \( n-1 \) elements and there are \( n \) people. According to pigeon-hole principle two people will have the same number of friends.**Case 2**: There is no person with \( 0 \) acquaintances. In this case the number of friends each person could have belongs to the set \( \{1,2,\dots, n-1\} \). This set has \( n-1 \) elements, and there are \( n \) people, hence according to pigeon-hole principle two people will have the same number of friends.
Problem 2 Assume that no two of the given integers differ by a multiple of \( 2n \). This means that each two of the given integers have different remainders modulo \( 2n \). The set of possible remainders is \( \{0,1,\dots, 2n-1\} \) and this set can be written as the union of the following sets: \[ \{0,1,\dots, 2n-1\}=B_0\cup B_1\cup B_2\cup\cdots \cup B_{n-1}\cup B_n,\] where \( B_0=\{0\} \), \( B_n=\{n\} \), and \( B_i=\{i,2n-i\} \) for \( i\in\{1,2,\dots, n-1\} \). Since there are \( n+1 \) sets in the union, by pigeon-hole principle there must exist two integers \( i \) and \( j \) among the chosen \( n+2 \) integers such that \( i,j\in B_k \) for some \( k\in\{1,2,\dots, n-1\} \). Clearly, this \( i \) and \( j \) will satisfy \( 2n\mid i+j \). Problem 3 Let us divide the square in \( 50 \) rectangles of the format \( 2\times 1 \). Then by pigeon-hole principle three points are in one of the rectangles. We will now prove that these three points form a triangle with an area smaller than \( 1 \). Let us denote by \( S_{\triangle XYZ} \) the area of the triangle \( XYZ \). We have three points \( A \), \( B \), and \( C \) that belong to the rectangle \( PQRS \) with \( PQ=2 \) and \( QR=1 \). Consider the line through \( C \) parallel to \( AB \). This line intersects the sides of \( PQRS \) in at most \( 2 \) points, \( C^{\prime} \) and \( C^{\prime\prime} \). Then we have \[ S_{\triangle ABC}\leq \max\left\{S_{\triangle ABC^{\prime}},S_{\triangle ABC^{\prime\prime}}\right\}.\] Assume that \( S_{\triangle ABC}\leq S_{\triangle ABC^{\prime}} \). Assume that \( C^{\prime}\in PQ \). Then \[ S_{\triangle ABC^{\prime}}\leq \max\left\{S_{\triangle ABP},S_{\triangle ABQ}\right\}.\] Therefore in order to solve the given problem it suffices to solve it under the condition that \( C \) is one of the vertices of the rectangle. Similarly as before, we can reduce the problem to the one in which \( A \), \( B \), and \( C \) are all vertices of the rectangle. The area of such a triangle is \( 1 \), hence \( S_{\triangle ABC}\leq 1 \). Problem 4
There is a total of \( 2^n \) subsets of \( S \) and if each of them have different sums, then we have a total of \( 2^n \) sums. The largest sum is \( n+1+(n+2)+\cdots n^2< n\cdot n^2=n^3 \). Since \( 2^n> n^3 \) two subsets \( U \) and \( V \) have the same sum. Set \( A=U\setminus (U\cap V) \) and \( B=V\setminus (U\cap V) \).
Problem 5
A set \( S\subseteq \{2,3,4,5,\dots\} \) is called 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 \). We will prove that the maximal value for \( k \) is \( 2 \). Indeed, if \( k\geq 3 \), then the set \( \{2,4,6,8,10\} \) is composite but none of its elements is \( \geq \) \( 5\cdot 3=15 \). Let us prove that every composite set with at least \( 3 \) elements has an element greater than \( 2|S| \). Assume the contrary, that all elements of \( S \) are smaller than \( 2|S| \). Let \( |S|=n \). Then \( S\subseteq \{2,3,\dots, 2n-1\} \). Let us group the elements in pairs \( (2,3) \), \( (4,5) \), \( \dots \), \( (2n-2,2n-1) \). There are \( n-1 \) pairs and by the pigeon-hole principle some two elements from \( S \) must be in the same pair. This is a contradiction since numbers from the same pair are relatively prime. 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.\] Let \( \Gamma_m({\bf P}) \) be the set of all points that are at a distance at least \( 2013 \) from the polygonal line \( P_1\dots P_m \). The volume of the set \( \Gamma_m({\bf P}) \) is at most \( l_m({\bf P})\cdot 2013^2\pi + \frac{4\cdot 2013^3\pi}3 \). Consider a sphere of radius \( 0.49 \) around each point with integer coordinates. These spheres do not intersect and for each point with integer coordinates that is at a distance at most \( 2012 \) from \( P_1\dots P_n \) the corresponding sphere is inside \( \Gamma_m({\bf P}) \). Therefore \( \alpha_m({\bf P})\cdot 0.49^3\cdot\frac{4\pi}3\leq l_m({\bf P})\cdot 2013^2\pi + \frac{4\cdot 2013^3\pi}3 \). 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. Let us make the following graph. The set of vertices is the set of all points \( (\pm 1, \pm 1, \dots, \pm1) \). Two points are connected by an edge if they differ by exactly one coordinate. The degree of each vertex is \( n \). Look at the vertices that belong to \( B \) and let us paint in green the other endpoints of the edges originating from those vertices. We performed this painting job more than \( 2^{n+1} \) times, hence there is at least one point \( X \) that is painted at least three times. That \( X \) is at the distance \( 1 \) from three points \( P \), \( Q \), and \( R \) from \( B \). Then \( PQR \) is equilateral triangle of size \( 2\sqrt 2 \). 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? The answer is 2. One measurement is not enough even when we have only two boxes. Indeed, in this one measurement we could only fix in advance two numbers \( a_1 \) and \( a_2 \) and find the total weight of \( a_1 \) coins from the first and \( a_2 \) coins from the second box. We obtain the number \( M=a_1x+a_2y \), where \( w\in\{x,y\} \). Knowing \( M \), in general, we cannot conclude whether \( M=a_1p+a_2y \) or \( M=a_1x+a_2p \). Let us now prove that we can find all fake coins in 2 measurements. In the first measurement we pick \( 3^i \) coins from the box \( i \) and find their total weight \( M \). Denote \( N=3+3^2+\cdots + 3^n=\frac12(3^{n+1}-3) \). Let us consider two dfiferent cases: \( M< Nw \) and \( M> Nw \). Since the cases are very similar, we will consider only the first one. We assume that \( M< Nw \). This means that the fake coins are lighter than the regular ones. Let us denote by \( f \) the weight of a fake coin. Then we have that \( M\geq Nf \) which means that \( f\leq \frac MN \). For any sequence \( \overrightarrow a=(a_1, \dots, a_n)\in \{0,1\}^n \) denote by \( T_{\overrightarrow a}=\sum_{i=1}^n a_i3^i \). Denote by \( L \) the maximum of the set \( \left\{T_{\overrightarrow a}:\overrightarrow a\in\{0,1\}^n,\; T_{\overrightarrow a}< \frac N2\right\} \). Then we have that \( f\geq \frac{M-Lw}{N-L} \) thus \[ \frac{M-Lw}{N-L}\leq f\leq \frac{M}N.\] We have that \( T_{\overrightarrow a}\neq T_{\overrightarrow{b}} \) whenever \( \overrightarrow a\neq \overrightarrow {b} \). Let us denote \( \omega=\min \left|\frac{T_{\overrightarrow a}}{T_{\overrightarrow{b}}}-1\right| \) where the minimum is taken over all pairs \( (\overrightarrow a, \overrightarrow {b}) \) that satisfy \( \overrightarrow a\neq \overrightarrow {b} \).
Assume that the weight of coins from the box \( i \) is \( x_i \). Then for each \( i \) we have \( x_i\in\{w,f\} \). If we assume that \( x_n=f \) then we have \( A=\sum \alpha_ix_i \leq \sum_{i=1}^{n-1}\alpha_i w+ \alpha_n\frac{M}N=B_n \). If we assume that \( x_n=w \) then we have \( A\geq \sum_{i=1}^{n-1}\alpha_i\cdot \frac{M-Lw}{N-L}+ \alpha_nw=A_n \). By our choice of \( \alpha_n \) we have that \( B_n< A_n \). Now if we find out that \( A\leq B_n \) we can be sure that \( x_n=f \) because otherwise we must have \( A\geq A_n> B_n \) which contradicts the fact that \( B_n< A_n \). Similarly, if \( A\geq A_n \) we know that \( x_n=w \). If it turned out that \( x_n=f \) then we found \( j=0 \). Otherwise, we can repeat the same procedure for boxes \( 1 \), \( 2 \), \( \dots \), \( n-1 \) whose total sum of weights is \( A-\alpha_nw \). In such a way we arrive to the box \( j \) that contains the fake coins. We know the total mass of all coins in boxes \( 1 \), \( \dots \), \( j \), which is equal to \( \hat A=A-\alpha_nw-\alpha_{n-1}w-\cdots-\alpha_{j+1}w \). Then we have \( \hat A=\alpha_1x_1+\cdots + \alpha_{j-1}x_{j-1}+\alpha_j f \leq (\alpha_1+\cdots+\alpha_{j-1})w+\alpha_jf \) and \( \hat A\geq \alpha_j f \) which implies that \[ \frac{\hat A}{\alpha_j}-\frac{\sum_{i=1}^{j-1}\alpha_i}{\alpha_j}\leq f\leq \frac{\hat A}{\alpha_j}.\] Thus the lemma is proved for \( \hat f=\frac{\hat A}{\alpha_j} \). The proof of the lemma is complete.For each sequence \( \overrightarrow a\in\{0,1\}^n \) let us define \( \varphi(\overrightarrow a, f)= T_{\overrightarrow a}f+(N-T_{\overrightarrow a})w \). If \( f \) and \( f^{\prime} \) are two real numbers smaller than \( w \), and \( \overrightarrow a \) and \( \overrightarrow b \) two sequences then we have: \begin{eqnarray*} \left|\varphi(\overrightarrow a, f)-\varphi(\overrightarrow b,f’)\right|&=&\left|T_{\overrightarrow a}(f-w)-T_{\overrightarrow b}(f’-w) \right|\\ &=&\left|T_{\overrightarrow a}(f-w)-T_{\overrightarrow b}(f-w)+ T_{\overrightarrow b}(f-f’) \right|\\&\geq& \left|T_{\overrightarrow a}-T_{\overrightarrow b}\right|\cdot |f-w|-T_{\overrightarrow b}|f-f’|\\ &\geq& 3\omega \cdot\left(w-\frac MN\right)-N\cdot |f-f’|. \end{eqnarray*} In the last inequality we used that \( w-f> w-\frac MN \) and \( |T_{\overrightarrow a}-T_{\overrightarrow b}|\geq 3\omega \). It suffices to pick \( \varepsilon \) that satisfies \( \varepsilon < \frac {3\omega}N\cdot\left(w-\frac MN\right) \). Then we use lemma to find a value of \( \hat f \) that is within \( \varepsilon \) of \( f \), and then we check all the possible values of \( \varphi(\overrightarrow a, \hat f) \). The sequence \( \overrightarrow a \) for which \( |\varphi(\overrightarrow a, \hat f)-M| \) is minimal is the sequence of boxes with 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 |