University:
Amherst College
Course:
MATH 220 | Mathematical Reasoning and Proof
Academic year:

2020
Views:

253

Pages:

2
Author:

Nathaly Davidson

Worksheet: Pigeonhole principle Math 220-02, Spring 2020 Work on the problems below with one or two students nearby. Call me over if you have questions or want to check answers! Each of these problems can be solved using the pigeonhole principle: Let m, n ∈ N. Suppose that a set of objects (“pigeons”) are distributed among n categories (“pigeonholes”). If the number of objects is at least n(m − 1) + 1, then there is some category with at least m objects in it. 1. Assume that all people have at most 200, 000 hairs on their head. Prove that in New York City, there are two people with exactly the same number of hairs on their head. The pigeons are: The pigeonholes are: 2. How many digits of π must you examine before you are guaranteed to see some specific digit at least 1000 times? The pigeons are: 24 February 2020. The pigeonholes are: page 1 of 2 Worksheet: Pigeonhole principle Math 220-02, Spring 2020 3. Suppose that there are seven bicycles on the section of the Norwottuck Rail Trail running from Amherst College to the Connecticut River. Assume that this section of the trail is exactly six miles long. Prove that there are two bicycles that are at most one mile apart. The pigeons are: The pigeonholes are: 4. Suppose that S = {s1 , s2 , · · · , s10 } is a set of 10 natural numbers. Prove that some nonempty subset of S has sum divisible by 10. By convention, the “sum” of a set with just one number is the number itself. This is a more challenging application of pigeonhole, so I’ve told you below what the pigeonholes and pigeonholes could be below; see if you can find a proof along these lines. The pigeons are: The numbers 0, s1 , s1 + s2 , s1 + s2 + s3 , · · · , s1 + s2 + · · · + s10 . The pigeonholes are: The digits 0, 1, 2, · · · , 9. 24 February 2020. page 2 of 2

Worksheet Pigeonhole principle Math 220-02, Spring 2020

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock