# 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 Discrete 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:

# Chessboard Problem | PRMO-2018 | Problem No-26

Try this beautiful Chessboard Problem based on Chessboard from PRMO - 2018.

## Chessboard Problem - PRMO 2018- Problem 26

What is the number of ways in which one can choose 60 units square from a $11 \times 11$ chessboard such that no two chosen square have a side in common?

,

• $$56$$
• $$58$$
• $$60$$
• $$62$$
• $$64$$

Game problem

Chess board

combination

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

Prmo-2018, Problem-26

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

$$62$$

## Try with Hints

#### <br>First Hint

Total no. of squares $=121$
Out of these, 61 squares can be placed diagonally. From these any 60 can be selected in ${ }^{61} C_{60}$ ways $=61$

Now can you finish the problem?

#### Second Hint

From the remaining 60 squares 60 can be chosen in any one way

Total equal to ${ }^{61} \mathrm{C}{60}+{ }^{60} \mathrm{C}{60}=61+1=62$

# Chocolates Problem | PRMO - 2018 | Problem No. - 28

Try this beautiful Problem on Combinatorics from integer based on chocolates from PRMO -2018

## Chocolates Problem - PRMO 2018- Problem 28

Let N be the number of ways of distributing 8 chocolates of different brands among 3 children such that each child gets at least one chocolate, and no two children get the same number of chocolates. Find the sum of the digits of $\mathrm{N}$.

,

• $$28$$
• $$90$$
• $$24$$
• $$16$$
• $$27$$

Combination

Combinatorics

Probability

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

Prmo-2018, Problem-28

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

$$24$$

## Try with Hints

#### First Hint

we have to distribute $$8$$ chocolates among $$3$$ childrens and the condition is Eight chocolets will be different brands that each child gets at least one chocolate, and no two children get the same number of chocolates. Therefore thr chocolates distributions will be two cases as shown below.....

Now can you finish the problem?

#### Second Hint

case 1:$(5,2,1)$

Out of $$8$$ chocolates one of the boys can get $$5$$ chocolates .So $$5$$ chocolates can be choosen from $$8$$ chocolates in $$8 \choose 5$$ ways.

Therefore remaining chocolates are $$3$$ . Out of $$3$$ chocolates another one of the boys can get $$2$$ chocolates .So $$2$$ chocolates can be choosen from $$3$$ chocolates in $$3 \choose 2$$ ways.

Therefore remaining chocolates are $$1$$ . Out of $$1$$ chocolates another one of the boys can get $$1$$ chocolates .So $$1$$ chocolates can be choosen from $$1$$ chocolates in $$1 \choose 1$$ ways.

Therefore number of ways for first case will be $$8 \choose 5$$ $$\times$$ $$3 \choose 2$$ $$\times$$ $$1 \choose 1$$$$\times$$ $3!$=$\frac{8}{2!.5!.1!}$$\times 3 Case 2:(4,3,1) Out of $$8$$ chocolates one of the boys can get $$4$$ chocolates .So $$4$$ chocolates can be choosen from $$8$$ chocolates in $$8 \choose 4$$ ways. Therefore remaining chocolates are $$4$$ . Out of $$4$$ chocolates another one of the boys can get $$3$$ chocolates .So $$3$$ chocolates can be choosen from $$4$$ chocolates in $$4 \choose 3$$ ways. Therefore remaining chocolates are $$1$$ . Out of $$1$$ chocolates another one of the boys can get $$1$$ chocolates .So $$1$$ chocolates can be choosen from $$1$$ chocolates in $$1 \choose 1$$ ways. Therefore number of ways for first case will be $$8 \choose 4$$ $$\times$$ $$4 \choose 3$$ $$\times$$ $$1 \choose 1$$$$\times$$ 3!=\frac{8}{4!.3!.1!}$$\times 3$

Can you finish the problem...?

#### Third Hint

Therefore require number of ways =$\frac{8}{2!.5!.1!}$$\times 3+\frac{8}{4!.3!.1!}$$\times 3$=$24$

# Trigonometry | PRMO-2018 | Problem No-14

Try this beautiful Problem on Trigonometry from PRMO -2018

## Trigonometry Problem - PRMO 2018- Problem 14

If $x=\cos 1^{\circ} \cos 2^{\circ} \cos 3^{\circ} \ldots . \cos 89^{\circ}$ and $y=\cos 2^{\circ} \cos 6^{\circ} \cos 10^{\circ} \ldots \ldots \cos 86^{\circ},$ then what is the integer nearest to $\frac{2}{7} \log _{2}(\mathrm{y} / \mathrm{x}) ?$

,

• $$28$$
• $$19$$
• $$24$$
• $$16$$
• $$27$$

Trigonometry

Logarithm

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

Prmo-2018, Problem-14

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

$$19$$

## Try with Hints

#### First Hint

Given that $x=\cos 1^{\circ} \cos 2^{\circ} \cos 3^{\circ} \cdots \cos 89^{\circ}$

$$\Rightarrow x=\cos 1^{\circ}\cos 89^{\circ}\cos 2^{\circ}\cos 88^{\circ}........\cos 45^{\circ}$$

$$\Rightarrow x=\cos 1^{\circ}\sin 1^{\circ}\cos 2^{\circ}\cos 2^{\circ}........\cos 45^{\circ}$$ ( as cos(90-x)=sin x)

$$\Rightarrow x=\frac{1}{2^{44}} (2 \cos 1^{\circ} \sin 1^{\circ}) (2\cos 2^{\circ}\sin 2^{\circ})........\cos 45^{\circ}$$

$\Rightarrow x =\frac{ \cos 45^{\circ} \cdot \sin 2^{\circ} \cdot \sin 4^{\circ} \cdots \sin 88}{ 2^{44}}$ (as sin 2x= 2 sin x cos x)

Now can you finish the problem?

#### Second Hint

Therefore we can say that
$x=\frac{1}{2^{1 / 2}} \times \frac{\sin 4^{\circ} \cdot \sin 8^{\circ} \cdots \sin 88^{\circ}}{2^{44} \times 2^{22}}$
$=\frac{\sin \left(90-86^{\circ}\right) \cdot \sin \left(90-84^{\circ}\right) \cdots \sin (90-2)}{2^{66} \cdot 2^{1 / 2}}$
$=\frac{\cos 2^{\circ} \cdot \cos 6^{\circ} \cdot \cos 86^{\circ}}{2^{133 / 2}}$
$x=\frac{y}{2^{133 / 2}}$

Can you finish the problem...?

#### Third Hint

$\frac{y}{x}=2^{133 / 2}$
$\frac{2}{7} \log \left(\frac{y}{x}\right)=\frac{2}{7} \times \log _{2}(2)^{133 / 2}$
$=\frac{2}{7} \times \frac{133}{2}$
$=19$

# 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}$

# Colour Problem | PRMO-2018 | Problem No-27

Try this beautiful Combinatorics Problem based on colour from integer from Prmo-2018.

## Colour Problem- PRMO 2018- Problem 27

What is the number of ways in which one can colour the square of a $4 \times 4$ chessboard with colours red and blue such that each row as well as each column has exactly two red squares and blue
squares?

,

• $$28$$
• $$90$$
• $$32$$
• $$16$$
• $$27$$

Chessboard

Combinatorics

Probability

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

Prmo-2018, Problem-27

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

$$90$$

## Try with Hints

#### First Hint

First row can be filled by ${ }^{4} \mathrm{C}_{2}$ ways $=6$ ways.
Case-I

Second row is filled same as first row
$\Rightarrow$
here second row is filled by one way
$3^{\text {rd }}$ row is filled by one way
$4^{\text {th }}$ row is filled by one way

Total ways in Case-I equals to ${ }^{4} \mathrm{C}_{1} \times 1 \times 1 \times 1=6$ ways

now we want to expand the expression and simplify it..............

#### Second Hint

Case-II $\quad$ Exactly $1$ R & $1$ B is interchanged in second row in comparision to $1^{\text {st }}$ row
$\Rightarrow$
here second row is filled by $2 \times 2$ way
$3^{r d}$ row is filled by two ways
$4^{\text {th }}$ row is filled by one way
$\Rightarrow$
Total ways in Case-II equals to ${ }^{4} \mathrm{C}_{1} \times 2 \times 2 \times 2 \times 1=48$ ways

#### Third Hint

Case-III $\quad$ Both $\mathrm{R}$ and $\mathrm{B}$ is replaces by other in second row as compared to $1^{\text {st }}$ row
$\Rightarrow$
here second row is filled by 1 way
$3^{r d}$ row is filled by $4 \choose 2$ ways

$\Rightarrow \quad$ Total ways in $3^{\text {th }}$ Case equals to ${ }^{4} \mathrm{C}_{2} \times 1 \times 6 \times 1=36$ ways
$\Rightarrow \quad$ Total ways of all cases equals to 90 ways

# Coin Toss Problem | AMC 10A, 2017| Problem No 18

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

## Coin Toss - AMC-10A, 2017- Problem 18

Amelia has a coin that lands heads with probability $\frac{1}{3}$, and Blaine has a coin that lands on heads with probability $\frac{2}{5}$. Amelia and Blaine alternately toss their coins until someone gets a head; the first one to get a head wins. All coin tosses are independent. Amelia goes first. The probability that Amelia wins is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. What is $q-p ?$

,

• $1$
• $2$
• $3$
• $4$
• $5$

combinatorics

Coin toss

Probability

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2017 Problem-18

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

$4$

## Try with Hints

#### First Hint

Amelia has a coin that lands heads with probability $\frac{1}{3}$, and Blaine has a coin that lands on heads with probability $\frac{2}{5}$. Amelia and Blaine alternately toss their coins until someone gets a head; the first one to get a head wins.

Now can you finish the problem?

#### Second Hint

Let $P$ be the probability Amelia wins. Note that $P=$ chance she wins on her first turn $+$ chance she gets to her second turn $\cdot \frac{1}{3}+$ chance she gets to her third turn $\cdot \frac{1}{3} \ldots$ This can be represented by an infinite geometric series,

Therefore the value of $$P$$ will be $P=\frac{\frac{1}{3}}{1-\frac{2}{3} \cdot \frac{3}{5}}=\frac{\frac{1}{3}}{1-\frac{2}{5}}=\frac{\frac{1}{3}}{\frac{3}{5}}=\frac{1}{3} \cdot \frac{5}{3}=\frac{5}{9}$ which is of the form $$\frac{p}{q}$$

Now Can you finish the Problem?

#### Third Hint

Therefore $$q-p=9-5=4$$

# Recursion Problem | AMC 10A, 2019| Problem No 15

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

## Recursion- AMC-10A, 2019- Problem 15

A sequence of numbers is defined recursively by $a_{1}=1, a_{2}=\frac{3}{7},$ and $a_{n}=\frac{a_{n-2} \cdot a_{n-1}}{2 a_{n-2}-a_{n-1}}$

for all $n \geq 3$ Then $a_{2019}$ can be written as $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. What is $p+q ?$

• $2020$
• $4039$
• $6057$
• $6061$
• $8078$

### Key Concepts

Algebra

Recursive formula

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2019 Problem-15

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

$8078$

## Try with Hints

#### First Hint

The given expression is $a_{n}=\frac{a_{n-2} \cdot a_{n-1}}{2 a_{n-2}-a_{n-1}}$ and given that $a_{1}=1, a_{2}=\frac{3}{7}$. we have to find out $$a_{2019}$$?

at first we may use recursive formula we can find out $$a_3$$ , $$a_4$$ with the help of $$a_1$$, $$a_2$$. later we can find out $$a_n$$

Now can you finish the problem?

#### Second Hint

Given that $a_{n}=\frac{a_{n-2} \cdot a_{n-1}}{2 a_{n-2}-a_{n-1}}$

Now $$n=3$$ then $a_{3}=\frac{a_{(3-2)} \cdot a_{(3-1)}}{2 a_{(3-2)}-a_{(3-1)}}$

$$\Rightarrow$$ $a_{3}=\frac{a_{(1)} \cdot a_{(2)}}{2 a_{(1)}-a_{(2)}}$

$$\Rightarrow$$ $a_{3}=\frac{a_{(1)} \cdot a_{(2)}}{2 a_{(1)}-a_{(2)}}$

$$\Rightarrow$$ $a_{3}=\frac{1*\frac{3}{7}}{2*1-\frac{3}{7}}$

$$\Rightarrow$$ $a_{3}=\frac{3}{7}$

Similarly if we put $$n=4$$ we get $$a_4=\frac{3}{15}$$ (where $a_{1}=1, a_{2}=\frac{3}{7}$,$$a_3=\frac{3}{7}$$)

Continue this way we $a_{n}=\frac{3}{4 n-1}$

So can you find out the value of $$a_{2019}$$?

Now Can you finish the Problem?

#### Third Hint

Now $a_{n}=\frac{3}{4 n-1}$

Put $$n=2019$$

$a_{2019}=\frac{3}{8075}$ which is the form of $$\frac{p}{q}$$

Therefore $$p+q=8078$$

# Roots of Polynomial | AMC 10A, 2019| Problem No 24

Try this beautiful Problem on Algebra based on Roots of Polynomial from AMC 10 A, 2019. You may use sequential hints to solve the problem.

## Algebra- AMC-10A, 2019- Problem 24

Let $p, q,$ and $r$ be the distinct roots of the polynomial $x^{3}-22 x^{2}+80 x-67$. It is given that there exist real numbers $A, B$, and $C$ such that $\frac{1}{s^{3}-22 s^{2}+80 s-67}=\frac{A}{s-p}+\frac{B}{s-q}+\frac{C}{s-r}$

for all $s \notin{p, q, r} .$ What is $\frac{1}{A}+\frac{1}{B}+\frac{1}{C} ?$

,

• $243$
• $244$
• $245$
• $246$
• $247$

Algebra

Linear Equation

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2019 Problem-24

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

$244$

## Try with Hints

#### First Hint

The given equation is $\frac{1}{s^{3}-22 s^{2}+80 s-67}=\frac{A}{s-p}+\frac{B}{s-q}+\frac{C}{s-r}$.....................(1)

If we multiply both sides we will get

Multiplying both sides by $(s-p)(s-q)(s-r)$ we will get
$$1=A(s-q)(s-r)+B(s-p)(s-r)+C(s-p)(s-q)$$

Now can you finish the problem?

#### Second Hint

Now Put $S=P$ we will get $\frac{1}{A}=(p-q)(p-r)$............(2)

Now Put $S=q$ we will get $\frac{1}{B}=(q-p)(q-r)$...........(3)

Now Put $S=r$ we will get $\frac{1}{C}=(r-p)(r-q)$...........(4)

Now Can you finish the Problem?

#### Third Hint

Adding (2) +(3)+(4) we get,$\frac{1}{A}+\frac{1}{B}+\frac{1}{C}=p^{2}+q^{2}+r^{2}-p q-q r-p r$

Now Using Vieta's Formulas, $p^{2}+q^{2}+r^{2}=(p+q+r)^{2}-2(p q+q r+p r)=324$ and $p q+q r+p r=80$

Therefore the required answer is $324-80$=$244$

# Probability in Marbles | AMC 10A, 2010| Problem No 23

Try this beautiful Problem on Probability in Marbles based on smallest value AMC 10 A, 2010. You may use sequential hints to solve the problem.

## Probability in Marbles - AMC-10A, 2010- Problem 23

Each of 2010 boxes in a line contains a single red marble, and for $1 \leq k \leq 2010$, the box in the $k$ th position also contains $k$ white marbles. Isabella begins at the first box and successively draws a single marble at random from each box, in order. She stops when she first draws a red marble. Let $P(n)$ be the probability that Isabella stops after drawing exactly $n$ marbles. What is the smallest value of $n$ for which $P(n)<\frac{1}{2010}$ ?

,

• $20$
• $22$
• $44$
• $45$
• $46$

Probability

Combination

Marbles

## Suggested Book | Source | Answer

Pre College Mathematics

#### Source of the problem

AMC-10A, 2010 Problem-23

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

$45$

## Try with Hints

#### First Hint

Given that Each of 2010 boxes in a line contains a single red marble, and for $1 \leq k \leq 2010$, the box in the $k$ th position also contains $k$ white marbles..

Therefore The probability of drawing a white marble from box $k$ is $\frac{k}{k+1}$ and the probability of drawing a red marble from box $k$ is $\frac{1}{k+1}$

Now can you finish the problem?

#### Second Hint

Also given that She stops when she first draws a red marble. Let $P(n)$ be the probability that Isabella stops after drawing exactly $n$ marbles.

Therefore we can say $P(n)=\left(\frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdots \frac{n-1}{n}\right) \cdot \frac{1}{n+1}=\frac{1}{n(n+1)}$

Now Can you finish the Problem?

#### Third Hint

Therefore the probability $\frac{1}{n(n+1)}<\frac{1}{2010}$ or $n(n+1)>2010$

Now $n^2+n-2010>0$

Now to find out the factorization we see that $45 \times 46=2070$ and $44 \times 45 =1980$

As $n$ is smallest so $n=45$