## Pigeonhole Principle

“The Pigeonhole principle” ~ Students who have never heard may think that it is a joke. Pigeonhole Principle is one of the simplest but most useful ideas in mathematics. Let’s learn the Pigeonhole Principle with some applications.

## Pigeonhole Principle Definition:

In Mathematics, the pigeonhole principle states that if we must put N + 1 or more pigeons into N Pigeon Holes, then some pigeonholes must contain two or more pigeons.

### Pigeonhole Principle Example:

If Kn+ 1 (where k is a positive integer) pigeons are distributed among n holes than some hole contains at least k + 1 pigeons.

### Applications of Pigeonhole Principle:

This principle is applicable in many fields like Number Theory, Probability, Algorithms, Geometry, etc.

## Problems:

### Problem 1

A bag contains beads of two colours: black and white. What is the smallest number of beads which must be drawn from bag, without looking so that among these beads, two are of the same colour?

Solution: We can draw three beads from bags. If there were no more than one bead of each colour among these, then there would be no more than two beads altogether. This is obvious and contradicts the fact that we have chosen there beads. On the other hand, it is clear that choosing two beads is not enough. Here the beads play the role of pigeons, and the colours (black and white) play the role of pigeonhole.

### Problem 2

Find the minimum number of students in a class such that three of them are born in the same month?

Solution: Number of month n =12

According to the given condition,

K+1 = 3

K = 2

M = kn +1 = 2*12 + 1 = 25.

### Problem 3

Show that from any three integers, one can always chose two so that $a^3$b – a$b^3$ is divisible by 10.

Solution: We can factories the term $a^3$b – a$b^3$ = ab(a + b)(a – b), which is always even, irrespective of the pair of integers we choose.

If one of three integers from the above factors is in the form of 5k, which is a multiple of 5, then our result is proved.

If none of the integers are a multiple of 5 then the chosen integers should be in the form of (5k)+-(1) and (5k)+-(2) respectively.

Clearly, two of these three numbers in the above factors from the given expression should lie in one of the above two from, which follows by the virtue of this principle.

These two integers are the ones such that their sum and difference is always divisible by 5. Hence, our result is proved.

### Problem 4

If n is a positive integer not divisible by 2 or 5 then n has a multiple made up of 1’s.

Watch the solution:

Categories

## Value of Sum | PRMO – 2018 | Question 16

Try this beautiful Problem based on Value of Sum from PRMO 2018, Question 16.

## Value of Sum – PRMO 2018, Question 16

What is the value of $\sum_{1 \leq i<j \leq 10 \atop i+j=\text { odd }}(i-j)-\sum_{1 \leq i<j \leq 10 \atop i+j=\text { even }}(i-j) ?$

• $50$
• $53$
• $55$
• $59$
• $65$

Odd-Even

Sum

integer

## Check the Answer

Answer:$55$

PRMO-2018, Problem 16

Pre College Mathematics

## Try with Hints

We have to find out the sum . Now substitite $i=1,2,3…9$ and observe the all odd-even cases……

Can you now finish the problem ……….

$i=1 \Rightarrow$$1+(2+4+6+8+10-3-5-7-9) =1-4+10=7 i=2 \Rightarrow$$0 \times 2+(3+5+7+9-4-6-8-10)$
$=-4$

$i=3 \Rightarrow$$1 \times 3+(4+6+8+10-5-7-9) =3-3+10=10 i=4 \Rightarrow$$ 0 \times 4+(5+7+9-6-8-10)=-3$
$i=5 \Rightarrow $$1 \times 5+(6+8+10-7-9)=5-2+10 =13 i=6 \Rightarrow$$ 0 \times 6+(7+9-8-10)=-2$
$i=7 \Rightarrow $$1 \times 7+(8+10-9)=7-1+10=16 i=8 \Rightarrow$$ 0 \times 8+(9-10)=-1$
$i=9 \Rightarrow$$1 \times 9+(10)=19$

Can you finish the problem……..

Therefore $S =(7+10+13+16+19)$-$(4-3-2-1)$ =$55$

Categories

## Good numbers Problem | PRMO-2018 | Question 22

Try this beautiful good numbers problem from Number theory from PRMO 2018, Question 22.

## Good numbers Problem – PRMO 2018, Question 22

A positive integer $k$ is said to be good if there exists a partition of ${1,2,3, \ldots, 20}$ into disjoint proper subsets such that the sum of the numbers in each subset of the partition is $k$. How many good numbers are there?

• $4$
• $6$
• $8$
• $10$
• $2$

Number theorm

good numbers

subset

## Check the Answer

Answer:$6$

PRMO-2018, Problem 22

Pre College Mathematics

## Try with Hints

What is good numbers ?

A good number is a number in which every digit is larger than the sum of digits of its right (all less significant bits than it). For example, 732 is a good number, $7>3+2$ and $3>2$ .

Given that $k$ is said to be good if there exists a partition of ${1,2,3, \ldots, 20}$ into disjoint proper subsets such that the sum of the numbers in each subset of the partition is $k$. Now at first we have to find out sum of these integers ${1,2,3, \ldots, 20}$. Later create some partitions such that two partitions be disjoint set and sum of the numbers of these partitions be good numbers

Can you now finish the problem ……….

Sum of numbers equals to $\frac{20 \times 21}{2}=210 \& 210=2 \times 3 \times 5 \times 7$

So $\mathrm{K}$ can be 21,30,35,47,70,105

Can you finish the problem……..

Case 1 :

$\mathrm{A}=\{1,2,3,4,5,16,17,18,19,20\}$, $\mathrm{B}=\{6,7,8,9,10,11,12,13,14,15\}$

Case 2 :

$A=\{20,19,18,13\}$, $B=\{17,16,15,12,10\}$, $C=\{1,2,3,4,5,6,7,8,9,11,14\}$

Case 3 :

$\mathrm{A}=\{20,10,12\}$, $\mathrm{B}=\{18,11,13\}$, $\mathrm{C}=\{16,15,9,2\}$, $\mathrm{D}=\{19,8,7,5,3\}$, $\mathrm{E}=\{1,4,6,14,17\}$

Case 4 :

$A=\{20,10\}, B=\{19,11\}$,$C=\{18,12\}, D=\{17,13\}$,$E=\{16,14\}$, $F=\{1,15,5\},$
$G=\{2,3,4,6,7,8\}$

Case 5 :

$A=\{20,15\}$, $B=\{19,16\}$, $C=\{18,17\}$, $D=\{14,13,8\}$, $E=\{12,11,10,2\},$
$F=\{1,3,4,5,6,7,9\}$

Case 6 :

$A=\{1,20\}$,$B=\{2,19\}$, $C=\{3,18\} \ldots \ldots \ldots \ldots$, $J=\{10,11\}$

Therefore Good numbers equal to $6$

Categories

## Polynomial Problem | PRMO-2018 | Question 30

Try this beautiful Polynomial Problem from Number theorm from PRMO 2018, Question 30.

## Polynomial Problem – PRMO 2018, Question 30

Let $P(x)=a_{0}+a_{1} x+a_{2} x^{2}+\ldots .+a_{n} x^{n}$ be a polynomial in which $a_{i}$ is non-negative integer for each $\mathrm{i} \in{0,1,2,3, \ldots, \mathrm{n}} .$ If $\mathrm{P}(1)=4$ and $\mathrm{P}(5)=136,$ what is the value of $\mathrm{P}(3) ?$

• $30$
• $34$
• $36$
• $39$
• $42$

Number theorm

Polynomial

integer

## Check the Answer

Answer:$34$

PRMO-2018, Problem 30

Pre College Mathematics

## Try with Hints

Given that $P(x)=a_{0}+a_{1} x+a_{2} x^{2}+\ldots .+a_{n} x^{n}$ where $\mathrm{P}(1)=4$ and $\mathrm{P}(5)=136$. Now we have to find out $P(3)$.

Therefore if we put $x=1$ and $x=5$ then we will get two relations . Using these relations we can find out $a_0$ , $a_1$, $a_2$ .

Can you now finish the problem ……….

$a_{0}+a_{1}+a_{2}+\ldots \ldots+a_{n}=4$
$\Rightarrow a_{i} \leq 4$
$a_{0}+5 a_{1}+5^{2} a_{2}+\ldots+a 5^{n} a_{n}=136$
$\Rightarrow a_{0}=1+5 \lambda \Rightarrow a_{0}=1$

Can you finish the problem……..

Hence $5 a_{1}+5^{2} a_{2}+\ldots \ldots+5^{n} a_{n}=135$
$a_{1}+5 a_{2}+\ldots 5^{n-1} a_{n-1}=27$
$\Rightarrow a_{1}=5 \lambda+2 \Rightarrow a_{1}=2$
$\Rightarrow 5 a_{2}+\ldots .5^{n-1} a_{n-1}=25$
$a_{2}+5 a_{3}+\ldots .5^{n-2} a_{n-2}=5$
$\Rightarrow a_{2}=5 \lambda \Rightarrow a_{2}=0$
$a_{3}+5 a_{4}+\ldots \ldots \ldots+5^{n-3} a_{n-3}=1$
$a_{3}=1$
$\Rightarrow a_{4}+5 a_{5}+\ldots .+5^{n-4} a_{n-3}=0$
$a_{4}=a_{5}=\ldots . a_{n}=0$
Hence $P(n)=x^{3}+2 x+1$
$P(3)=34$

Categories

## Digits Problem | PRMO – 2018 | Question 19

Try this beautiful Digits Problem from Number theorm from PRMO 2018, Question 19.

## Digits Problem – PRMO 2018, Question 19

Let $N=6+66+666+\ldots \ldots+666 \ldots .66,$ where there are hundred 6 ‘s in the last term in the sum. How many times does the digit 7 occur in the number $N ?$

• $30$
• $33$
• $36$
• $39$
• $42$

Number theorm

Digits Problem

integer

## Check the Answer

Answer:$33$

PRMO-2018, Problem 19

Pre College Mathematics

## Try with Hints

Given that $\mathrm{N}=6+66+666+……. \underbrace{6666 …..66}_{100 \text { times }}$

If you notice then we can see there are so many large terms. but we have to find out the sum of the digits. but since the number of digits are large so we can not calculate so eassily . we have to find out a symmetry or arrange the number so that we can use any formula taht we can calculate so eassily. if we multiply $\frac{6}{9}$ then it becomes $=\frac{6}{9}[9+99+\ldots \ldots \ldots \ldots+\underbrace{999 \ldots \ldots \ldots .99}_{100 \text { times }}]$

Can you now finish the problem ……….

$\mathrm{N}=\frac{6}{9}[9+99+\ldots \ldots \ldots \ldots+\underbrace{999 \ldots \ldots \ldots .99}_{100 \text { times }}]$
$=\frac{6}{9}\left[(10-1)+\left(10^{2}-1\right)+…….+\left(10^{100}-1\right)\right]$
$=\frac{6}{9}\left[\left(10+10^{2}+…..+10^{100}\right)-100\right]$

Can you finish the problem……..

$=\frac{6}{9}\left[\left(10^{2}+10^{3}+\ldots \ldots \ldots+10^{100}\right)-90\right]$
$=\frac{6}{9}\left(10^{2} \frac{\left(10^{99}-1\right)}{9}\right)-60$
$=\frac{200}{27}\left(10^{99}-1\right)-60$
$=\frac{200}{27}\underbrace{(999….99)}_{99 \text{times}}-60$
$=\frac{1}{3}\underbrace{(222…..200)}_{99 \mathrm{times}}-60$

$=\underbrace{740740 \ldots \ldots .7400-60}_{740 \text { comes } 33 \text { times }}$ $=\underbrace{740740 \ldots \ldots .740}_{32 \text { times }}+340$
$\Rightarrow 7$ comes 33 times

Categories

## External Tangent | AMC 10A, 2018 | Problem 15

Try this beautiful Problem on Geometry based on External Tangent from AMC 10 A, 2018. You may use sequential hints to solve the problem.

## External Tangent – AMC-10A, 2018- Problem 15

Two circles of radius 5 are externally tangent to each other and are internally tangent to a circle of radius 13 at points $A$ and $B$, as shown in the diagram. The distance $A B$ can be written in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. What is $m+n ?$

,

• $21$
• $29$
• $58$
• $69$
• $93$

Geometry

Triangle

Pythagoras

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2018 Problem-15

#### Check the answer here, but try the problem first

$69$

## Try with Hints

#### First Hint

Given that two circles of radius 5 are externally tangent to each other and are internally tangent to a circle of radius 13 at points $A$ and $B$. we have to find out the length $AB$.

Now join $A$ & $B$ and the points $Y$ & $Z$. If we can show that $\triangle XYZ \sim \triangle XAB$ then we can find out the length of $AB$.

Now can you finish the problem?

#### Second Hint

now the length of $YZ=5+5=10$ (as the length of the radius of smaller circle is $5$) and $XY=XA-AY=13-5=8$. Now $YZ|| AB$.therefore we can say that $\triangle XYZ \sim \triangle XAB$. therefore we can write $\frac{X Y}{X A}=\frac{Y Z}{A B}$

Now Can you finish the Problem?

#### Third Hint

From the relation we can say that $\frac{X Y}{X A}=\frac{Y Z}{A B}$

$\Rightarrow \frac{8}{13}=\frac{10}{AB}$

$\Rightarrow AB=\frac{13\times 10}{8}$

$\Rightarrow AB=\frac{65}{4}$ which is equal to $\frac{m}{n}$

Therefore $m+n=65+4=69$

Categories

## Dice Problem | AMC 10A, 2014| Problem No 17

Try this beautiful Problem on Probability based on Dice from AMC 10 A, 2014. You may use sequential hints to solve the problem.

## Dice Problem – AMC-10A, 2014 – Problem 17

Three fair six-sided dice are rolled. What is the probability that the values shown on two of the dice sum to the value shown on the remaining die?

,

• $\frac{1}{6}$
• $\frac{13}{72}$
• $\frac{7}{36}$
• $\frac{5}{24}$
• $\frac{2}{9}$

combinatorics

Dice-problem

Probability

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2014 Problem-17

#### Check the answer here, but try the problem first

$\frac{5}{24}$

## Try with Hints

#### First Hint

Total number of dice is $3$ and each dice $6$ possibility. therefore there are total $6^{3}=216$ total possible rolls. we have to find out the probability that the values shown on two of the dice sum to the value shown on the remaining die.

Without cosidering any order of the die , the possible pairs are $(1,1,2),(1,2,3),(1,3,4)$,$(1,4,5),(1,5,6),(2,2,4),(2,3,5)$,$(2,4,6),(3,3,6)$

Now can you finish the problem?

#### Second Hint

Clearly $(1,1,1).(2,2,4),(3,3,6)$ this will happen in $\frac{3 !}{2}=3$ way

$(1,2,3),(1,3,4)$,$(1,4,5),(1,5,6),(2,3,5)$,$(2,4,6),$this will happen in $3 !=6$ ways

Now Can you finish the Problem?

#### Third Hint

Therefore, total number of ways $3\times3+6\times6=45$ so that sum of the two dice will be the third dice

Therefore the required answer is $\frac{45}{216}$=$\frac{5}{24}$

Categories

## Problem on Curve | AMC 10A, 2018 | Problem 21

Try this beautiful Problem on Algebra based on Problem on Curve from AMC 10 A, 2018. You may use sequential hints to solve the problem.

## Curve- AMC 10A, 2018- Problem 21

Which of the following describes the set of values of $a$ for which the curves $x^{2}+y^{2}=a^{2}$ and $y=x^{2}-a$ in the real $x y$ -plane intersect at
exactly 3 points?

• $a=\frac{1}{4}$
• $\frac{1}{4}<a<\frac{1}{2}$
• $a>\frac{1}{4}$
• $a=\frac{1}{2}$
• $a>\frac{1}{2}$

Algebra

greatest integer

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2018 Problem-14

#### Check the answer here, but try the problem first

$a>\frac{1}{2}$

## Try with Hints

#### First Hint

We have to find out the value of $a$

Given that $y=x^{2}-a$ . now if we Substitute this value in $x^{2}+y^{2}=a^{2}$ we will get a quadratic equation of $x$ and $a$. if you solve this equation you will get the value of $a$

Now can you finish the problem?

#### Second Hint

After substituting we will get $x^{2}+\left(x^{2}-a\right)^{2}$=$a^{2} \Longrightarrow x^{2}+x^{4}-2 a x^{2}=0 \Longrightarrow x^{2}\left(x^{2}-(2 a-1)\right)=0$

therefore we can say that either $x^2=0\Rightarrow x=0$ or $x^2-(2a-1)=0$

$\Rightarrow x=\pm \sqrt {2a-1}$. Therefore

Now Can you finish the Problem?

#### Third Hint

Therefore $\sqrt {2a-1} > 0$

$\Rightarrow a>\frac{1}{2}$

Categories

## Right-angled Triangle | AMC 10A, 2018 | Problem No 16

Try this beautiful Problem on Geometry based on Right-angled triangle from AMC 10 A, 2018. You may use sequential hints to solve the problem.

## Right-angled triangle – AMC-10A, 2018- Problem 16

Right triangle $A B C$ has leg lengths $A B=20$ and $B C=21$. Including $\overline{A B}$ and $\overline{B C}$, how many line segments with integer length can be drawn from vertex $B$ to a point on hypotenuse $\overline{A C} ?$

,

• $5$
• $8$
• $12$
• $13$
• $15$

Geometry

Triangle

Pythagoras

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2018 Problem-16

#### Check the answer here, but try the problem first

$13$

## Try with Hints

#### First Hint

Given that $\triangle ABC$ is a Right-angle triangle and $AB=20$ and $BC=21$. we have to find out how many line segments with integer length can be drawn from vertex $B$ to a point on hypotenuse $\overline{AC}$?

Let $P$ be the foot of the altitude from $B$ to $AC$. therefore $BP$ is the shortest legth . $B P=\frac{20 \cdot 21}{29}$ which is between $14$ and $15$.

Now can you finish the problem?

#### Second Hint

let us assume a line segment $BY$ with $Y$ on $AC$which is starts from $A$ to $P$ . So if we move this line segment the length will be decreases and the values will be look like as $20,…..,15$. similarly if we moving this line segment $Y$ from $P$ to $C$ hits all the integer values from $15, 16, \dots, 21$.

Now Can you finish the Problem?

#### Third Hint

Therefore numbers of total line segments will be $13$

Categories

## Finding Greatest Integer | AMC 10A, 2018 | Problem No 14

Try this beautiful Problem on Algebra based on finding greatest integer from AMC 10 A, 2018. You may use sequential hints to solve the problem.

## Finding Greatest Integer – AMC-10A, 2018- Problem 14

What is the greatest integer less than or equal to $\frac{3^{100}+2^{100}}{3^{96}+2^{96}} ?$

• $80$
• $81$
• $96$
• $97$
• $625$

Algebra

greatest integer

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2018 Problem-14

#### Check the answer here, but try the problem first

$80$

## Try with Hints

#### First Hint

The given expression is $\frac{3^{100}+2^{100}}{3^{96}+2^{96}} ?$

We have to find out the greatest integer which is less than or equal to the given expression .

Let us assaume that $x=3^{96}$ and $y=2^{96}$

Therefore the given expression becoms $\frac{81 x+16 y}{x+y}$

Now can you finish the problem?

#### Second Hint

Now $\frac{81 x+16 y}{x+y}$

=$\frac{16 x+16 y}{x+y}+\frac{65 x}{x+y}$

$=16+\frac{65 x}{x+y}$

Now if we look very carefully we see that $\frac{65 x}{x+y}<\frac{65 x}{x}=65$

Therefore $16+\frac{65 x}{x+y}<16+65=81$

Now Can you finish the Problem?

#### Third Hint

Therefore less than $81$ , the answer will be $80$