Suggest a Book

# Basics of Pigeonhole Principle

Level: unknown

posted Jun 12 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Prove the following :

• Given $n$ integers, some nonempty subset of them has sum divisible by $n$.

• Let $A$ be a set of $n+1$ integers from {${1, 2,\dots , 2n}$}. Prove that some element of $A$ divides another. Is this best possible, i.e., is the conclusion still true for $n$ integers between $1$ and $2n$ ?

• Given any $n + 1$ distinct integers between $1$ and $2n$, show that two of them are relatively prime. Is this result best possible, i.e., is the conclusion still true for $n$ integers between $1$ and $2n$ ?

• Let $p$ be a prime number. Prove that at least one of the first $p + 1$ Fibonacci numbers must be divisible by $p$.

• A collection of subsets of {$1, 2, \dots , n$} has the property that each pair of subsets has at least one element in common. Prove that there are at most $2^{n−1}$ subsets in the collection.

• Given any $n+2$ integers, show that there exist two of them whose sum or difference, is divisible by $2n$.

• Given $2n − 1$ integers, prove that one can choose exactly $n$ of them whose sum is divisible by $n$.

• Let $n$ be a positive integer, and let $X$ be a set of $n+2$ integers, each of absolute value at most $n$. Show that there exist three distinct numbers $a, b, c$ in $X$ such that $a + b = c$.

• You are given a list of $n$ positive integers whose sum is less than $2n$. Prove that, for any positive integer $m$ not exceeding the sum of these $n$ integers, one can choose some of the integers so that their sum is $m$.

delete retag edit

## Stats

Posted: Jun 12 '12

Seen: 70 times

Last updated: Jun 12 '12