Skip to content

5.14 Pigeonhole Principle

  1. \(A\subset \{1,2,...,2n\}\) and \(|A|=n+1\).

    There are \(n_1,n_2\in A\) s.t. \(n_1+n_2=2n+1\)​

    \(m_1,m_2\in A\) s.t. \(m_1-m_2=n\)​

    We want to construct pigeonhole. \(f:\{1,...,n+1\}\to \text{set of pairs}\) \((1,2n),(2,2n-1),...,(n,n+1)\) where \(i\mapsto\) pir that contains \(a_i\)​

    For example \(n=4,\) set = \(\{2,1,4,5,8\}\), then \(1\mapsto (2,7),2\mapsto (1,8),3\mapsto (4,5),4\mapsto (4,5),1\mapsto (1,8)\)

    \(g:\{1,...,n+1\}\to\) set of pairs \((2n,n),(2n-1,2n-1),...,(n+1,1)\)​

  2. Let \(T\) is a square with side length of 3 units. \(P=\{a_{1},...,a_{10}\}\subset T\)​

    Show that \(\exists i,j:i\neq j:||a_i-a_j||\leq \sqrt{2}\)​

    image​

    \(f: I=\{1,...,10\}\to\) set of small squares where \(i\mapsto\) small square \(a_i\) belongs to

    image​

  3. Round robin chess tournament

    win - player scores +1 pt.

    loss - player scores -1 pt.

    draw- 0 points

    It is known that at least \(70\%\) of all the games ended in a draw

    Prove, that in the end of the tournament there exists \(2\) players that score the same number of points

    Consider \(10\) players, then we have \(\binom{10}{2}\) possible games

    Then at least 32 games ended in a draw and at most 13 games changed the scores of the players

    Suppose all players scored different number of points

    image​

    \(5\) players with positive scores and all the scores are different

    The minimal possible sum of their scores is \(1+2+3+4+5=15\)​

    But in \(13\) games we cannot score \(15\) points

  4. Original, Ramsey problem can be stated in terms of a search of monochromatic cliques of the given size

    image​

  5. Let \(r,s\in\N\), show \(\exists N\in \N\) such that any sequence of \(N\) different real numbers either has an increasing subsequence of length \(r\) or a decreasing subsequence of length \(s\)​

    For example \(2,3,5,7,13,6,-1,-5\) and label it as \(1,2,3,...,N\)

    image image​

    Thus it's clearly \(N=R(r,s)\) holds, but can \(N\) less than \(R(r,s)\)? Yes, \(N \le (r-1)(s-1)+1\)

    Why?

    Suppose there is no increasing subsequence of length r and no decreasing subsequence of length s

    Let define a function such that \(i \mapsto (a_i, b_i)\) where
    \(a_i\): length of a longest increasing sequence that end in position \(i\)
    \(b_i\): length of the longest decreasing subsequence that end in position \(i\)

    Then \(1 \le a_i \le r-1\) and \(1 \le b_i \le s-1\)
    Then all possibilities of \((a_1,b_i)\) are \((r-1)(s-1)\)

    If we set \(N=(r-1)(s-1)+1\), then by pigeonhole principle, we know there at least two different numbers are in the same pair, that is

    For example if \(i=5\), then above example, \(a_5=5\) and \(b_{5}=1\)

    Suppose \(\exists j = 9\) and \(a_{9}=5,b_{9}=1\), then two cases

    If \(n_{5}<n_{9}\), then we can add \(n_9\) into \(a_{9}\), then \(a_{9}=6\) contradiction

    If \(n_{5}>n_{9}\), then we can add \(n_{5}\) into \(b_{5}\), then \(b_{5}=6\) contradiction

    Generally, if we have \(n_i\) and \(n_j\) s.t. \((a_i,b_i)=(a_j,b_j)\) and \(i<j\)

    Then if \(n_i<n_j\), then we can add at least \(n_j\) into \(a_i\), then \(a_j=a_i+1\)

    If \(n_i>n_j\), then we can at least add \(n_i\) into \(b_j\), then \(b_i=b_j+1\)

    Contradiction

    Then there doesn't exists \(n_i\) and \(n_j\) s.t. \((a_i,b_i)=(a_j,b_j)\) and \(i<j\)

    Thus If \(N=(r-1)(s-1)+1\), then either has an increasing subsequence of length \(r\) or a decreasing subsequence of length \(s\)
    By the way, we know \(N\) is bounded by \((r-1)(s-1)+1\), that is \(N\leq (r-1)(s-1)+1\)