slides

Document technical information

Format pdf
Size 333.9 kB
First found May 22, 2018

Document content analysis

Category Also themed
Language
Type
not defined
Concepts
no text concepts found

Persons

Organizations

Places

Transcript

Chapter 1. Pigeonhole Principle
Prof. Tesler
Math 184A
Winter 2017
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
1 / 12
Pigeonhole principle
https://commons.wikimedia.org/wiki/File:TooManyPigeons.jpg
If you put 10 pigeons into 9 holes, at least one hole has at least two
pigeons.
Pigeonhole Principle
If you put n items into k boxes, for integers n > k > 0, then at least one
box has 2 or more items.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
2 / 12
Example: Five real numbers in [0, 1]
Pick five real numbers between 0 and 1: x1 , . . . , x5 ∈ [0, 1].
We will show that at least two of them differ by at most 1/4.
Split [0, 1] into 4 bins of width 1/4:
0
1/4 1/2 3/4
1
Put 5 numbers into 4 bins. At least two numbers are in the same
bin, and thus, are within 1/4 of each other.
Technicality: We didn’t say how to handle 41 , 12 , and 34 .
Is 41 in the 1st or 2nd bin? However, it doesn’t affect the conclusion.
Generalization
For an integer n > 2, pick n numbers between 0 and 1.
1
Then at least two of them are within n−1
of each other.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
3 / 12
Example: Picking 6 numbers from 1 to 10
Pick 6 different integers from 1 to 10.
Claim: Two of them must add up to 11.
Example
1, 4, 7, 8, 9, 10 has 1 + 10 = 11 and 4 + 7 = 11.
Proof.
Pair up the numbers from 1 to 10 as follows:
(1, 10)
(2, 9)
(3, 8)
(4, 7)
(5, 6)
There are 5 pairs, each summing to 11.
At least two of the 6 numbers must be in the same pair.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
4 / 12
Example: 5 points on a sphere
Select any five points on a sphere. The sphere may be cut in half (both
halves include the boundary) so that one of the two hemispheres has
at least four of the points.
Pick any two of the five points.
Form the great circle through those points, splitting it into two
hemispheres.
Three of the five points remain.
One of the two hemispheres must contain at least two of these
points, plus the original two points. Thus, it contains at least four
of the points.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
5 / 12
Notation
Let x be a real number.
bxc = floor of x = largest integer that’s 6 x
dxe = ceiling of x = smallest integer that’s > x
b2.5c = 2
b−2.5c = −3
b2c = d2e = 2
d2.5e = 3
d−2.5e = −2
b−2c = d−2e = −2
You have probably seen [x] used for greatest integer , and you may
encounter some differences in definitions for negative numbers.
However, we will use the floor and ceiling notation above, and will
use square brackets for
[n] = {1, 2, 3, . . . , n} (for integers n > 1)
and
[0] = ∅.
This notation is common in Combinatorics.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
6 / 12
Generalized Pigeonhole Principle
Put n items into k boxes. Then
There is a box with at least dn/ke items.
There is a box with at most bn/kc items.
Example
150 pigeons are placed into 60 holes.
At least one hole has d150/60e = d2.5e = 3 or more pigeons.
At least one hole has b150/60c = b2.5c = 2 or fewer pigeons.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
7 / 12
Proof of Generalized Pigeonhole Principle
Put n items into k boxes. Then
1
There is a box with at least dn/ke items.
2
There is a box with at most bn/kc items.
Let ai be the number of items in box i, for i = 1, . . . , k.
Each ai is a nonnegative integer, and a1 + · · · + ak = n.
Assume (by way of contradiction) that all boxes have fewer than
dn/ke items: ai < dn/ke for all i. Thus, ai 6 dn/ke − 1 for all i.
Then the total number of items placed in the boxes is
a + · · · + ak 6 k · (dn/ke − 1) .
| 1 {z
}
=n
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
8 / 12
Proof of Generalized Pigeonhole Principle
1. Show there is a box with at least dn/ke items
Assume that every box has fewer than dn/ke items.
Then the total number of items placed in the boxes is
(∗)
a + · · · + ak 6 k · (dn/ke − 1)
| 1 {z
}
=n
Dividing n by k gives n = kq + r, where the quotient, q, is an integer
and the remainder, r, is in the range 0 6 r 6 k − 1.
If there is no remainder (r = 0), then dn/ke = n/k = q.
Inequality (∗) becomes n 6 k(q − 1) = n − k.
But n − k is smaller than n, a contradiction.
If there is a remainder (1 6 r 6 k − 1), then dn/ke = q + 1.
Inequality (∗) becomes n 6 k((q + 1) − 1) = kq = n − r, so n 6 n − r.
But n − r is smaller than n, a contradiction.
Thus, our assumption that all ai < dn/ke was incorrect, so some
box must have ai > dn/ke.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
9 / 12
Proof of Generalized Pigeonhole Principle
2. Show there is a box with at most bn/kc items
Assume that every box has more than bn/kc items.
Then the total number of items placed in the boxes is
(∗)
a + · · · + ak > k · (bn/kc + 1)
| 1 {z
}
=n
Dividing n by k gives n = kq + r, where the quotient, q, is an integer
and the remainder, r, is in the range 0 6 r 6 k − 1.
bn/kc = q, so inequality (∗) becomes
n > k(q + 1) = kq + k = n − r + k, so n > n + (k − r).
But k − r > 0, so n is smaller than n + (k − r), a contradiction.
Thus, our assumption that all ai > bn/kc was incorrect, so some
box must have ai 6 bn/kc.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
10 / 12
Example: Ten points in the unit square
(0,1)
(1,1)
(0,0)
(1,0)
Pick 10 points (x1 , y1 ), . . . , (x10 , y10 ) in [0, 1] × [0, 1].
Split [0, 1] × [0, 1] into a 3 × 3 grid of 1/3 × 1/3 squares.
10 points placed into 9 squares, and 10 > 9, so some square has
at least two points.
The farthest apart that
points can be within the same square is
√
p
(1/3)2 + (1/3)2 = 3 2 .
Thus, at least two points are at most
√
2
3
apart.
If
√you pick 10 points in [0, 1] × [0, 1], there must be two of them at most
2/3 ≈ 0.4714045 apart.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
11 / 12
Example: Ten points in the unit square
(0,1)
(1,1)
(0,0)
(1,0)
Pick 10 points (x1 , y1 ), . . . , (x10 , y10 ) in [0, 1] × [0, 1].
Split [0, 1] × [0, 1] into a 2 × 2 grid of 1/2 × 1/2 squares.
One of the 4 squares must have at least d10/4e = d2.5e = 3 points.
The farthest apart that two
points can be within the same square
√
p
is (1/2)2 + (1/2)2 = 2 2 .
√
Thus, there is a disk (filled-in circle) of diameter 2/2 with at least
three of the points.
If
√you pick 10 points in [0, 1] × [0, 1], there is a disk of radius
2/4 ≈ 0.3535534 with at least three of the points.
Prof. Tesler
Ch. 1. Pigeonhole Principle
Math 184A / Winter 2017
12 / 12

Similar documents

×

Report this document