1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
\input ws-form.tex
\input tikz.tex%have to draw graphs
{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}}
Fall 2019\par\noindent
Worksheet 2\par\noindent
Due 09/10/2019}
\smallskip \hrule \medskip
\question{
Q1 - Consider the set $X={1,2,3,4,5}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the 2-element subsets of X. Can you put these 10 pigeons into the two holes in a way that there is no 3-element subset $S={a,b,c} \subset X$ for which all pigeons from $S$ go in the same hole? Then answer the same question if $X={1,2,3,4,5,6}$ with $15=C(6,2)$ pigeons.
}{
Each 3-element subset has 3 2-element subsets, so $m=3$. Treating the number of holes as $n$, we have greater than $mn+1=3\cdot 2+1=7$ pigeons, so there is no way to satisfy the condition. By the same calculus, a 6-element set cannot be organized in such a way to fulfil this condition.
}\vfil
\question{
Q2 - Let $n = 10,000$. Suppose a friend tells you that he has a secret family of subsets of ${1,2,\dots,n}$, and if you guess it correctly, he will give you one million dollars. You think you know the family of subsets he has in mind and it contains exactly half the subsets, i.e., the family has $2^{n-1}$ subsets. Discuss how you can share your hunch with your friend in an effort to win the prize.
}{
Treating the family of all subsets as a set $S$, $S$ has $2^n$ members because any item can either be in or not in the subset.
If my family of subsets were also treated as a set $P$, $P$ could be defined as $2^{10,000} \choose 2^{9,999}$ different families.
Communicating such information would be impossible unless another symbolic definition could be derived.
For example, $N = x \in S : 0 \notin x$ is easily communicable, as any set I have a hunch about would likely be, but most sets satisfying these solutions cannot---in general---be easily communicated.
}\vfil\eject
\question{
Considering graph G in Figure 5.47,
a) Let $V_1 = {g,j,c,h,e,f}$ and $E_1={ge,jg,ch,ef}$. Is $(V_1,E_1)$ a subgraph of $\bf G$?
c) Let $V_3 = {a,d,c,h,b}$ and $E_3={ch,ac,ad,bc}$. Is $(V_3,E_3)$ an induced subgraph of $\bf G$?
e) Draw the subgraph of $\bf G$ induced by {c,h,f,i,j}
f) Draw a subgraph of $\bf G$ having vertex set ${e,f,b,c,h,j}$ that is {\it not} an induced subgraph.
g) Draw a spanning subgraph of $\bf G$ with exactly 10 edges.
}{
a) Yes because $V_1 \subset V_G$ and $E_1 \subset E_G$.
c) No because $dh \in V_G$ but $dh \notin V_3$ and $d, h \in E_3, E_G$
e) \tikzpicture
\draw (2,0) -- (1,0) -- (0,0) -- (0, 1); %ifhc
\node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {i};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {f};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {h};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (3,1) {j};
\endtikzpicture
f) \tikzpicture
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {c};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {h};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {f};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1,1) {e};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {b};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {j};
\endtikzpicture
g) \tikzpicture
%abcdghij
\draw (0,0) -- (0,1) -- (0,2) -- (1,2) -- (3,2) -- (0,1);%bchdac
\draw (1.75,3) -- (3,2) -- (1,5) -- (0,2);%gaih
\draw (1.75,3) -- (0.75,3) -- (1,2);%gjd
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {b};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {h};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1,2) {d};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (3,2) {a};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1.75,3) {g};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (1,5) {i};
\node[draw,circle,inner sep=0.1cm,fill=white] () at (0.75,3) {j};
\endtikzpicture
}
\bye
|
