Learn anything, properly.

Probability Theory · Chapter 1

Type your answer; the page checks it

1. A fair coin is tossed three times. List the sample space of ordered results, and for the events \(A\) , “at least two heads”, and \(B\) , “the first toss is a head”, compute \(P(A)\) , \(P(B)\) , \(P(A\cap B)\) , and \(P(A\cup B)\) , checking the last against Theorem 1.3(f).

   Answer

   The sample space has the \(8\) equally likely sequences HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. \(A=\{\text{HHH},\text{HHT},\text{HTH},\text{THH}\}\) and \(B\) is the set of four sequences beginning with H, so \(P(A)=P(B)=\tfrac12\) . \(A\cap B=\{\text{HHH},\text{HHT},\text{HTH}\}\) has probability \(\tfrac38\) , and \(A\cup B\) has five outcomes, probability \(\tfrac58=\tfrac12+\tfrac12-\tfrac38\) .

Probability Theory · Chapter 7

How many rolls? Type a number

9. Use the weak law to find a number of rolls of a fair die that guarantees the sample mean lies within \(0.1\) of \(3.5\) with probability at least \(0.9\) .

   Answer

   One roll has variance \(\tfrac{35}{12}\) . The weak law requires \(\dfrac{35/12}{n\,(0.1)^2}\le 0.1\) , that is, \(n\ge 2917\) .

Probability Theory · Chapter 3

The smaller of two dice: check your value

17. Use the tail-sum formula to find the expected value of the smaller of the two numbers when two fair dice are rolled, and check that the expected smaller and expected larger numbers add up to the expected sum.

    Answer

    For the smaller number \(L\) , \(P(L\ge k)=\bigl((7-k)/6\bigr)^2\) , so \(E[L]=(36+25+16+9+4+1)/36=91/36\approx 2.53\) . Since the smaller and larger numbers add up to the sum of the two dice, \(E[L]+E[M]=\tfrac{91}{36}+\tfrac{161}{36}=7\) .

Discrete Optimization · Chapter 3

Stuck? Open a hint, not the solution

12. An undirected network allows flow in either direction on each edge up to its capacity. Explain how to convert it to a directed network, and show that a maximum flow never needs to use both directions of one edge.

    Hint

    Replace each edge by two opposite arcs of the same capacity. If a flow uses both directions with amounts \(p\ge q>0\) , reduce both by \(q\) : conservation at both endpoints and the value are unchanged, and one direction becomes empty.

Real Analysis · Chapter 1

A hint before the proof

2. Using only the order axioms (O1) to (O4) and the field axioms, prove that \(0<a<b\) implies \(a^2<b^2\) , and deduce that a positive real number has at most one positive square root.

   Hint

   Multiply \(a<b\) by the positive number \(a\) to get \(a\cdot a<a\cdot b\) , and by the positive number \(b\) to get \(a\cdot b<b\cdot b\) ; both steps are (O4). Then use (O2). For uniqueness, if \(\beta\ne\gamma\) are positive, (O1) says one is smaller, and then their squares differ.

Differential Equations · Chapter 1

A hint for the direction field

7. For \(y'=t^2+y^2-1\) describe the isoclines, find the region of the plane in which solutions are decreasing, and explain why every solution that enters the region \(t>1\) is increasing from then on.

   Hint

   The isocline of slope \(c\) is the circle \(t^2+y^2=1+c\) , which exists for \(c>-1\) . Solutions decrease exactly where \(t^2+y^2<1\) . For the last part, compare \(t^2\) with \(1\) .

Game Theory · Chapter 1

Change one payoff; a hint if you need it

17. For Example 1.5, change the single payoff \(u_2(M,C)\) from \(6\) to \(0\) . Redo the elimination, say how many strategies are now strictly dominated in the full game, and explain why the surviving profile is the same although the knowledge needed to reach it has changed.

    Hint

    With \(u_2(M,C)=0\) , compare \(C\) with \(L\) in all three rows. You should find two strictly dominated strategies in the full game, one for each player. By Theorem 1.7 the order does not matter, so the survivor is unchanged; what changes is that the removal of \(C\) no longer needs player 2 to know anything about player 1.

Discrete Mathematics · Chapter 1

A proof arrives one step at a time

Theorem 1.12 (irrationality of the square root of two). There are no positive integers \(a\) and \(b\) with \(a^{2}=2b^{2}\) . Consequently \(\sqrt2\) is not a rational number.

Proof. Suppose, for contradiction, that positive integers \(a\) and \(b\) with \(a^{2}=2b^{2}\) exist. Among all such pairs choose one in which \(b\) is as small as possible; this can be done because every nonempty set of positive integers has a least element.

Since \(a^{2}=2b^{2}\) , the integer \(a^{2}\) is even, so \(a\) is even by Proposition 1.11. Write \(a=2c\) with \(c\) a positive integer. Then \(4c^{2}=2b^{2}\) , so \(b^{2}=2c^{2}\) . Thus \(b^{2}\) is even, and by Proposition 1.11 again \(b\) is even. Write \(b=2d\) with \(d\) a positive integer. Substituting into \(b^{2}=2c^{2}\) gives \(4d^{2}=2c^{2}\) , that is, \(c^{2}=2d^{2}\) .

Now \((c,d)\) is a pair of positive integers with \(c^{2}=2d^{2}\) and \(d<b\) . This contradicts the choice of \(b\) as the smallest possible. Hence no such pair exists. If \(\sqrt2\) were rational it would equal \(a/b\) for some positive integers \(a\) and \(b\) , and squaring would give \(a^{2}=2b^{2}\) , which we have shown to be impossible.

Discrete Optimization · Chapter 2

Why Dijkstra is right, step by step

Theorem 2.4 (correctness of Dijkstra’s algorithm). If \(c_{vw}\ge 0\) for every arc, then at the moment a node \(v\) is settled its label equals \(d(v)\) , and at termination \(\rho(v)=d(v)\) for every node.

Proof. Every finite label is the length of a walk from \(s\) , namely the one traced back through predecessors, so \(\rho(v)\ge d(v)\) throughout. We show by induction on the order of settling that \(\rho(v)\le d(v)\) when \(v\) is settled. The first node settled is \(s\) , with \(\rho(s)=0=d(s)\) .

Suppose \(v\) is about to be settled and all earlier settled nodes carry their distances. Let \(P\) be any path from \(s\) to \(v\) . It starts in \(S\) and ends outside \(S\) , so it has a first arc \((x,y)\) with \(x\in S\) and \(y\notin S\) . When \(x\) was settled the arc \((x,y)\) was relaxed, so \(\rho(y)\le\rho(x)+c_{xy}=d(x)+c_{xy}\) , and \(d(x)\) is at most the length of the part of \(P\) up to \(x\) . Hence \(\rho(y)\) is at most the length of \(P\) up to \(y\) . The remainder of \(P\) consists of arcs of nonnegative length, so \(\rho(y)\) is at most the length of \(P\) . Finally \(\rho(v)\le\rho(y)\) , because \(v\) was chosen with the smallest label among unsettled nodes. So \(\rho(v)\) is at most the length of every path to \(v\) , that is, \(\rho(v)\le d(v)\) .

A node never settled has label \(\infty\) and is unreachable, since otherwise the argument above applied to a path reaching it would exhibit an unsettled node with a finite label.

Rocket Science · Chapter 1

Every figure proves one sentence

Probability Theory · Chapter 1

Why birthdays collide so soon

Game Theory · Chapter 2

Where the two reaction curves meet

Three courses · Chapter 1

Recall what you read, card by card

1. Definition 1.1 (statement). Discrete Mathematics

   Definition 1.1 (statement). A statement, or proposition, is a sentence that is either true or false, and not both. Its truth value is \(T\) if it is true and \(F\) if it is false.

2. Definition 1.1 (game in strategic form). Game Theory

   Definition 1.1 (game in strategic form). A game in strategic form consists of a finite set of players \(N=\{1,\dots,n\}\) ; for each player \(i\) a nonempty set \(S_i\) of strategies; and for each player \(i\) a payoff function

   \[ u_i:S_1\times\dots\times S_n\to\mathbb R . \]

3. Definition 1.1 (algebra and sigma-algebra). Measure Theory

   Definition 1.1 (algebra and sigma-algebra). Let \(X\) be a set. A family \(\mathcal A\) of subsets of \(X\) is an algebra on \(X\) if

   \[ X\in\mathcal A,\qquad A\in\mathcal A\ \Rightarrow\ A^c\in\mathcal A,\qquad A,B\in\mathcal A\ \Rightarrow\ A\cup B\in\mathcal A . \]

Three courses · Chapter 1

Three more cards to recall

1. Definition 1.1 (cross product). Multivariable Calculus

   Definition 1.1 (cross product). For \(\mathbf a=(a_1,a_2,a_3)\) and \(\mathbf b=(b_1,b_2,b_3)\) in \(\mathbb R^3\) ,

   \[ \mathbf a\times\mathbf b=(a_2b_3-a_3b_2,\ a_3b_1-a_1b_3,\ a_1b_2-a_2b_1). \]

2. Definition 1.1 (partial differential equation, classical solution). Partial Differential Equations

   Definition 1.1 (partial differential equation, classical solution). A partial differential equation of order \(m\) for an unknown function \(u\) of the variables \(x=(x_1,\dots,x_n)\) is a relation

   \[ F\bigl(x,u,Du,D^2u,\dots,D^mu\bigr)=0 , \]

3. Definition 1.1 (closed system). Rocket Science

   Definition 1.1 (closed system). A closed system is a fixed collection of matter: no mass enters or leaves it during the time considered. For a closed system with total momentum \(P\) and total external force \(F_{\mathrm{ext}}\) ,

   \[ \frac{\mathrm dP}{\mathrm dt}=F_{\mathrm{ext}}. \]

Game Theory · Chapter 1

Select any sentence and ask

Two cafés, run by Arno and Bea, face each other across a square and sell the same espresso. Each Monday the owners set a price for the week, High or Low, without knowing what the other has chosen. If both charge High, each clears a weekly profit of 6 (in hundreds of euros). If both charge Low, each clears 3. If one charges Low and the other High, the low-price café takes most of the trade and clears 8, while the other clears 1. What will the owners do?

Discrete Mathematics · Chapter 1

Four cards on a table: ask about them

Four cards lie on a table. Each has a letter on one side and a number on the other, and the faces you can see are A, K, 4, and 7. Someone asserts a rule: if a card has a vowel on one side, then it has an even number on the other. Which cards must you turn over to find out whether the rule holds for these four cards?

Continuous Optimization · Chapter 1

A workshop with two products: ask why

A small workshop makes two products. Each unit of the first earns a profit of 3 and each unit of the second a profit of 2. A unit of either product needs one hour of assembly, and 4 assembly hours are available per day; a unit of the first needs two hours on a finishing machine, a unit of the second needs one, and the machine runs 5 hours per day. How much of each product should the workshop make?