Scribd
Upload
3 views1 page

Problem Set 4

The document presents a problem set focused on the Pigeonhole Principle, outlining various mathematical problems and their answers. Key problems include determining the minimum number of students required to ensure certain grade distributions, the existence of subsets with specific properties, and relationships among integers and distances. Each problem is designed to illustrate the application of the Pigeonhole Principle in different contexts.

Uploaded by

preachingchaos7
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
3 views1 page

Problem Set 4

The document presents a problem set focused on the Pigeonhole Principle, outlining various mathematical problems and their answers. Key problems include determining the minimum number of students required to ensure certain grade distributions, the existence of subsets with specific properties, and relationships among integers and distances. Each problem is designed to illustrate the application of the Pigeonhole Principle in different contexts.

Uploaded by

preachingchaos7
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

Problem Set 4

Pigeonhole Principle

1. What is the minimum number of students required in a discrete mathematics class


to ensure that at least 8 students will receive the same grade, given that there are
5 possible grades A, B, C, D, E. Answer: 36

2. Find the minimum number of students to ensure that 4 of them were born on the
same day of the week. Answer: 22

3. Given the set t1, . . . , 9u how many elements must be chosen to guarantee that there
is at least one pair having difference 5? Answer: 6

4. Let a1 , a2 , . . . , a13 be not necessarily distinct integers. Show that there exists a
subset of these numbers with sum divisible by 13.

5. Let n P N. Show that every pn`1q-element subset of t1, 2, . . . , 2n´1u must contain
a pair of elements having sum 2n.

6. Let n P N. Show that among n ` 1 integers from t1, 2, . . . , 2nu there are two which
are coprime.

7. There are 12 persons present in a room. Prove that among them there are two
persons who have the same number of acquaintances in the room.

8. Among any 10 natural numbers there are always two whose sum or difference is a
multiple of 17.

9. Let E Ă t1, 2, . . . , 100u and |E| “ 10. Show that E has two nonempty disjoint
subsets having equal sum of its elements.

10. There are 5 points inside a square of side length 1 unit. Prove that there are two
of the five points having distance at most ?12 .

You might also like