\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section6.2Functions with Rules Described in Words
Nearly all of the functions we have seen so far have had sets of numbers for their domain and codomain and have had rules defined by formulas. In this section, which include functions whose domain and codomain are sets of other discrete objects such as graphs and bit strings.
As a first example of functions with rules described in words, we consider the floor and ceiling functions which take a real (decimal) number input and find a nearby integer to output.
For a real number \(x\text{,}\) the floor of \(x\text{,}\) denoted \(\lfloor x \rfloor\text{,}\) is the result of rounding \(x\) down to the nearest integer less than or equal to \(x\text{.}\) Officially, \(\lfloor x \rfloor=k\) where \(k\) is the greatest integer such that \(k\le x\text{.}\) For example, \(\lfloor 2.4 \rfloor = 2\) and \(\lfloor -2.4 \rfloor = -3\text{.}\) This name comes from the fact that we look down to see the floor of a room. Notice that the floor is the first integer at or to the left of the number on the real number line.
Figure6.2.2.Calculating the floor by looking left on the real number line.
For a real number \(x\text{,}\) the ceiling of \(x\text{,}\) denoted \(\lceil x \rceil\text{,}\) is the result of rounding \(x\) up to the nearest integer greater than or equal to \(x\text{.}\) Officially, \(\lceil x \rceil =k\) where \(k\) is the least integer such that \(k\ge x\text{.}\) For example, \(\lceil 2.4 \rceil = 3\) and \(\lceil -2.4 \rceil = -2\text{.}\) This name comes from the fact that we look up to see the ceiling of a room. Notice that the ceiling is the first integer at or to the right of the number on the real number line.
Figure6.2.3.Calculating the ceiling by looking right on the real number line.
Professor Dorée expects 40 students to attend a talk. She wants to cans of sparkling water so each student can get one, then how many 12-packs of cans should she buy? What if there are \(n\) students? Your answer should involve \(n\) and floor or ceiling.
Give an example of a real number \(x\) that is not an integer where \(\lceil 2x \rceil = 2 \lceil x \rceil\text{.}\) Give a counterexample to the conjecture that \(\lceil 2x \rceil = 2 \lceil x \rceil\) for all real numbers \(x\text{.}\)
Does there exist a real number \(x\) where \(\lfloor x \rfloor = 6\text{?}\) Is it unique? How many real numbers \(x\) have \(\lfloor x \rfloor = 6\text{?}\) Describe all real numbers \(x\) such that \(\lfloor x \rfloor = 6\text{.}\)
If \(x\) is a real number such that \(\lfloor x \rfloor \neq \lceil x \rceil\text{,}\) then how are \(\lfloor x \rfloor\) and \(\lceil x \rceil\) related? State your answer in the form of a conjecture. Be as specific as possible.
Give an example of a real number \(x\) such that \(\fn{floor}(x) = 11\text{.}\) Now find a different real number \(s\) such that \(\fn{floor}(s)=11\text{.}\)Solution.
Note that \(\fn{floor}(11) = \lfloor 11 \rfloor = 11\) and so one example is \(x=11\text{.}\) Another example is \(x = 11.38\) because \(\fn{floor}(11.38) = \lfloor 11.38 \rfloor = 11\text{.}\)
Describe all real numbers \(x\) such that \(\fn{floor}(x)=11\text{.}\)Solution.
Any real number \(x\) that is 11 or larger, but not as larger as 12 will have \(\fn{floor}(x)=11\text{.}\) We can describe these real numbers using the inequality \(11 \le x \lt 12\) or the interval \([11,12)\text{.}\)
Find an integer \(n\) such that \(\fn{countdiv}(n) = 4\text{.}\) Is it unique? Explain.
Solution.
The integer six has four divisors: 1, 2, 3, and 6. Therefore \(\fn{coundiv}(6)=4\text{.}\) It is not unique because, for example, the integer ten also has four divisors: 1, 2, 5, and 10 and so \(\fn{countdiv}(10)=4\) as well.
Describe all integers with \(\fn{countdiv}(n) = 4\text{.}\)Solution.
By our work in Subsection 4.4.B, there are two possible prime factorizations of a number having four positive divisors: \(p^3\) or \(pq\) where \(p\) and \(q\) are distinct primes. (If we made a divisor table, it would be \(1 \times 4\) or \(2 \times 2\text{.}\))
Give a counterexample to the statement: for every positive integer \(a\) and \(b\text{,}\) if \(a\lt b\text{,}\) then \(\fn{countdiv}(a) \lt \fn{countdiv}(b)\text{.}\) It follows that the function \(\fn{countdiv}\) is not increasing.
Solution.
We want an example that shows the statement is false, meaning it is a broken promise. A counterexample is \(a=6\) and \(b=7\) because \(6 \lt 7\) but \(\fn{countdiv}(6)=4\) and \(\fn{countdiv}(7) = 2\text{,}\) so \(\fn{countdiv}(6) \ge \fn{countdiv}(7)\text{.}\)
defined by \(\fn{twopart}(n)\) is the highest power of two that divides \(n\text{.}\) Note that \(1 = 2^0\) is a power of two. Evaluate \(\fn{twopart}(24)\text{,}\)\(\fn{twopart}(30)\text{,}\) and \(\fn{twopart}(31)\text{.}\)
defined by \(\pi(n)=\) the number of primes less than or equal to \(n\text{.}\) Note that the function \(\pi\) has nothing to do with the real number \(\pi\text{.}\) Evaluate \(\pi(6)\) and \(\pi(20)\text{.}\)
Evaluate \(\fn{deg3}(K_{3,7})\) where \(K_{3,7}\) is the complete bipartite graph defined in Definition 3.2.12.
Solution.
The complete bipartite graph \(K_{3,7}\) has three (black) vertices of degree seven and seven (white) vertices of degree three, so \(\fn{deg3}(K_{3,7})=7\text{.}\)
Evaluate \(\fn{deg3}(L_{2 \times 5})\) where \(L_{2 \times 5}\) is the ladder defined in Example 3.2.25.
Solution.
The ladder \(L_{2 \times 5}\) has four corner vertices of degree two and the other \(10-4=6\) inner vertices have degree three, so \(\fn{deg3}(L_{2 \times 5})=6\text{.}\)
It turns out we can draw a graph \(G\) with ten vertices such that \(\fn{deg3}(G) = n\) for \(n=0,1,2,3,4,5,6,7,8,9\text{,}\) and 10 and so the image of \(\fn{deg3}\) is \(\{0,1,2,3,4,5,6,7,8,9,10\}\text{.}\) Draw a graph \(G\) with ten vertices such that \(\fn{deg3}(G) = 2\text{.}\) (Challenge yourself to draw the others.)
Solution.
is defined by \(\fn{comp}(G)=\overline{G}\text{,}\) the graph theoretic complement of the graph \(G\text{.}\) Evaluate (draw) \(\fn{comp}(W_4)\) for the wheel graph \(W_4\text{.}\)
is defined by \(c(G)=\) the the number of edges in of the longest path in \(G\text{.}\) Evaluate \(c(C_5)\) for the cycle \(C_5\) and \(c(K_{1,4})\) for the complete bipartite graph (star) \(K_{1,4}\text{.}\)
Next, let’s look at functions defined on bit strings. We defined bit strings, the length of a bit string, and the weight of a bit string in Definition 2.4.1. We start by establishing the notation for the empty string and for sets of bit strings.
For any non-negative integer \(n\text{,}\) the set of all bit strings of length \(n\) is \(\mathbb{B}_n\text{.}\) For example, \(\mathbb{B}_0 = \{\lambda\}\text{,}\)\(\mathbb{B}_1 = \{\bs{0}, \bs{1}\}\text{,}\)\(\mathbb{B}_2 = \{\bs{00}, \bs{01}, \bs{10}, \bs{11}\}\) and
Evaluate \(\fn{wgt}(\bs{001})\text{,}\)\(\fn{wgt}(\bs{1111})\text{,}\) and \(\fn{wgt}(\lambda)\text{.}\)Solution.
The weight of a bit string is the number of \(\bs{1}\) s in the bit string. Since \(\bs{001}\) has one \(\bs{1}\text{,}\)\(\fn{wgt}(\bs{001})=1\text{.}\) Since \(\bs{1111}\) has four \(\bs{1}\) s, \(\fn{wgt}(\bs{1111})=4\text{.}\) Since \(\lambda\) has no \(\bs{1}\) s, \(\fn{wgt}(\lambda)=0\text{.}\)
Describe all bit strings \(b\) such that \(\fn{wgt}(b)=0\text{.}\)Solution.
For a bit string to have weight 0, it cannot contain any \(\bs{1}\) s. That is, it must be empty or entirely \(\bs{0}\) s. We can list such strings as \(\lambda, \bs{0}, \bs{00}, \bs{000}, \bs{0000}, \ldots\text{.}\)
What is the image of the function \(\fn{wgt}\text{?}\)Solution.
It is not possible to have a negative weight. We saw in (d) and (c) that any non-negative integer is the weight of some bit strings. Therefore, the image of \(\str{wgt}\) is \(\mathbb{N}\text{.}\)
defined by \(\fn{lastbit}(b) =\) the last bit in the bit string \(b\text{.}\) Evaluate \(\fn{lastbit}(\bs{0})\) and \(\fn{lastbit}(\bs{1011})\text{.}\)
defined by \(\fn{append}(b)=b\bs{1}\text{,}\) literally the string \(b\) with a \(\bs{1}\) added to the right. Evaluate \(\fn{append}(\bs{0})\) and \(\fn{append}(\bs{1011})\text{.}\)
defined by \(\fn{reverse}(b)=\overleftarrow{b}\text{,}\) where \(\overleftarrow{b}\) means the bit string \(b\) written in reverse order. Evaluate \(\fn{reverse}(\bs{0})\) and \(\fn{reverse}(\bs{1011})\text{.}\)
\begin{equation*}
f(b)= \left\{ \begin{array}{ll} b \amp \text{ if the last bit of the bit string } b \text{ is } \bs{0} \\ b \text{ without its last bit } \amp \text{ if the last bit of the bit string } b \text{ is } \bs{1} \end{array} \right.\text{.}
\end{equation*}
Evaluate \(f(\bs{0})\) and \(f(\bs{1011})\text{.}\)
Define a simple-to-describe function \(g:\mathbb{B}^*\to \mathbb{B}^*\) such that \(g(\bs{1011}) = \bs{0100}\text{,}\)\(g(\bs{110})= \bs{001}\text{,}\) and \(g(\bs{000011}) = \bs{111100}\text{.}\)
Define a simple-to-describe function \(h:\mathbb{B}^*\to \mathbb{B}^*\) such that \(g(\bs{1011}) = \bs{10111}\text{,}\)\(g(\bs{110})= \bs{1100}\text{,}\) and \(g(\bs{000011}) = \bs{0000110}\text{.}\) Hint: even.
Give an example of a real number \(x\) such that \(\fn{ceil}(x) = 11\text{.}\) Now find a different real number \(s\) such that \(\fn{ceil}(x)=11\text{.}\)
Give an example of real numbers \(x\) and \(y\) that are not integers such that \(\lfloor x +y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor\text{.}\)
Give a counterexample to the conjecture that \(\lfloor x +y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor\) for all real numbers \(x\) and \(y\text{.}\)
Write a formula for \(a \fn{ div } n\) in terms of \(a\) and \(n\text{.}\) Use \(\frac{a}{n}\text{,}\) not \(a \div n\text{,}\) in your formula. Hint: Your answer should involve floor or ceiling.
SubsubsectionExercises for 6.2.B Number-theoretic Functions
11.Practice.
The function \(g(n)=\) the largest integer less than or equal to \(\sqrt{n}\text{.}\) Evaluate \(g(17)\text{,}\)\(g(30)\text{,}\) and \(g(9)\text{.}\) Show work.
is defined by \(\fn{fivepart}(n)\) is the highest power of five that divides \(n\text{.}\) Note that \(1 = 5^0\) is a power of five. Evaluate \(\fn{fivepart}(30)\text{,}\)\(\fn{fivepart}(24)\text{,}\) and \(\fn{fivepart}(75)\text{.}\) Show work
defined by \(f(n)=\) the number of distinct positive primes that divide \(n\text{.}\) Evaluate \(f(12)\text{,}\)\(f(16)\text{,}\)\(f(30)\text{,}\) and \(f(1)\text{.}\) Show work.
\begin{equation*}
t(n)= \left\{ \begin{array}{cl} 2 \amp \text{ if } 2 \mid n \land 5 \mid n \\ 1 \amp \text{ if } 2 \mid n \oplus 5 \mid n \\ 0 \amp \text{ if } 2 \nmid n \land 5 \nmid n \end{array} \right.\text{.}
\end{equation*}
Recall \(\land\) means “and” whereas \(\oplus\) means “xor”, the exclusive or.
Evaluate \(t(20)\) and \(t(6)\text{.}\) Show work.
\begin{equation*}
\fn{gplt}(n)=\left\{\begin{array}{cl} 0 \amp \text{ if } n=1 \\ \text{ the largest prime less than or equal to } n \amp \text{ if } n \ge 2 \end{array} \right.\text{.}
\end{equation*}
The \(\str{gplt}\) stands for “greatest prime less than”.
Evaluate \(g(6)\text{,}\)\(g(67)\text{,}\)\(g(678)\text{,}\) and \(g(6789)\text{.}\) Use technology (calculator or Internet search) to evaluate the necessary logs.
is defined by \(\fn{cleaf}(G)\) is the number of leaves (degree 1 vertices) in the graph \(G\text{.}\)
Evaluate \(\fn{cleaf}(P_{10})\text{,}\)\(\fn{cleaf}(K_{1,9})\text{,}\) and \(\fn{cleaf}(C_{10})\) for the path \(P_{10}\text{,}\) the complete bipartite graph (star) \(K_{1,9}\text{,}\) and the cycle \(C_{10}\text{.}\)
Let \(\mathbb{G}\) denote the set of all graphs. The function \(k: \mathbb{Z}^+ \to \mathbb{G}\) by \(k(n) = K_{n,n+1}\text{,}\) the complete bipartite graph.
is defined by \(g(G) =\) the number of vertices in the smallest cycle subgraph in \(G\text{,}\) if \(G\) contains any cycles, and 0 if \(G\) is acyclic.
Evaluate \(g(K_5)\) and \(g(P_5)\) for the complete graph \(K_5\) and the path \(P_5\text{.}\)
Let \(\mathbb{T}\) denote the set of all trees as defined in Definition 3.4.33 and let \(\mathbb{T}_3\) denote the set of all trees with at least three vertices. The function
is defined by \(\fn{prune}(T)=\) the graph we get when we remove all leaves and their corresponding edges from \(T\text{.}\)
Evaluate \(\fn{prune}(P_5)\) and \(\fn{prune}(K_{1,6})\) where \(P_5\) is the path and \(K_{1,6}\) is the complete bipartite graph (star). You may draw the answer or state its standard name.
Describe the fixed points of the function \(\fn{reverse}\text{.}\) That means, describe all bit strings \(b\) such that \(\fn{reverse}(b) =b\text{.}\) Hint: There is a name for such strings.
Given a natural number \(n\text{,}\) describe a general bit string \(b\) such that \(\fn{runzero}(b) = n\text{.}\) Your answer should involve \(n\text{.}\)
\begin{equation*}
h(b) = \left\{ \begin{array}{cl} b \amp \text{ if the last bit of the bit string } b \text{ is \bs{0}} \\ b \text{ without its last bit } \amp \text{ if the last bit of the bit string } b \text{ is \bs{1}} \end{array} \right.
\end{equation*}
Evaluate \(h(\bs{1011})\) and \(h(\bs{1010})\text{.}\)
For this problem, let \(\mathbb{A}\) be the set of all strings of uppercase letters \(\str{A}-\str{Z}\text{,}\) including the empty string \(\lambda\text{,}\) and let \(\mathbb{A}^*\) be the set of all nonempty strings of uppercase letters \(\str{A}-\str{Z}\text{.}\)
Define \(\fn{trim}:\mathbb{A}^* \to \mathbb{A}\) by \(\fn{trim}(s) =\) the string \(s\) without its first character. Identify the domain and codomain of \(\fn{trim}\) and evaluate \(\fn{trim}(\str{HAIR})\) and \(\fn{trim}(\str{X})\text{.}\)
Define \(\fn{countE}:\mathbb{A}^* \to \mathbb{Z}\) by \(\fn{countE}(s) =\) the number of occurrences of \(\str{E}\) in the string \(s\text{.}\) Identify the domain and codomain of \(\fn{countE}\) and evaluate \(\fn{countE}(\str{STEEP})\text{,}\)\(\fn{countE}(\str{STEP})\text{,}\) and \(\fn{countE}(\str{STOP})\text{.}\)
Define \(\fn{isE}:\mathbb{A}^* \to \{\text{ yes } , \text{ no } \}\) by
\begin{equation*}
\fn{isE}(s) = \left\{ \begin{array}{cl} \text{ yes } \amp \text{ if \str{E} is in } s \\ \text{ no } \amp \text{ if \str{E} is not in } s \end{array} \right.\text{.}
\end{equation*}
Identify the domain and codomain of \(\fn{isE}\) and evaluate \(\fn{isE}(\str{STEEP})\) and \(\fn{isE}(\str{DOG})\text{.}\)
Define a simple-to-describe function \(f:\mathbb{B}^*\to \mathbb{B}^*\) such that \(f(\bs{1011}) = \bs{10111}\text{,}\)\(f(\bs{110})= \bs{1100}\text{,}\) and \(f(\bs{000011}) = \bs{0000111}\text{.}\)
Define a simple-to-describe function \(g:\mathbb{B}\to \mathbb{B}\) such that \(g(\bs{1011}) = 111\text{,}\)\(g(\bs{110})= 11\text{,}\) and \(g(\bs{0000}) = \lambda\text{.}\)
Define a simple-to-describe function \(h:\mathbb{B}^*\to \mathbb{Z}\) such that \(h(\bs{1011}) = 2\text{,}\)\(h(\bs{110})= 1\text{,}\) and \(h(\bs{000011}) = -2\text{.}\) Hint: count \(\bs{0}\)s and \(\bs{1}\)s.
