# Questions tagged [pigeonhole-principle]

This tag is for questions involving the Pigeonhole Principle, which roughly states that if $n$ items are placed in $m$ containers and $n>m$, then at least one container has more than one item.

1,129 questions
Filter by
Sorted by
Tagged with
22 views

### Permutations with pigeonhole principle quesion

I have set G of 101 functions from  to  ( is S10). I need to prove that there are 2 functions (a,b) from the set G, and two numbers I,j that belongs to , that sustain a(i) = b(i) and a(...
35 views

### Proof by contradiction of a variant of PHP

Let $a_1, a_2,\ldots , a_n$ be positive integers. Prove that if $(a_1+a_2+\ldots+a_n)-n+1$ pigeons are to be put in $n$ pigeonholes, then for some $i$, the statement "The $i^{th}$ pigeonhole ...
76 views

### If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$.

$\blacksquare~$ Problem: If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$. $\blacksquare~$ My Approach: Let the minimum element chosen ...
30 views

### Math Question - Pigeonhole-Principle [closed]

Vera has $10$ white socks, $10$ black socks, $10$ brown socks, $10$ blue socks, and $10$ red socks. How many socks (at a minimum) must she pull out of her sock drawer to ensure at least two matching ...
77 views

### Show that for every integer $n$ there is a multiple of $n$ that has only $0s$ and $1s$ in its decimal expansion.

Can anyone please explain this example as I tried a lot to understand it but I can't! The problem: Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal ...
38 views

### How many vertices with same degree

In a simple graph with $2000$ vertices without any vertex with $\deg(a)=0$, we have exactly two vertices which have the same degree. What is the degree of these two? I think I should use pigeon hole ...
66 views

47 views

### Problem about the generalized pigeonhole principle

This problem from Discrete Mathematics and its application's for Rosen What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10-...
73 views

### Putnam Pigeonhole principle problem regarding a 20 person college and 6 courses

Question: A certain college has 20 students and offers 6 courses. Each student can enroll in any or all of the 6 courses, or none at all. Prove or disprove: there must exist 5 students and 2 courses, ...
147 views

### Proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$

How can one prove that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$? It is not hard to see this is equivalent to show that among $2n-1$ residue classes ...
58 views

### 36 cards were distributed equally to 6 people. Prove that there is a person who has at least 4 cards of the same suit

36 cards were distributed equally to 6 people. It is known that for any two people there are at least two suits, such that they have equal cards of these suits. Prove that there is a person who has ...
58 views

55 views

### What is the minimum $N$ such that if $N$ people discuss three topics, then at least three people will discuss the same topic? [closed]

$N$ people corresponded by mail with one another, each corresponding with all of the rest. In their letters, only three topics were discussed. If we can always find at least three people who discussed ...
108 views

### Use Induction to solve a $\bmod$ question.

On a holiday my $m \in \mathbb{N}, m \geq 1$, many of my family members gave me $a_m \in \mathbb{N}$ much money. Here $a_m$ implies the amount each family member gave. Let's say that a computer game ...
64 views

### In a math competition with $8$ students and $8$ problems, if each problem is solved by $5$ students, then two students together solve all problems. [closed]

Eight students are entered in a math competition. They all have to solve the same set of $8$ problems. After correction, we see that each problem was correctly resolved by exactly $5$ students. Show ...
112 views

### A 10x10 table filled with 0 to 9 numbers

I saw this question but I couldn't find the answer. Assume that we have a 10x10 table, and it's filled with 0 to 9 numbers ( 10 of each of them are in the table, 10x zero, 10x one, and ... ) By using ...
84 views

86 views

### USSR MO 1980 pigeonhole-principle [closed]

Let $n \geq 3$ be an odd number. Show that there is a number in the set $\{2^1-1,2^2-1,...,2^{n-1} - 1\}$ which is divisible by $n$.
42 views

### Prove that L has four elements , the product of which is equal to the fourth power of an integer

The set $L$ consists of 2003 integers , none of which has a prime divisor larger than $24$. Prove that $L$ has four elements , the product of which is equal to the fourth power of an integer. Above ...
34 views

### understanding a pigeonhole principle problem

I am trying to understand an already solved problem which makes use of the pigeonhole principle There are $271$ students in an exam which consists of $3$ random, non-repeating questions out of a ...
48 views

33 views

### prove 3 separate subsets of 90 numbers with similar sums

"Given a set of 90 numbers , each with 3 digits , prove that there exist 3 subsets which are each separate , that have the same sum (sum of the numbers)." I know that I should use the pigeonhole ...
44 views

### Questions About A Pigeonhole Principle Problem

I've encountered the following pigeonhole principle problem. It uses notation from set theory, which is a subject I haven't studied yet. I would like to check if I have understood notation, and the ...
32 views

### Discrete Mathematics - Pigeon Hole Principle/ Geometry combinatrix

I am trying to solve a problem that states a certain number of points lets say 50, are in a 20cm cube. It then asks to prove that 7 are in a 10cm cube. How is this even pigeonhole? I've not done this ...