diff options
Diffstat (limited to 'tech-math')
| -rw-r--r-- | tech-math/hw3.tex | 70 | ||||
| -rw-r--r-- | tech-math/hw4.tex | 36 | ||||
| -rw-r--r-- | tech-math/hw5.tex | 61 | ||||
| -rw-r--r-- | tech-math/hw6.tex | 33 | ||||
| -rw-r--r-- | tech-math/ws3.tex | 64 | ||||
| -rw-r--r-- | tech-math/ws4.tex | 52 | ||||
| -rw-r--r-- | tech-math/ws5.tex | 28 |
7 files changed, 344 insertions, 0 deletions
diff --git a/tech-math/hw3.tex b/tech-math/hw3.tex new file mode 100644 index 0000000..8880ff8 --- /dev/null +++ b/tech-math/hw3.tex @@ -0,0 +1,70 @@ +\input ws-form.tex +\def\pre#1{\par\leavevmode\llap{\hbox to .5in{\hfil #1 \hfil}}} +\def\prebullet{\pre{$\bullet$}} +\def\em{\it\bf} +\parindent=.5in +\question{% +Q1 (5.34) -- Below are three sequences of length 10. One of the sequences cannot be the degree sequence of any graph. Identify it and say why. For each of the other two, say why (if you have enough information) a connected graph with that degree sequence: +\prebullet is definitely hamiltonian/cannot be hamiltonian; +\prebullet is definitely eulerian/cannot be eulerian; +\prebullet is definitely a tree/cannot be a tree; and +\prebullet is definitely planar/cannot be planar. + +(If you do not have enough information to make a determination for a sequence without having specific graph(s) with that degree sequence, write “not enough information” for that property.) +\pre{a.} $(6,6,4,4,4,4,2,2,2,2)$ +\pre{b.} $(7,7,7,7,6,6,6,2,1,1)$ +\pre{c.} $(8,6,4,4,4,3,2,2,1,1)$ +}{ +Sequence $c$ cannot be a degree sequence because $\sum deg = 2q = 35$ where $q$ is the number of edges, which means there is a fractional number of edges, which is impossible. + +\pre{a.} There is not enough info for hamiltonian. Definitely eulerian, because the degree of all vertices is even. Cannot be a tree because there must be exactly $n-1$ edges, and the sum of degrees is greater than $2n-2$. Not enough info for planar because the number of edges, $18 \leq 3n - 6 = 24$, the restriction on planar graphs derived from Euler's formula. + +\pre{b.} Definitely not hamiltonian because there are two vertices of degree 1, which means there's no way to ``escape'' them to form a cycle. Definitely not eulerian because many vertices are not of even degree. Similar to $a$, $b$ cannot be a degree sequence of a tree because $25 \neq 10-1 = 9$. Definitely not planar by the same inequality used for $a$: $25 \not\leq 24$.} +\question{% +Q2 (5.39) -- Determine pr\"ufer$({\bf T})$ for the tree ${\bf T}$ in Figure 5.58 (not pictured). +}{ +$(9,3,9,5,9,4,5,14,1,6,5,1)$ +} +\question{% +Q3 (6.1) -- We say that a relation $R$ on a set $X$ is {\em symmetric} if $(x,y) \in R$ implies $(y,x) \in R$ for all $x, y \in X$. If $X = {a, b, c, d, e, f}$, how many symmetric relations are there on $X$? How many of these are reflexive? +}{ +Constructing symmetric relations as a choice of 2 elements from 7 (adding an artificial element to account for reflexive pairs), there are ${2 \choose 7} = 21$ symmetric relations on $X$. + +Further restricting the set to exclusively reflexive relations, reflexive pairs needn't be considered, so no artifical element need be added. Therefore, there are ${2 \choose 6} = 15$ symmetric, reflexive relations on $X$. +} +\question{% +\def\mod{\thinspace({\rm mod\thinspace} m)} +Q4 (6.2) -- A relation $R$ on a set $X$ is an {\em equivalence relation} if $R$ is reflexive, symmetric, and transitive. Fix an integer $m \geq 2$. Show that the relation defined on the set $\bf Z$ of integers by $aRb(a, b \in {\bf Z})$ if and only if $a \equiv b \thinspace({\rm mod\thinspace} m)$ is an equivalence relation. (Recall that $a \equiv b \thinspace({\rm mod \thinspace} m)$ means that when dividing $a$ by $m$ and $b$ by $m$ you get the same remainder.) +}{ +Assume that $a \equiv b \thinspace({\rm mod \thinspace} m)$ is not an equivalence relation---that is, it is either not reflexive, not symmetric, or not transitive. It is clearly transitive because if $a \equiv b \equiv c \mod$, then the remainders of $a$ and $b$ are the same and the remainders of $b$ and $c$ are the same, so $a$ and $c$ are the same. It is also clearly symmetric, because equality of remainders transfers to equivalency from mod. Third, it is reflexive because the remainder of $b \div m$ is equal to $b \div m$. By contradiction, this means that no relation $aRb$ on $\bf Z$ could exist if $a \equiv b \mod$ is not an equivalence relation. +} +\question{% +Q5 (6.7) -- Alice and Bob are considering posets $\bf P$ and $\bf Q$. They soon realize that $\bf Q$ is isomorphic to ${\bf P}^d$. After 10 minutes of work, they figure out that $\bf P$ has height 5 and width 3. Bob doesn't want to find the height and width of $\bf Q$, since he figures it will take (at least) another 10 minutes to answer these questions for $\bf Q$. Alice says Bob is crazy and that she already knows the height and width of $\bf Q$. Who's right and why? +}{ +If $\bf P^d$ is isomorphic to $\bf Q$, then there is a bijection $f: X \to Y$ between the base sets of $\bf P^d$ and $\bf Q$ such that all the same comparisons exist on relations $P^d$ and $Q$ for respective $v$ and $f(v)$. This means that any comparison or set of comparisons valid or invalid on $\bf P^d$ would be valid or invalid, respectively, on $\bf Q$. Therefore, a given chain or anti-chain will be retained and thus the heights and widths are the same of $\bf P^d$ and $\bf Q$. Note also that the heights and widths of $\bf P^d$ and $\bf P$ are the same because they have the same comparable objects, just opposite comparisons. (Alice is right) +} +\question{% +Q6 (6.8) -- For this exercise, considef the poset $\bf P$ in Figure 6.5 (not pictured). +\pre{a.} List the maximal elements of $\bf P$. +\pre{b.} List the minimal elements of $\bf P$. +\pre{c.} Find a maximal chain with two points in $\bf P$. +\pre{d.} Find a chain in $\bf P$ with three points that is {\it not} maximal. Say why your chain is not maximal. +\pre{e.} Find a maximal antichain with four points in $\bf P$. +}{ +\pre{a.} $(15, 8, 11, 2, 17, 3)$ +\pre{b.} $(16, 1, 5, 14)$ +\pre{c.} $(16, 8)$ +\pre{d.} $(15, 7, 13)$ is not maximal because, with transitivity, adding $1$ would form a larger chain. +\pre{e.} $(16, 1, 5, 14)$ +} +\question{% +Q7 (6.9) -- Find the height $h$ of the poset ${\bf P} = (X, P)$ shown below as well as a maximum chain and a partition of $X$ into $h$ antichains using the algorithm from this chapter. +}{ +Partition: $(23,12,22,18) \cup () \cup () +} +\question{% +Q8 (6.11) -- A restaurant chef has designed a new set of dishes for his menu. His set of dishes contains 10 main courses, and he will select a subset of them to place on the menu each night. To ensure variety of main courses for his patrons, he wants to guarantee that a night's menu is neither completely contained in nor completely contains another night's menu. What is the largest number of menus he can plan using his 10 main courses subject to this requirement? +}{ +This is equivalent to asking the size of the maximum anti-chain of the subset lattice ${\bf 2}^{10}$, which is ${10 \choose 5}=252$, by Sperner's Theorem. +} +\bye diff --git a/tech-math/hw4.tex b/tech-math/hw4.tex new file mode 100644 index 0000000..4c0413a --- /dev/null +++ b/tech-math/hw4.tex @@ -0,0 +1,36 @@ +\noindent {\bf Q4)} + +C1: f, d, j, k + +C2: b, h, c, l, e, m, o + +C3: g, n, a, i + +Width = w = 3. + +Antichain: $\{f,b,g\}$ + +\noindent {\bf Q5)} + +1. If vertex A has vertex B in its down set, then vertex B has vertex A in its up set. Therefore, any vertex in the "difference" between two adjacent up sets in the "subset chain" outlined in the text must have a unique down set to any of the other "differences" and the same as every other vertex within the same "difference." If it didn't have the same down set as the other vertices, then a vertex which is in one down set but not the other could not have one of the original vertices in its up set (meaning they wouldn't be in the same difference, which is a contradiction). Similarly, if it had the same up set as a vertex within a different "difference," the vertex appearing "later" in the sequence should have appeared "earlier." The bijection establishes a similarity in size. + +2. For all $x \in X$, $i \leq j$ in R because the largest (least) up set it could have must be smaller than the up sets of anything in its down set. As described in part 1, the subset sequence means that if there are i-1 lesser down sets, the vertices behind those downsets must define at least i-1 lesser up sets, so $j \geq i$. + +3. If $x < y$ in P, x is in the down set of y and y is in the up set of x. All of the lesser (larger) up sets than x's also have lesser (smaller) down sets than y's. As a subposet, $|D|=|U|$ and with the addition of x's down set, k (number of y down sets) $>$ j (number of x up sets) in all cases. + +4. For every up and down set, at least one vertex has that up or down set. This means that every integer is used at least once as a left endpoint and as a right endpoint in the final interval representation. If the interval representation could be made on [d-1], this would force two previously comparable intervals to be incomparable (a right endpoint that was one away from a left endpoint is now on the same integer). It is also unique because none of the endpoints could be moved w/o similar dilemma. + +\noindent {\bf Q6)} + +a. If each of the linear orders are "flipped" so that if $a < b$, $a' > b'$, then the intersection of those linear orders is the dual of P. The number of linear orders defining an intersection stays the same. + +b. Let Q=(Y,Q) be a superset of P=(X,P) --- that is, $X \subset Y$ and $P = Q \cap (X \times X)$. Each linear order used to define Q can be stripped of elements in Y but not in X to create a set of linear orders defining P, so $dim(Q) \geq dim(P)$. + +c. When a point is removed, all of its comparisons are removed, so it can just be "taken out" of each linear order. Once removed, there are two possible cases. Either all remaining linear orders are non-identical or more than one are the same. In the first case, the dimension stays the same. In the second, it can only decrease by one because if there were more than 2 identical orders, one of the orders would've been originally non-minimal (if point 'a' is removed and 3+ orders are removed, the one with 'a' positioned between its other two locations is redundant because any comparisons it defines are covered by one of the other two) + +d. 3, for all. + +e. Dillworth's theorem states that there is a maximal partition of size width=w into chains. The order of each chain must be preserved in every linear order by definition, so each element can be referred to by its chain without loss of generality. A first "basic order" can be created, containing all comparisons. It takes at most w-1 orders to distinctly label the invalid comparisons in that list (moving vertices from one chain along the line until all valid comparisons still exist creates one order without invalidating any proper relations). + +f. A poset like the example on the left (complete bipartite except incomparability between opposites) with 2n vertices clearly has a width equal to n because all points from one independent set makes the maximum antichain. Its dimension is equal to n because it can only define one of the partner incomparabilities per linear order. In general, set 1 $<$ set 2, so a linear order has to look like "$2 < 4 ... 9 < 10 < 7 ...$" Within n linear orders, incomparability within independent sets can be easily defined. +\bye diff --git a/tech-math/hw5.tex b/tech-math/hw5.tex new file mode 100644 index 0000000..b20efb0 --- /dev/null +++ b/tech-math/hw5.tex @@ -0,0 +1,61 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} +\noindent {\bf Q1)} %#2 + +\pre{a.} +$$\sum_{i=0}^\infty x^{i+1} = {x \over 1-x}$$ + +\pre{c.} +$$\sum_{i=0}^\infty 2^ix^i = {1 \over 1-2x}$$ + +\pre{d.} +$$\sum_{i=0}^\infty x^{i+4} = {x^4 \over 1-x}$$ + +\pre{f.} +$$(2+x)^8$$ %%BUG BUG BUG + +\pre{i.} +$$3+2x+4x^2+x^3\sum_{i=0}^\infty x^i = 3 + 2x + 4x^2 + {x^3 \over 1 - x}$$ + +\noindent {\bf Q2)} %#7 + +The generating function for $x_1$ is $1 \over 1-x$ because it is possible for all $n$. For $x_2$, $x^2 \over 1-x$ because there is no way of satisfying the restriction for $n<2$. For $x_3$, $1 \over 1-x^4$ as it is impossible for $n \not\equiv 0 ({\rm mod} 4)$ and $1+x+x^2+x^3$ for $x_4$ (because it cannot be all of the partition for $n$ more than $4$). One must also consider a fictional $x_5$ to account for the solutions which sum to less than $n$. This has the generating function $1 \over 1-x$. The combined possible number of solutions $c_n$ is the value of the coefficient for $x^n$ in their product. The product is $$x^2(1+x+x^2+x^3) \over (1-x)^3(1-x^4),$$ but by the fact that $$1+x+x^2+x^3={1-x^4 \over 1-x},$$ this is equal to $$x^2 \over (1-x)^4.$$ + +This, in closed form, becomes $${x^2 \over 6}\sum^\infty_{n=0} n(n-1)(n-2)x^{n-2} += \sum^\infty_{n=0} {n(n-1)(n-2) \over 6}x^n += \sum^\infty_{n=0} {n \choose 3}x^{n-1} += \sum^\infty_{n=-1} {n+1 \choose 3}x^n,$$ +giving a number of solutions $n+1 \choose 3$ + + + +\noindent {\bf Q3)} %#9 + +$$\sum^\infty_{n=0} {n \choose p}x^n$$ + +Note: in this problem and Q2, I used 0 and infinity as my bounds (mostly) because ${k \choose n}=0$ for $k<0$ and $k>n$. + +\noindent {\bf Q4)} %#21 + +\pre{a.} +$a_n = 7^n$ + +\pre{b.} +$$x^2e^{3x} += x^2\sum^\infty_{n=0} {(3x)^n \over n!} += x^2\sum^\infty_{n=0} {3^n x^n \over n!} += \sum^\infty_{n=0} {3^n x^{n+2} \over n!} += \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!} += \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!} += \sum^\infty_{n=2} {3^{n-2}(n)(n-1) x^n \over n!}.$$ + +This shows $a_n = n(n-1)3^n$. + +\pre{c.} +$a_n = (-1)^n n!$ + +\pre{d.} +\def\mod#1{\thinspace(\thinspace{\rm mod} #1)} +$$e^{x^4} = 1 + x^4 + {x^8 \over 2!} \dots $$ +$$a_n = \left\{{ 0 : n\not\equiv 0 \mod{4} \atop {n! \over {n\over 4}!}: n\equiv 0\mod{4} }\right\}$$ + +\bye diff --git a/tech-math/hw6.tex b/tech-math/hw6.tex new file mode 100644 index 0000000..6d0ab8c --- /dev/null +++ b/tech-math/hw6.tex @@ -0,0 +1,33 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\noindent {\bf Q1)} %#13:2 + +Bob is right because if the flow of the network were greater than eighteen, the flow into the sink (T) would have to be greater than 18, which is greater than the sum of the capacities of incoming edges from G, A, and H. + +\noindent {\bf Q2)} %#13:3 + +$(S,H,B,I,A,D,T)$ has a flow $\delta = 1$ because of the limiting factor BI. The update would change SH to a flow of 2, HB to 2, IB to 0, IA to 10, and AT to 4---setting $\hat\phi = \phi + 1 = 16.$ + +\noindent {\bf Q3)} %#13:6 + +54. + +\noindent {\bf Q4)} %#13:10 + +$\phi = 73.$ + +Cut: $$\left\{ {L = \{S,C,F,G,E\} \atop U = \{T,A,B,D\}}\right\}$$ + +\noindent {\bf Q5)} %#10:4 + +According to Theorem 7.12, $$lim_{n\to\infty} {d_n\over n!} = {1\over e}.$$ This means that the odds one of the permutations Zori chooses is a derangement is approximately ${1\over e}$, meaning that if Bob paid one dollar to pay, he should win with a slightly higher payout around $2.72$ (to make the game fair). + +\noindent {\bf Q6)} %#10:5 + +\pre{a.} Because the connections are independent, the graph generation can be simulated as only running on that 3-element subgraph. Because it is connected if all three possible edges exist, the odds that all three were selected to exist is ${1\over2}^3 = {1\over8} = P(E_S).$ + +\pre{b.} $P(E_S) = P(E_S|E_T)$ because $P(E_S) = {1\over 8}$ and $E_T$ being true guarantees nothing about any of the independent selections on $S$ (i.e. if their intersection is one vertex, $E_T$ doesn't show that any vertex pair on $S$ shares an edge). + +\pre{c.} Regardless of if connections form between 3 and 5 or 4 and 5, both conditions state that $\{2,3,4\}$ is fully connected. Thus, $23$ is an edge, and the odds that $S$ is connected are equal to the independent coin tosses respective to $12$ and $13$ (a $1\over4$ chance in either case). + +\bye diff --git a/tech-math/ws3.tex b/tech-math/ws3.tex new file mode 100644 index 0000000..841c9a9 --- /dev/null +++ b/tech-math/ws3.tex @@ -0,0 +1,64 @@ +\input ws-form.tex +\input tikz%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 + +\def\G{{\bf G}} +\question{% +Q1 - (Chapter 5, Exercise 18) Find a proper $(t+1)$-coloring of the graph $\G_{t+1}$ in Mycielski's proof of Proposition 5.25. This establishes that $\chi(\G_{t+1})\leq t+1$. +}{ +$\G_{t+1}=(V,E)$ is constructed as a $t$-colorable graph $\G_t$, an independent graph $I$ where $|I|=|G_t|=n$, and a separate vertex $z$. For the distinct vertices $i_1,i_2,\dots,i_n \in I$, $\{i_k,z\} \in E$ and $\{i_k,g_{G_j}\} \in E$ if $\{G_{t_j},G_{t_i}\} \in E$, given a similar enumeration on $G$. + +Let $\phi:V\to C$ be a proper coloring where $C$ is a set of colors $|C|=t+1$. If $\phi(i_k)=\phi(G_{t_j})$ and $\phi(z)=c$ where $c \notin \phi(I)$, $\phi$ is a proper coloring of $G_{t+1}$ on $t+1$ colors. +} +\question{% +Q2 - (Chapter 5, Exercise 20) Construct and draw the graph $\G_5$ from Mycielski's proof of Proposition 5.25. +}{ +\tikzpicture + \node[draw,circle,inner sep=0.1cm,fill=white] (a) at (0,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (b) at (0,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (c) at (1,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (d) at (2,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (e) at (1,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (f) at (0,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (g) at (3,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (h) at (2,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (i) at (1,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (j) at (0,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (k) at (4,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (l) at (3,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (m) at (2,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (n) at (1,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (o) at (0,4) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (p) at (5,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (q) at (4,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (r) at (3,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (s) at (2,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (t) at (1,4) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (u) at (0,5) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (v) at (6,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (w) at (5,1) {}; + \draw (a) -- (b) -- (c) -- (d) -- (e) -- (a); + \draw (a) -- (f) -- (c); + \draw (b) -- (g) -- (d); + \draw (c) -- (h) -- (e); + \draw (d) -- (i) -- (a); + \draw (e) -- (j) -- (b); + \draw (f) -- (k); \draw (g) -- (k); \draw (h) -- (k); \draw (i) -- (k); \draw (j) -- (k); %G_4 + \draw (a) +\endtikzpicture + Starting with $C_5$, I constructed $G_4$ and then $G_5$ outwards from the origin. + AAAAAAAHHHHHHH. I have decided to complete this on paper. +} +\question{% +Q3 - (Chapter 5, Exercise 31) Exhibit a planar drawing of an eulerian planar graph with 10 vertices and 21 edges. +}{ +} +\question{% +Q4 - (Chapter 5, Exercise 32) Show that every planar graph has a vertex that is incident to at most five edges. + }{} +\bye diff --git a/tech-math/ws4.tex b/tech-math/ws4.tex new file mode 100644 index 0000000..5a6ad0c --- /dev/null +++ b/tech-math/ws4.tex @@ -0,0 +1,52 @@ +\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 diff --git a/tech-math/ws5.tex b/tech-math/ws5.tex new file mode 100644 index 0000000..ff21fa2 --- /dev/null +++ b/tech-math/ws5.tex @@ -0,0 +1,28 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} +\noindent {\bf Q1} %#1 + +\pre{a.} $(A^2-A-2)r(n) = 0$ + +\pre{b.} $(A^4-3A^3+A^2+A)r(n) = 0$ + +\pre{c.} $(A^3-5A+1)g(n) = 3^n$ + +\pre{d.} $(A^3-A^2+2A-1)h(n-3) = 0$ + +\pre{e.} $(A^5 - 4A^4 - A^2 - 3)r(n-5) = (-1)^n$ + +\pre{f.} $(A^2 - A - 1)b(n-2) = 2^{n+1} - n^2$ + +\noindent {\bf Q2)} %#3 + +Equivalent to $$(A^2-3A+2)g(n) = 0.$$ $$A^2-3A+2=(A-1)(A-2).$$ Thus, $g(n) = c_1 + 2^n$. + +\noindent {\bf Q3)} %#5 + +The Fibonacci formula is $a_{n+2} = a_{n+1} + a_n \to (A^2-A-1)a(n) = 0$. This has roots $1 + \sqrt{5} \over 2$ and $1 - \sqrt{5} \over 2$. Thus, its solution set is $$a(n) = c_1\left({1+\sqrt{5} \over 2}\right)^n + c_2\left({1+\sqrt{5} \over 2}\right)^n.$$ + +\noindent {\bf Q4)} %#7 + +This yields the solution set, by previously mentioned methods, $$f(n) = c_1 5^n + c_2 (-2)^n.$$ For this set, $$f(0)=2= c_1 + c_2$$ and $$f(1) = 10 = 5c_1 - 2c_2.$$ Solving as a system of equations, this gives $c_1 = 2$ and $c_2 = 0$. The solution is, therefore, $$f(n) = 2(5)^n$$. + +\bye |