\input ws-form.tex

{\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

\def\pre#1{\par\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}}
\question{%
Q1 (7.1) -- A school has 147 third graders. The third grade teachers have planned a special treat for the last day of school and brought ice cream for their students. There are three flavors: mint chip, chocolate, and strawberry. Suppose that 60 students like (at least) mint chip, 103 like chocolate, 50 like strawberry, 30 like mint chip and strawberry, 40 like mint chip and chocolate, 25 like chocolate and strawberry, and 18 like all three flavors. How many students don't like any of the flavors available?
}{
Students who don't like available flavors = $147 - 60 - 103 - 50 + 30 + 40 + 25 - 18 = 11$.
}
\question{%
Q2 (7.4) -- How many positive integers less than or equal to 100 are divisible by none of 2, 3, and 5?
}{
$100 - ({100 \over 2} + {99 \over 3} + {100 \over 5}) + ({96 \over 2\cdot3} + {100 \over 2\cdot5} + {90 \over 3\cdot5}) - {90 \over 2\cdot3\cdot5} = 26$
}
\question{%
Q3 (7.11) -- As in Example 7.4, let $X$ be the set of functions from $[n]$ to $[m]$ and let a function $f \in X$ satisfy property $P_i$ if there is no $j$ such that $f(j) = i$.

\pre{a.} Let the function $f:[8]\to[7]$ be defined by the following table. Does $f$ satisfy property $P_2$? Why or why not? What about property $P_3$? List all the properties $P_i$ (with $i \leq 7$) satisfied by $f$.

\medskip
\centerline{\vbox{\halign{& #\hfil \cr
  $i$    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr \noalign{\smallskip\hrule\smallskip}
  $f(i)$ & 4 & 2 & 6 & 1 & 6 & 2 & 4 & 2 \cr
}}}

\pre{b.} Is it possible to define a function $g: [8] \to [7]$ that satisfies no property $P_i$, $i\leq7$? If so, give an example. If not, explain why not.

\pre{c.} Is it possible to define a function $h: [8] \to [9]$ that satisfies no property $P_i$, $i\leq9$? If so, give an example. If not, explain why not.
}{
\pre{a.} No because $f(2)=f(6)=f(8)=2$. However, it does satisfy $P_3$ because for no $i\in [8]$ is $f(i)=3$. Overall, it satisfies properties $\{3,5,7\}$ but not $8$ because $8 \not\in [7]$.
\pre{b.} Yes. $\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(1,1)\}$ satisfies none of the properties.
\pre{c.} No. Any function of the nature of $h$ cannot satisfy no properties (i.e. there must be at least one i for which $f(j)\neq i$ for all $j\in[8]$). This is by the pigeonhole theorem: to assign [9] to [8], one must put two outputs into one input, contradicting the definition as a function.
}
\question{%
List all the derangements of $[4]$. (For brevity, you may write a permutation $\sigma$ as a string $\sigma(1)\sigma(2)\sigma(3)\sigma(4)$.)
}{
2143,
2341,
2413,
3142,
3412,
3421,
4123,
4312,
4321
}
\bye