# Tagged Questions

Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then one at least one container has more than one item.

541 views

### How to draw Square Diagonal? [duplicate]

Draw a 5x5 square. In 16 of 25 squares draw diagonals in such a way that no diagonal ends touch. How can I do this?
48 views

### Prove existence of 5 non-attacking rooks

Problem: There are $41$ rooks on a $10\times10$ chessboard. Prove that there must exist $5$ rooks, none of which attack each other. I could only observe that at least one of rows and at least one ...
100 views

### Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
100 views

### Pigeonhole principle for proof

Prove that if a is a natural number, then there exists two unequal natural numbers k and l for which $$a^k - a^l$$ is divisible by 10. I'm strangely lost on this one. I understand the pigeonhole ...
63 views

### Two out of five in a group have the same number of friends…

I recently came across a problem- Prove that in a group of five people,there are two who must have the same number of friends in the group. I assume it must be solved by Pigeon Hole Principle (...
57 views

### show that there are at least $\frac{n(n-1)}{2}$elements in this sets

Let $x_{i},i=1,2,\cdots,n$ be real numbers,and such $$|x_{i}-x_{j}|>1(\forall i\neq j)$$ define set $A=\{x_{i}x_{j}+x_{k}|1\le i,j,k\le n\}$,show that $$|A|\ge\dfrac{n(n-1)}{2}$$ How can I go ...
101 views

### Lower bound for $R(3, 3,\ldots, 3)$

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges ...
61 views

### Prove that if $|S| \ge 2^{n−1} + 1$, then $S$ contains two elements which are disjoint from each other.

I'm trying to use the pigeonhole principle to prove that if $S$ is a subset of the power set of the first $n$ positive integers, and if $S$ has at least $2^{n-1}+1$ elements, then $S$ must ...
47 views

### Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
55 views

### Tricky probability question which cant be solved using exclusion?

I am confused on how to go about solving this problem- " What is the probability that 2 people in the group have a birthday in the same month out of a)exactly 20 people? b)atleast 20 people" I ...
69 views

### Prove that if 51 positive integers between 11 and 100 are chosen, then one of them must divide another.

I'm a little unsure how to approach this problem. Thanks for any help.
79 views

### Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2. In my attempt. I try $n=2$, and so ...
30 views

### Pigeon hole subset problem

For a given N numbers labeled from 1-N, we need to pick M numbers such that there are atleast K pairs of numbers(x,y) which statisfy x+y=N+1? can anyone help me out with this... please?
133 views

### Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

$n$ is also given to be an even number. So I want to prove this by using the pigeon-hole principle. I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as ...
73 views

### How to apply Pigeonhole principle in this question

There are 10 people at a party and each person knows an even number of people at the party. Prove that there are 3 people who know the same number of people. Here we assume that knowing someone is ...
64 views

### Variation on the “Number of non-bald people in NYC” problem

I have two questions about the following problem, taken from Challenging Problems in Algebra by Posamentier and Salkind: (1) Why is the answer not 1 person? (2) The answer given, without solution, is ...
168 views

### Let $S=\{3,4,5,6,7,8,9,10,11,12\}$. Suppose 6 integers are chosen from S. Must there be 2 integers whose sum is 15?

How can I go about solving this Pigeonhole Principle problem? So I think the possible numbers would be: $[3+12], [4+11], [5+10], [6+9], [7+8]$ I am trying to put this in words...
328 views

### In a group of 30 people, must at least 3 have been born in the same month? Why?

This is a pigeon hole principle problem and I'm not sure how I can word this to prove that at least 3 have been born in the same month out of 30 people?
86 views

### Show that there are at least 2 computers in the network … (Pigeonhole Principle)

A computer network consists of 6 computers. Each computer is directly connected to at least one of the other computers. Show that there are at least 2 computers in the network that are directly ...
286 views

### Application of the pigeon hole principle

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows: "During a month with 30 days, a ...
39 views

### Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\}$". Here is my proof ...
124 views

### Prove using Pigeon Hole principle.

A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, to avoid tiring himself, he decides not to play more than 12 games during any calendar week....
88 views

### Proving by pigeonhole principle that a duocolored 3x9 rectangle will always contain subrectangles whose corners are the same color.

Lets say each square of a 3x9 rectangular board is colored either blue or red. How can I prove mathematically that for any such coloring, the board will always contain a subrectangle (paralell to the ...
38 views

### Markov's Inequality and the Pigeonhole Principle

I heard someone in my department claim that Markov's inequality was just a continuous version of the pigeonhole principle. It seemed reasonable, but I'm struggling to make their connection precise. ...
56 views

### Are Square and equilateral triangle the only convex regular ngons that can be composed to smaller versions of themselves?

While I was trying to make an analogous question to Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\frac{\sqrt{2}}{n}$ apart, using equilateral ...
144 views

### Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\sqrt{2}/n$ apart

I know I need to use the pigeonhole principle to prove this, but I don't know exactly how. What I think I could do is divide the unit square into $n^2$ squares. Using Pythagoras theorem, the maximum ...
29 views

### If $x,y,a_1,\ldots,a_n\in\mathbb Z$ and $a_1,\ldots,a_n\in[x,y],$ then $a_1=x,a_2=x+1,\ldots,a_n=y$ (proof verification)

I recently solved a problem in which I used the following fact. If there are exactly $n$ integers in the interval $[x,y]$ ($x,y\in\mathbb Z$) and $a_1,a_2,\ldots,a_n$ are integers of that interval ...
92 views

### Discrete mathematics: Question regarding “Pigeonhole principle”. [closed]

Each point in the plane is coloured either red or blue. Show that there are two points of the same colour which are exactly 1 cm apart.
1k views

### Pigeonhole principle: Five points on an orange

Five points are drawn on the surface of an orange. Prove that it is possible to cut the orange in half in such a way that at least four of the points are on the same hemisphere. (Any points lying ...
202 views

### Application of Pigeon-Hole Principle to balls in bins.

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.
168 views

### Proof that only a certain amount of points can fit in a rectangle

Prove that no more than 8 points can fit in a rectangle with sides d and 2d if any 2 points have to be at least d units away from each other. I have proved that no more than 6 points can fit in ...
113 views

### Pigeonhole principle 3

I need help on this question, I'm lost and really don't know how to proceed: Use the pigeonhole principle to prove that in a round-robin chess tournament (with 18 participants) there will be at least ...
139 views

### Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or ...
68 views

### Problem involving weights of blocks and pigeonhole principle

So I have been trying to solve the following problem: Suppose you are given n blocks, each of which weighs an integral number of pounds, but less than n pounds. Suppose also that the total weight of ...
751 views

### Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is the ...
81 views

### problem related to pigeon hole principle

please help me to solve this using pigeon hole principle Suppose that S is a set of n integers. Show that one can choose a nonempty subset T of S such that the sum of all elements of T is divisible ...
71 views

### Discrete matematics, using pigeonhole principle [closed]

Please help me solve this problem: Assuming that in a box there are $10$ black socks and $12$ blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the ...