Scribd
Upload
166 views1 page

Pigeonhole Principle

The document presents various problems related to the Pigeonhole Principle, illustrating how to guarantee certain outcomes based on the distribution of items or characteristics among a set of entities. It includes scenarios involving students, dice, integers, points in a square, and colored balls, each demonstrating the principle's application in ensuring specific conditions are met. The problems range from calculating minimum selections to proving the existence of subsets with particular properties.

Uploaded by

preeti_jiten
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
166 views1 page

Pigeonhole Principle

The document presents various problems related to the Pigeonhole Principle, illustrating how to guarantee certain outcomes based on the distribution of items or characteristics among a set of entities. It includes scenarios involving students, dice, integers, points in a square, and colored balls, each demonstrating the principle's application in ensuring specific conditions are met. The problems range from calculating minimum selections to proving the existence of subsets with particular properties.

Uploaded by

preeti_jiten
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Pigeonhole Principle

1. How many students do you need in a school to guarantee that there are at least
2 students who have the same first two initials?
2. Show that in a group of 50 students at least 5 are born in a same month.
3. Danny has a bunch of dice in his drawer. He recalls that 5 of them are green, 6 of
them are blue and 7 of them are red . He reaches in and grabs several without
looking. How many does he have to grab, in order to ensure that 3 of them are
the same color?
4. 5 integers are randomly chosen from 1 to 2015. What is the probability that there
is a pair of integers whose difference is a multiple of 4?
5. Five points are drawn randomly inside a unit square, show that there is at least
two points with a distance less than
6. 10 integers are chosen from 1 to 100 inclusively. Prove that we can find 2 disjoint
non-empty subsets of the chosen integers such that the 2 subsets give the same
sum of elements.
7. Prove that for any given 50 positive integers, it is always possible to select out
four numbers al; a2; a3 and a4 from them, such that (a2 - al)(a4 - a3) is a
multiple of 2009.
8. Let AIBICIDIE be a regular pentagon. For 2 s n s 11, let AnBnCnDnEn be the
pentagon whose vertices are the midpoints of the sides of An-1 Bn-1 Cn-1 Dn-1
En-1. All the 5 vertices of each of the 11 pentagons are arbitrarily coloured red or
blue. Prove that four points among these 55 points have the same colour and
form the vertices of a cyclic quadrilateral. ( INMO 2019)
9. How many cards must be selected from a deck of 52 cards to make sure that at
least 3 cards of the same suit are selected?
10. In a bag, there are some balls of the same size that are colored by 7 colors, and
for each color the number of balls is 77. At least how many balls are needed to be
picked out at random to ensure that one can obtain 7 groups of 7 balls each such
that in each group the balls are homochromatic?
11. A bag contain 200 marbles. There are 60 red ones, 60 blue ones, 60 green ones
and the remaining 20 consist of yellow and white ones. If marbles are chosen
from the bag without looking, what is the smallest number one must pick in order
to ensure that, among the chosen marbles, at least 20 are of the same colour?
12. Prove that in a set containing n positive integers there must be a subset such
that the sum of all numbers in it is divisible by n.

You might also like