From cf201409a092b037371d09b4e09a16a0d7974898 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Wed, 20 Nov 2019 07:23:06 -0500 Subject: update --- jones-la/paret.tex | 19 ++++++++++++ jones-la/reflection.tex | 34 +++++++++++++++++++++ jones-la/shoot.tex | 50 +++++++++++++++++++++++++++++++ tech-math/hw3.tex | 70 ++++++++++++++++++++++++++++++++++++++++++++ tech-math/hw4.tex | 36 +++++++++++++++++++++++ tech-math/hw5.tex | 61 ++++++++++++++++++++++++++++++++++++++ tech-math/hw6.tex | 33 +++++++++++++++++++++ tech-math/ws3.tex | 64 ++++++++++++++++++++++++++++++++++++++++ tech-math/ws4.tex | 52 ++++++++++++++++++++++++++++++++ tech-math/ws5.tex | 28 ++++++++++++++++++ wroblewski-world/seminar.tex | 8 +++++ ws-form.tex | 3 +- 12 files changed, 457 insertions(+), 1 deletion(-) create mode 100644 jones-la/paret.tex create mode 100644 jones-la/reflection.tex create mode 100644 jones-la/shoot.tex create mode 100644 tech-math/hw3.tex create mode 100644 tech-math/hw4.tex create mode 100644 tech-math/hw5.tex create mode 100644 tech-math/hw6.tex create mode 100644 tech-math/ws3.tex create mode 100644 tech-math/ws4.tex create mode 100644 tech-math/ws5.tex create mode 100644 wroblewski-world/seminar.tex diff --git a/jones-la/paret.tex b/jones-la/paret.tex new file mode 100644 index 0000000..8e0a9ad --- /dev/null +++ b/jones-la/paret.tex @@ -0,0 +1,19 @@ +%%Formatting +\font\twelverm=ptmr7t at 12pt +\font\fourteenrm=ptmr7t at 14pt +\twelverm \baselineskip=24pt +\parindent=0.5in + +%%Header +\headline={\headline={Rohrer \pageno}} \nopagenumbers \vsize=9in +{\obeylines\parindent=0in +Holden Rohrer +Jones +AP Lang +4 Nov 2019 +\centerline{\fourteenrm Paret Essay}\baselineskip=28pt\par} + +%%Content + + +\bye diff --git a/jones-la/reflection.tex b/jones-la/reflection.tex new file mode 100644 index 0000000..a9b9299 --- /dev/null +++ b/jones-la/reflection.tex @@ -0,0 +1,34 @@ +\input mla8 + +\numberfirstpage +\name{Holden} \last{Rohrer} +\prof{Jones} +\clas{AP Lang} + +%\header +\medskip +\noindent{\bf Part 1: Book Overview} + +I read Stephen Hawking's ``A Brief History of Time,'' which used a much less narrative structure than a traditional memoir does. +It describes modern physics historically---how different theories developed over time, and I think that's why it's so effective. +Personal anecdotes like Hawking's co-development of the ``no-boundary proposal,'' where the universe is treated as flat (changing the definition of time so that it becomes indistinguishable with the spatial dimensions) or Newton's bitter feuds with other scientists are much more comprehensible than a purely mathematical construction of modern models. + +It centers around the two major modern theories of physics, quantum mechanics (the theory that describes very small things) and general relativity (the theory that describes very heavy things). +Each chapter is organized chronologically and centers on a certain realization or broad change in consensus, so they mostly start with a discussion of ``classical'' physics, theories that made intuitive sense on a human scale like the laws of motion or the geocentric (universe centered on Earth) model. + +As such, each is effectively a story. + +\noindent{\bf Part 2: My Passion} + +My passion is problem-solving. +At the beginning of this project, I thought that it was some specific field or study like computer science or mathematics or engineering, but my favorite bits of those fields are centred around solving problems. +In computer science or software engineering, there's a subcategory of embedded systems---small, highly constrained computers like the one that runs a thermostat or records data from a microphone into a wire. +I've set up and used a few of these for different tasks. +One such use case is running a small speaker or, as I attempted to do in a project for the engineering class, running headphones from an aux cable and providing a button-based interface to a small song library stored on an SD card. +My group was unsuccessful for a number of reasons, but we managed + +\noindent{\bf Part 3: Connection} +The story which stood out to me the most was Hawking's development of Hawking Radiation, where black holes release energy like a star, albeit at much lower temperatures. + + +\bye diff --git a/jones-la/shoot.tex b/jones-la/shoot.tex new file mode 100644 index 0000000..e0d2ff9 --- /dev/null +++ b/jones-la/shoot.tex @@ -0,0 +1,50 @@ +{\bf Paraphrase} + +I am a British police officer stationed in an Indian city, and therefore lack any respect from the locals---all of whom find me a ridiculous European, especially the Buddhists. +I agree with them: my status as a representative of imperialism gives them just cause, especially given all the horrendous things I myself have done. +I feel guilty for extending the empire, so I hate it, but so too do I hate the locals. + +One day, I received a call that an elephant was rampaging upon the town. +The elephant had struck down a hut, killed a cow, and raided a market because it was a tame elephant in ``must.'' +All seemed straightforward, but when I reached the area, little information was available. +The people knew neither its location nor its movements, and the area remained chaotic. +Nonetheless, I discovered (with some aid of local officials) a man who was trampled by the elephant so violently the skin off his back was torn cleanly. + +The orderly gave me a more powerful rifle than what I had arrived with, intending to only scare the beast. +But as the people had seen my rifle, they followed me out to the elephant, forming a large, unnerving crowd across the road. +I felt obliged to indulge the crowd; they wanted to see the elephant dead, so I had to give it to them so that I would not be laughed at. +But when I saw the elephant my opinion changed immediately. I could not kill such a magnificent beast, simply grazing the marshy fields, but I had to. +Despite the natives' uncoercive, unarmed status, I (even as an armed white man) still had to impress them as a matter of duty. + +For some time, I watched the elephant beat grass across his knees and chew it slowly. It would be wrong to kill such an animal, so I had to determine some method of avoidance. +I chose a slow approach ended with gunshots to the elephant if he charged me, but quickly I recognized that I would very easily become that man dead by the elephants' hooves. +I could not retreat, for I would be laughed at, but I couldn't approach and fail. +I had to shoot the elephant. + +I got down on the ground, and shot him four or five times, the crowd cheering at each. +While this did not kill the elephant for he is yet formidable against a .44 rifle, it crippled him. +The locals raced towards the elephant lying there helplessly while he died slowly, blood spurting out of his heart. +I left, but later I heard that it took the beast half an hour to fully die. + +Afterwards, the incident was discussed at length, even by other Europeans. +Half thought I had chosen wrong because the elephant was such a valuable creature. +The other segment sided with me, if only because I had legally done the right thing. + +\bigskip +{\bf Central Argument} + +Imperialism is a cruel tradition that drives even those in power to act heinously. +The pressures of appeasing both the natives (whom hate the enforcer) and one's superiors necessarily leads to poor and rash decision-making, often even encouraging unrighteous decisions. + +\bigskip +{\bf Assertions} + +1. ``Theoretically, I was all for the Burmese and all against their oppressors, the British.'' ``As a police officer, I was an obvious target.'' The police officer's dilemma is clear because he can neither follow his own sense of propriety and appease the locals (because his job required cruelty), but also he cannot fully engage the British ruling because then he would become ultimately unfavored with the Burmese. + +\bigskip +{\bf Words} + +\bigskip +{\bf Rhetorical Strategies} + +\bye 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 diff --git a/wroblewski-world/seminar.tex b/wroblewski-world/seminar.tex new file mode 100644 index 0000000..bca255d --- /dev/null +++ b/wroblewski-world/seminar.tex @@ -0,0 +1,8 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\pre{1.} Why did the Europeans believe they were justified in colonizing? + + +\pre{2.} What role did African Kingdoms play in this system? Were they equally as guilty as Europeans? To what point could they have resisted? + +\pre{3.} Given all that we have today, was European colonization of Americas necessary/good? Would Europeans and indigenous argue this differently? diff --git a/ws-form.tex b/ws-form.tex index debafd0..e85203a 100644 --- a/ws-form.tex +++ b/ws-form.tex @@ -4,8 +4,9 @@ \par\noindent #1 \bigskip +\def\vfilll{\vskip0pt plus 1filll} {\color{blue}% #2 -}\vfil +}\vfilll \penalty-200 } -- cgit