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 - Pigeons in hole

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:

Some Useful links:

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\)

Key Concepts


Game problem

Chess board

combination

Suggested Book | Source | Answer


Suggested Reading

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$

Subscribe to Cheenta at Youtube


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\)

Key Concepts


Combination

Combinatorics

Probability

Suggested Book | Source | Answer


Suggested Reading

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$

Subscribe to Cheenta at Youtube


Trigonometry | PRMO-2018 | Problem No-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\)

Key Concepts


Trigonometry

Logarithm

Suggested Book | Source | Answer


Suggested Reading

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$

Subscribe to Cheenta at Youtube


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

Key Concepts


combinatorics

Dice-problem

Probability

Suggested Book | Source | Answer


Suggested Reading

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

Subscribe to Cheenta at Youtube


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\)

Key Concepts


Chessboard

Combinatorics

Probability

Suggested Book | Source | Answer


Suggested Reading

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


Subscribe to Cheenta at Youtube


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$

Key Concepts


combinatorics

Coin toss

Probability

Suggested Book | Source | Answer


Suggested Reading

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\)

Subscribe to Cheenta at Youtube


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


Suggested Reading

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\)

Subscribe to Cheenta at Youtube


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$

Key Concepts


Algebra

Linear Equation

Suggested Book | Source | Answer


Suggested Reading

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$

Subscribe to Cheenta at Youtube


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$

Key Concepts


Probability

Combination

Marbles

Suggested Book | Source | Answer


Suggested Reading

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$

Subscribe to Cheenta at Youtube