MATH1061/7861, Thu 22 Oct 2020
B
cont Day
Existence prods
WIT
pet igeW
hole w 24 pigeons Question 1. Prove that, if 51 numbers are chosen from {1,2,…,100} then two of the chosen numbers must sum to 101.
but
i
out of cortol
pigeons F1
Hole
50 4,97 i hole i
50,54 hole
consecutive?
145
41
408
112
90,11
3 pigeons
41 S
in same hole
pain
0
pigeonhole
numbers Choose 51 s
to prom
No
consecutive
Try
41
control
2,92
i
of otdistiiitmbes
Icky
hole 3,98 7 hey
pigeons some pair gets I s
A co
Day 0,433
Efwus
n 7
multiple
mjftmeawpiuge.us
Question 2. What is the maximum number of distinct integers that can be chosen from {1,2,…,60} so that no three are
Not
97,8W
7,8 Is
pigeons
holes 2nd f
s pigeons pigeons
20 holes Ck 2
i i
those two 8
101
From
same hole
n
pigeons hole 3 pigeons
FH
w 2
Holes
112,3 Ju was 9 as
so uses 3 Hs
corsecutee
i
QubdXA E
amore 3
Ey
nak
i
78,9 58,59,60
All s appear
Question 3. Show that, if A is any 6-element subset of {1,2,…,12}, then:
i ◦ A must have two distinct subsets with the same sum; ◦ A must have two disjoint subsets with the same sum.
02
sub 1
ii
Pf
zi
holes Es
two pigeons subsetyffeffA
II
647578
SIU Imai O possible
two subsets have same sum
t sub 2 in same hole
Challenge A. What is the largest number of integers that can be chosen from {1,2,…,100} so that no chosen number divides
any other chosen number?
Question 4. For each of the following lists, draw a simple graph whose vertices have these degrees, or explain why no such graph exists.
A. 2,2,2,2
B. 3,2,1
C. 4,3,2,2,2,2,1,1 D. 1,1,1,1
E. 5,5,5,5,5,5
DEI
noooo
B
distinct endpoints O190,73 i loop od
imposts
belts
i
Sums t I Min
NI B NI
Ia
O i Notsimple
Question 5. A graph G has 5 vertices with degrees 3, 3, 2, 2, 2 respectively. How many edges does G have?
Question 6. A graph has 6 vertices and 10 edges. If five of its vertices have degree 3, what is the degree of the other vertex?
Question 7. What is the maximum possible number of edges for a simple graph with n vertices? What about a non-simple graph?
Challenge B. A group of 3 mathematicians goes to dinner, and they each hang their jacket at the door. On the way out, they each pick up a jacket at random. What is the probability that nobody goes home with their own jacket?
What if there are 10 mathematicians?
What if there are n mathematicians?
What happens to this probability as n grows larger? Does it approach 1? 0? Something in between? Question 8. Suppose you have a class of students in which:
◦ every student has brown eyes, brown hair, and/or a brown jacket; ◦ 15 students have brown eyes;
◦ 20 students have brown hair;
◦ 12 students have brown jackets;
◦ 7 of these students have both brown eyes and brown hair;
◦ 8 of these students have both brown eyes and brown jackets;
◦ 9 of these students have both brown hair and brown jackets;
◦ 6 of these students have brown hair, brown eyes and brown jackets.
How many students are in the class?