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

# Median of numbers | AMC-10A, 2020 | Problem 11

Try this beautiful problem from Geometry based on Median of numbers from AMC 10A, 2020.

## Median of numbers - AMC-10A, 2020- Problem 11

What is the median of the following list of $4040$ numbers$?$

$$1,2,3,.......2020,1^2,2^2,3^2...........{2020}^2$$

• $1989.5$
• $1976.5$
• $1972.5$

### Key Concepts

Median

Algebra

square numbers

Answer: $1976.5$

AMC-10A (2020) Problem 11

Pre College Mathematics

## Try with Hints

To find the median we need to know how many terms are there and the position of the numbers .here two types of numbers, first nonsquare i.e (1,2,3......2020) and squares numbers i.e $$(1^2,2^2,3^2......2020^2)$$.so We want to know the $$2020$$th term and the $$2021$$st term to get the median.

Can you now finish the problem ..........

Now less than 2020 the square number is $${44}^2$$=1936 and if we take $${45}^2$$=2025 which is greater than 2020.therefore we take the term that $$1,2,3...2020$$ trms + 44 terms=$$2064$$ terms.

can you finish the problem........

since $44^{2}$ is $44+45=89$ less than $45^{2}=2025$ and 84 less than 2020 we will only need to consider the perfect square terms going down from the 2064 th term, 2020, after going down $84$ terms. Since the $2020$th and $2021$st terms are only $44$ and $43$ terms away from the $2064$th term, we can simply subtract $44$ from $2020$ and $43$ from $2020$ to get the two terms, which are $1976$ and $1977$. Averaging the two,=$$1976.5$$

# Largest area Problem | AMC 8, 2003 | Problem 22

Try this beautiful problem from Geometry based Largest area.

## Largest area - AMC-8, 2003 - Problem 22

The following figures are composed of squares and circles. Which figure has a shaded region with largest area?

• $A$
• $B$
• $C$

### Key Concepts

Geometry

Circle

Square

Answer:$C$

AMC-8 (2003) Problem 22

Pre College Mathematics

## Try with Hints

To find out the largest area at first we have to find out the radius of the circles . all the circles are inscribed ito the squares .now there is a relation between the radius and the side length of the squares....

Can you now finish the problem ..........

area of circle =$$\pi r^2$$

can you finish the problem........

In A:

Total area of the square =$$2^2=4$$

Now the radius of the inscribed be 1(as the diameter of circle = side length of the side =2)

Area of the inscribed circle is $$\pi (1)^2=\pi$$

Therefore the shaded area =$$4- \pi$$

In B:

Total area of the square =$$2^2=4$$

There are 4 circle and radius of one circle be $$\frac{1}{2}$$

Total area pf 4 circles be $$4 \times \pi \times (\frac{1}{2})^2=\pi$$

Therefore the shaded area =$$4- \pi$$

In C:

Total area of the square =$$2^2=4$$

Now the length of the diameter = length of the diagonal of the square=2

Therefore radius of the circle=$$\pi$$ and lengthe of the side of the square=$$\sqrt 2$$

Thertefore area of the shaded region=Area of the square-Area of the circle=$$\pi (1)^2-(\sqrt 2)^2$$=$$\pi – 2$$

# The area of trapezoid | AMC 8, 2003 | Problem 21

Try this beautiful problem from Geometry: The area of trapezoid

## The area of trapezoid - AMC-8, 2003- Problem 21

The area of trapezoid ABCD is 164 $$cm^2$$. The altitude is  8 cm, AB is 10 cm, and CD is 17 cm. What is BC in centimeters?

,

i

• $8$
• $10$
• $15$

### Key Concepts

Geometry

trapezoid

Triangle

Answer: $10$

AMC-8 (2003) Problem 21

Pre College Mathematics

## Try with Hints

Draw two altitudes from the points B and C On the straight line AD at D and E respectively.

Can you now finish the problem ..........

Now the Triangle ABD and Triangle CED, are right angle triangle and BD=CE= 8 cm

can you finish the problem........

Given that the area of the trapezoid is 164 sq.unit

Draw two altitudes from the points B and C On the straight line AD at D and E respectively.

Now the Triangle ABD and Triangle CED, are right angle triangle and BD=CE= 8 cm

Using Pythagorean rules on the triangle ABD,we have...

$$(AD)^2 + (BD)^2 =(AB)^2$$

$$\Rightarrow (AD)^2 + (8)^2 =(10)^2$$

$$\Rightarrow (AD)^2 =(10)^2 - (8)^2$$

$$\Rightarrow (AD)^2 = 36$$

$$\Rightarrow (AD) =6$$

Using Pythagorean rules on the triangle CED,we have...

$$(CE)^2 + (DE)^2 =(DC)^2$$

$$\Rightarrow (CE)^2 + (8)^2 =(17)^2$$

$$\Rightarrow (CE)^2 =(17)^2 - (8)^2$$

$$\Rightarrow (CE)^2 = 225$$

$$\Rightarrow (CE) =15$$

Let BC= DE=x

Therefore area of the trapezoid=$$\frac{1}{2} \times (AD+BC) \times 8$$=164

$$\Rightarrow \frac{1}{2} \times (6+x+15) \times 8$$ =164

$$\Rightarrow x=10$$

Therefore BC=10 cm

# Triangle and Quadrilateral | AMC-10A, 2005 | Problem 25

Try this beautiful problem from Geometry: Area of Triangle and Quadrilateral from AMC 10A, 2005.

## Ratios of the areas of Triangle and Quadrilateral - AMC-10A, 2005- Problem 25

In $ABC$ we have $AB = 25$, $BC = 39$, and $AC=42$. Points $D$ and $E$ are on $AB$ and $AC$ respectively, with $AD = 19$ and $AE = 14$. What is the ratio of the area of triangle $ADE$ to the area of the quadrilateral $BCED$?

• $$\frac{19}{56}$$
• $$\frac{19}{66}$$
• $$\frac{17}{56}$$
• $$\frac{11}{56}$$
• $$\frac{19}{37}$$

### Key Concepts

Geometry

Triangle

Answer: $$\frac{19}{56}$$

AMC-10A (2005) Problem 25

Pre College Mathematics

## Try with Hints

Given that $AB = 25$, $BC = 39$, and $AC=42$.we have to find out Ratios of the areas of Triangle$$\triangle ADE$$ and the quadrilateral $$CBED$$.So if we can find out the area the $$\triangle ADE$$ and area of the $$\triangle ABC$$ ,and subtract $$\triangle ADE$$ from $$\triangle ABC$$ then we will get area of the region $$CBDE$$.Can you find out the area of $$CBDE$$?

Can you find out the required area.....?

Now $$\frac{\triangle ADE}{\triangle ABC}=\frac{AD}{AB}.\frac{AE}{AC}=\frac{19}{25}.\frac{14}{42}=\frac{19}{75}$$

Therefore area of $$BCED$$=area of $$\triangle ABC$$-area of $$\triangle ADE$$.Now can you find out Ratios of the areas of Triangle and the quadrilateral?

can you finish the problem........

$$\frac{[A D E]}{[B C E D]}=\frac{[A D E]}{[A B C]-[A D E]}$$
=$$\frac{1}{[A B C] /[A D E]-1}$$
=$$\frac{1}{75 / 19-1}$$

=$$\frac{19}{56}$$

# AP GP Problem | AMC-10A, 2004 | Question 18

Try this beautiful problem from Algebra : AP & GP from AMC 10A, 2004.

## AP GP - AMC-10A, 2004- Problem 18

A sequence of three real numbers forms an arithmetic progression with a first term of $$9$$. If $$2$$ is added to the second term and $$20$$ is added to the third term, the three resulting numbers form a geometric progression. What is the smallest possible value for the third term in the geometric progression?

• $$1$$
• $$4$$
• $$36$$
• $$49$$
• $$81$$

### Key Concepts

Algebra

AP

GP

Answer: $$1$$

AMC-10A (2003) Problem 18

Pre College Mathematics

## Try with Hints

We assume the common difference in the AP series is $$d$$ .....Therefore the numbers will be $$9, (9+d),(9+2d)$$ .Therefore according to the condition if we add $$2$$ with $$2$$nd term and add $$20$$ to the third term the numbers becomes in Geometric Progression........$$9$$ , $$(9+d+2)=11+d$$ , $$(9+2d+20)=29+2d$$

can you finish the problem........

Now according to the Geometric Progression , $$\frac{11+d}{9}=\frac{29+d}{11+d}$$

$$\Rightarrow (11+d)^2 =9(29+2d)$$

$$\Rightarrow d^2 +4d-140=0$$

$$\Rightarrow (d+14)(d-10)=0$$

$$\Rightarrow 10 ,-14$$

can you finish the problem........

Therefore we choose the value of $$d=-14$$ (as smallest possible value for the third term)

The third term will be $$2(-14)+29=1$$

# Probability in Divisibility | AMC-10A, 2003 | Problem 15

Try this beautiful problem from AMC 10A, 2003 based on Probability in Divisibility.

## Probability in Divisibility - AMC-10A, 2003- Problem 15

What is the probability that an integer in the set $${1,2,3,…,100}$$ is divisible by $$2$$ and not divisible by $$3$$?

• $$\frac {33}{100}$$
• $$\frac{1}{6}$$
• $$\frac{17}{50}$$
• $$\frac{1}{2}$$
• $$\frac{18}{25}$$

### Key Concepts

Number system

Probability

divisibility

Answer: $$\frac{17}{50}$$

AMC-10A (2003) Problem 15

Pre College Mathematics

## Try with Hints

There are total number of integers are $$100$$.and numer of integers divisible by $$2$$ is $$\frac{100}{2}$$=$$50$$. Now we have to find out divisible by $$2$$ and not divisible by $$3$$. so at first we have to find out the numbers of integers which are divisible by $$2$$ and $$3$$ both.......

can you finish the problem........

To be divisible by both $$2$$ and $$3$$, a number must be divisible by the lcm of $$(2,3)=6$$.

Therefore numbers of integers which are divisible by $$6$$=$$\frac{100}{6}=16$$ (between $$1$$ & $$100$$)

can you finish the problem........

Therefore the number of integers which are divisible by $$2$$ and not divisible by $$3$$= $$50 - 16=34$$.

So require probability= $$\frac{34}{100}=\frac{17}{50}$$

# Area of the Region Problem | AMC-10A, 2007 | Problem 24

Try this beautiful problem from Geometry: Area of the region

## Problem on Area of the Region - AMC-10A, 2007- Problem 24

Circle centered at $$A$$ and $$B$$ each have radius $$2$$, as shown. Point $$O$$ is the midpoint of $$\overline{AB}$$, and $$OA = 2\sqrt {2}$$. Segments $$OC$$ and $$OD$$ are tangent to the circles centered at $A$ and $B$, respectively, and $EF$ is a common tangent. What is the area of the shaded region $$ECODF$$?

• $$\pi$$
• $$7\sqrt 3 -\pi$$
• $$8\sqrt 2 -4-\pi$$

### Key Concepts

Geometry

Triangle

similarity

Answer: $$8\sqrt 2 -4-\pi$$

AMC-10A (2007) Problem 24

Pre College Mathematics

## Try with Hints

We have to find out the area of the region $$ECODF$$ i.e of gray shaded region.this is not any standard geometrical figure (such as circle,triangle...etc).so we can not find out the value easily.Now if we join $$AC$$,$$AE$$,$$BD$$,$$BF$$.Then $$ABFE$$ is a rectangle.then we can find out the required area by [ area of rectangle $$ABEF$$- (area of arc $$AEC$$+area of $$\triangle ACO$$+area of $$\triangle BDO$$+ area of arc $$BFD$$)]

Can you find out the required area.....?

Given that Circle centered at $$A$$ and $$B$$ each have radius $$2$$ and Point $$O$$ is the midpoint of $$\overline{AB}$$, and $$OA = 2\sqrt {2}$$

Area of $$ABEF$$=$$2 \times 2 \times 2\sqrt 2$$=$$8\sqrt 2$$

Now $$\triangle{ACO}$$ is a right triangle. We know $$AO=2\sqrt{2}$$and $$AC=2$$, so $$\triangle{ACO}$$ is isosceles, a $$45$$-$$45$$ right triangle.$$\overline{CO}$$ with length $$2$$. The area of $$\triangle{ACO}=\frac{1}{2} \times base \times height=2$$. By symmetry, $$\triangle{ACO}\cong\triangle{BDO}$$, and so the area of $$\triangle{BDO}$$ is also $$2$$.now the $$\angle CAO$$ = $$\angle DBO$$=$$45^{\circ}$$. therefore $$\frac{360}{45}=8$$

So the area of arc $$AEC$$ and arc $$BFD$$=$$\frac{1}{8} \times$$ area of the circle=$$\frac{\pi 2^2}{8}$$=$$\frac{\pi}{2}$$

can you finish the problem........

Therefore the required area by [ area of rectangle $$ABEF$$- (area of arc $$AEC$$+area of $$\triangle ACO$$+area of $$\triangle BDO$$+ area of arc $$BFD$$)]=$$8\sqrt 2-(\frac{\pi}{2}+2+2+\frac{\pi}{2}$$)=$$8\sqrt 2 -4-\pi$$

# Circular Cylinder Problem | AMC-10A, 2001 | Problem 21

Try this beautiful problem from Geometry based on Circular Cylinder.

## Circular Cylinder Problem - AMC-10A, 2001- Problem 21

A right circular cylinder with its diameter equal to its height is inscribed in a right circular cone. The cone has diameter $10$ and altitude $12$, and the axes of the cylinder and cone coincide. Find the radius of the cylinder.

• $$\frac{30}{23}$$
• $$\frac{30}{11}$$
• $$\frac{15}{11}$$
• $$\frac{17}{11}$$
• $$\frac{3}{2}$$

### Key Concepts

Geometry

Cylinder

cone

Answer: $$\frac{30}{11}$$

AMC-10A (2001) Problem 21

Pre College Mathematics

## Try with Hints

Given that the diameter equal to its height is inscribed in a right circular cone.Let the diameter and the height of the right circular cone be $$2r$$.And also The cone has diameter $10$ and altitude $12$, and the axes of the cylinder and cone coincide.we have to find out the radius of the cylinder.Now if we can show that $$\triangle AFE \sim \triangle AGC$$, then we can find out the value of $$r$$

Can you now finish the problem ..........

Given that $$Bc=10$$,$$AG=12$$,$$HL=FG=2r$$. Therefore $$AF=12-2r$$,$$FE=r$$,$$GC=5$$

Now the $$\triangle AFE \sim \triangle AGC$$, Can you find out the radius from from this similarity property.......?

can you finish the problem........

Since $$\triangle AFE \sim \triangle AGC$$, we can write $$\frac{AF}{FE}=\frac{AG}{GC}$$

$$\Rightarrow \frac{12-2r}{r}=\frac{12}{5}$$

$$\Rightarrow r=\frac{30}{11}$$

Therefore the radius of the cylinder is $$\frac{30}{11}$$

# Problem on Circumscribed Circle | AMC-10A, 2003 | Problem 17

Try this beautiful problem from Geometry based on Circumscribed Circle

## Problem on Circumscribed Circle - AMC-10A, 2003- Problem 17

The number of inches in the perimeter of an equilateral triangle equals the number of square inches in the area of its circumscribed circle. What is the radius, in inches, of the circle?

• $$\frac{5\sqrt3}{\pi}$$
• $$\frac{3\sqrt3}{\pi}$$
• $$\frac{3\sqrt3}{2\pi}$$

### Key Concepts

Geometry

Triangle

Circle

Answer: $$\frac{3\sqrt3}{\pi}$$

AMC-10A (2003) Problem 17

Pre College Mathematics

## Try with Hints

Let ABC is a equilateral triangle which is inscribed in a circle. with center $$O$$. and also given that perimeter of an equilateral triangle equals the number of square inches in the area of its circumscribed circle.so for find out the peremeter of Triangle we assume that the side length of the triangle be $$x$$ and the radius of the circle be $$r$$. then the side of an inscribed equilateral triangle is $$r\sqrt{3}$$=$$x$$

Can you now finish the problem ..........

The perimeter of the triangle is=$$3x$$=$$3r\sqrt{3}$$ and Area of the circle=$$\pi r^2$$

Now The perimeter of the triangle=The Area of the circle

Therefore , $$3x$$=$$3r\sqrt{3}$$=$$\pi r^2$$

can you finish the problem........

Now $$3x$$=$$3r\sqrt{3}$$=$$\pi r^2$$ $$\Rightarrow {\pi r}=3\sqrt 3$$ $$\Rightarrow r=\frac{3\sqrt3}{\pi}$$