# Math for CS (MIT 6.042J) Study Group Shared Notes

## Session 26

### Problem 1

Part a.
$\frac{12!}{3!3!3!3!} = 369,600$

b. $4!$ (since each group can be seen as a separate unit) (this is a 24-to-1 mapping)

c. How many group assignments are possible?

part a / part b

$\frac{12!}{3!3!3!3!} / 4!$
$369,600 / 4! = 369,600 / 24 = 15,400$

part d.

$\frac{(3n)!}{3!^nn!}$

### Problem 2

part a.

This seems a lot like the question from last week. It maps to a 16 bit string with 8 ones.

${ 16 \choose 8 } = \frac{16!}{8!8!} = 259,459,200$

part b. How many nonnegative integer solutions are there for $x_1 + x_2 + \dots + x_m = k$

If one x term is k, and the rest are zero then there are m options.

If one x term is $k-1$, another x term is 1, and the rest are zero then there are $m * (m - 1)$ options.

$mk!$ different options for the x terms.

$\frac{k!}{x_1!x_2!...x_m!}$

${k \choose m} = \frac{k!}{m!(k-m)!}$

part c.

## Session 22

**Problem 1:**
Companies are serenaded by students

Starting state:

| Students | Day 1 | Day 2 | Day 3 | Day 4 | Day 5 |
| --------- | ------------ | ---------------- | -------------------- | ---------------- | --- |
| Albert | | | | | AT&T |
| Sarah | Draper | Draper | ~~Draper~~, Bellcore | Bellcore | Bellcore |
| Tasha | Bellcore | ~~Bellcore~~, HP | HP | HP | HP |
| Elizabeth | AT&T, ~~HP~~ | AT&T | AT&T | ~~AT&T~~, Draper | Draper |

## Session 17, DAGs

## Session 16, Digraphs

**Part a)**

dist(u ,v) = dist(u,x) + dist(x,v) implies x is on a shortest path from u to v

by contradiction:
suppose x is NOT on a shortest path from u to v
But then when you merge the two walks with x-hat, the resulting merge would *not* be a shortest path, contradicting the statement that dist(u,v) is a shortest path. Therefore, x must be on a shortest path.

### Problem 3

**Part a)**
Find a string of length 10 that contains all possible combinations of {0,1} of length 3.

possible 10-bit string: 0001011100 (joe)
possible 10-bit string: 0100011101 (kate)
possible 10-bit string: 1110001011 (liz)

## Session 13

Related modular arithmetic problems with solutions: https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec22_sol.pdf

### Problem 1.

$\text{remainder}(9876^{3456789}(9^{99})^{5555}-6789^{3414259}, 14)$

### Problem 2.

Suppose $a, b$ are relatively prime and greater than 1. In this problem you will prove the Chinese Remainder Theorem, which says that for all $m, n$ there is an $x$ such that it solves this system of equations:

$x \equiv m \text{ mod } a$
$x \equiv n \text{ mod } b$

Moreover, $x$ is unique up to congruence modulo $ab$, namely, if $x^\prime$ also satisfies the above congruences then

$x^{\prime} \equiv x \text{ mod } ab$

**part a** Prove that for any $m, n$, there is some $x$ satisfying the system of equations.

Let $b^{-1}$ be an inverse of b modulo a.
Let $a^{-1}$ be the inverse of a modulo b.
Define $e_{a} := b^{-1}b$.
and $e_{b} := a^{-1}a$.
Let $x = me_{a} + ne_{b}$

$e_{a}$ $\equiv$ 1 $\text{ mod } b$
$e_{b}$ $\equiv$ 1 $\text{ mod } a$

## Session 12

The Pulverizer:

[Solutions to problem 4](https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec21_sol.pdf)

### Problem 1.

(a) Use the Pulverizer to find integers $x, y$ such that

$$x30 + y22 = \text{gcd}(30, 22)$$

x30 + y22 = 2

| x | y | rem(x,y) | = x - q * y |
| --- | --- | --------:| ----------------------- |
| 30 | 22 | 8 | = a - b |
| 22 | 8 | 6 | = b - 2(a - b) |
| | | | = (b -2a + 2b) |
| | | | = -2a + 3b |
| 8 | 6 | 2 | = 8 - 6 |
| | | | = (a - b) - (-2a + 3b) |
| | | | = 3a - 4b |
| 6 | 2 | 0 | = 6 - 3(2) |
| | | | = (-2a +3b) - 3(3a -4b) |
| | | | = -2a +3b - 9a +12b |
| | | | = -11a + 15b |
| 2 | 0 | 0 | |

Answer is 3a - 4b.

(b) Find integers x' and y' such that y' is non-negative and less than 30

3 - 22 and -4 + 30
-19a + 26b

### Problem 2 (a)

$m = 2^{9}5^{24}11^{7}17^{12}$ and $n = 2^{3}7^{22}11^{211}13^{1}17^{9}19^{2}$

$\text{gcd}(m,n) = 2^{3}11^{7}17^{9}$

$\text{lcm}(m,n) = 2^{9}5^{24}7^{22}11^{211}13^{1}17^{9}19^{2}$

LCM of 15 and 18 example:

### Problem 3


...
Linear combinations:

Rule 2
3 and 4
5 and 6
7

**Part c**
Related part from Euclid Algorithm:

question for clarity: what is $(loga + logb) - (log(a/2) + logb)$?

### Problem 4.

#### Part B

if $a|bc$ and gcd(a,b) = 1, then a|c.

Given that $a|bc$, then $a|b$ and/or $a|c$. We know that the largest $k \in Z$, where $k|a$ and $k|b$ is 1 since $\text{gcd}(a,b) = 1$. Therefore a cannot divide b. This means that $a|c$.

#### Part C

if p|bc then p|b or p|c

not(p|b or p|c) => not(p|bc)
not(p|b) and not(p|c) => not(p|bc)

This is clearly true since if p cannot divide b and cannot divide c, then it cannot divide bc.

#### Part D

"Let $m$ be the smallest integer linear combination of $a$ and $b$ that is positive. Show that $m = gcd(a,b)$"

https://math.stackexchange.com/questions/219941/is-greatest-common-divisor-of-two-numbers-really-their-smallest-linear-combinati

Let m be the smallest integer linear combination of a and b that is positive. Show that m = gcd(a,b). Corollary 8.2.3: "a linear combination of a and b is a multiple of gcd(a,b)." It follows that the smallest multiple of the gcd(a,b) is gcd(a,b).

## Session 11

- [In-class questions, session 11](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp11.pdf)
- [Solutions from 2010](https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec08_sol.pdf)

## Session 10

- [In-class questions, session 10](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp10.pdf)
- [SOLUTIONS from 2010](https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec19_sol.pdf)

### Problem 1(a)

Prove that $\frac{1}{x}$ (which is also $x^{-1}$) is an F18 function.

Reminder on inverse: https://www.wolframalpha.com/input/?i=inverse+of+y%3Dx%5E2

Things that we can make

| Thing | Rule |
| ----------------------------- | ------------------------------------------------------------------------------------------ |
| $y = x$ | This is `id(x)` |
| $y = x^2$ | This is $fg$ |
| $y = 2^g$ | This is $2^g$ |
| $y=\frac{log_{e}x}{log_{e}2}$ | [Inverse of $2^g$](https://www.wolframalpha.com/input/?i=inverse+of+y%3D2%5Ex) |
| $y = log_{e}x$ | $y=\frac{log_{e}x}{log_{e}2}$ multipled by the constant $y = log_{e}2$ (a constant) |
| $y = e^x$ | inverse of $log_{e}x$ |
| $y = -log_{e}x$ | $y = log_{e}x$ multiplied with $y = -1$ (a constant) |
| $y = e^{-log_{e}x}$ | $y = e^x$ composed with $y = -log_{e}x$ |

$y = e^{-log_{e}x}$ is equivalent to $y = 1/x$ https://www.wolframalpha.com/input/?i=y%3De%5E%28-log%28x%29%29

### Problem 1(b)

Not done here. Prove the derivative for each base case.

Prove for each rule.

### Problem 2 (a)


Proof by structural induction that $$\text{RecMatch} \subseteq \text{Erasable}$$

Base case:
$\lambda \in Erasable$ and $\lambda \in RecMatch$

Inductive hypothesis:
$$\forall \text{ s, t } \in \text{ RecMatch } => \text{ s, t } \in \text{ Erasable }$$

For all two-argument constructors $c = [ s ] t$

Base case:
- For $s = \lambda$, the empty string is erasable by definition of Erasable.

Constructor case:

Suppose that P(s, t) and assume that P(c(s, t)).

### Problem 2 (b)

Base case:

P(n) for n = 0, which is a length 0 string (lambda), which is the base case of the definition of RecMatch

Case (y is the empty string): since y is the result of removing a single instance of p from x, and y is empty, x must have been p, which is an element of RecMatch

Case (y = [s]t for some strings s,t in RecMatch):

- Subcase: x = py: y is in RecMatch by inductive hypothesis, and y can be produced by a single erase of x, which must have been in

- Subcase: x is of the form [s']t where s is an erase of s'. (Solution is given)

- Subcase: x is of the form [s]t' where t is an erase of t'.
- We know t $\in$ RecMatch, so t' is $\in$ Erasable. But |t'| < |x| so by induction hypothesis, we can assume t' is $\in$ RecMatch. Then x must be the result of the constructor step of RecMatch, so x $\in$ RecMatch.

### Problem 3a

$S := {2^k3^m5^n | k,m,n \in N}$

Base case $1 \in S$ (k,m,n all are 0)
Constructor cases:
if $n \in S$, then $2n \in S$.
if $n \in S$, then $3n \in S$.
if $n \in S$, then $5n \in S$.

### Problem 3b

$S := {2^{k}3^{2k+m}5^{m+n}\ |\ k,m,n \in N}$

Base case $1 \in S$ (k,m,n all are 0)
Constructor cases:
if $a \in T$, then $18a \in T$ (k = 1, m,n = 0, gives $2^{1}3^{2}5^{0} = 18$).
if $a \in T$, then $15a \in T$ (m = 1, k,n = 0, gives $2^{0}3^{1}5^{1} = 15$).
if $a \in T$, then $5a \in T$ (n = 1, m,k = 0, gives $2^{0}3^{0}5^1 = 5$).

### Problem 3c

$L := \{(a,b) \in Z^2 | (a - b) \text{ is a multiple of 3}\}$

Base case: $(0, 0) \in L$
$(a, b) = (1, 1) \in L$
$(a, b) = (2, 2) \in L$

Constructor case:
if $(a, b) \in L$ then $(a - 3, b) \ and \ (a + 3, b) \ and \ (a, b - 3) and (a, b + 3) \in L$

$(n, n)$
$(3(n + a), 3n)$

### Problem 3 (d)


Base case: provides numbers where the difference is 0. 0 is a multiple of 3.

Constructor cases: $P(a, b) \implies P(c(a, b))$
case i: (0,0) -> (-3,0)
(1,1) -> (-2, 1) -2 - 1 = -3
(2,2) -> (-1, 2) -1 - 2 = -3

## Session 9

- [In-class problems](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp9.pdf)

### Problem 1.
**Part a.**

$\frac{2r(s-1)}{2} + r = rs$

$r(s-1) + r = rs$
$rs - r + r = rs$
$rs = rs$

**Part b.**
The state machine reaches a final state when s = 0, so $rs = 0$ and $rs + a = xy$.

$0s + a = xy$
$a = xy$

**Part c.**

$s = \frac{s}{2}$ when s in even
$s = \frac{s-1}{2}$ when s is odd

So $s$ is at least halved per run, so the program can't run more than $\log{s} + 1$ times.

### Problem 2.

**Part a.**

Starting state:
L = 1,2,3 ... 14, 15

Impossible state:
L = 15, 14, 13 ... 2, 1

**Part b.**
Starting state:
p(L) = 0, i = 4, and 0 + 4 is even
so parity(S) = 0

Impossible state:
Every pair is out of order, so p(L) = 105 (and i is still 4), and 105 + 4 = odd
so parity(S) = 1

**Part c.**

### Problem 3.
**Part a.**

Always let a car exit the bridge.

Let in a car if:
$(2A - 3B) - 5C < 1000$

When a car enters the state becomes (3, 0, 1) *(A, B, C)*.

$(2(3) - 3(0)) - 5(1) = 1$

When the car exits then the state becomes (3, 2, 0)
$(2(3) - 3(2)) - 5(0) = 0$

If C > 1000:
Collapse bridge

** part b.**

| Column 1 | Column 2 |
| -------- | -------- |
| A | SI |
| B | SI |
| A + B | SI |
| A - B | N |
| 3C - A | WD |
| 2A - 3B | N |
| B + 3C | N |
| 2A - 3B - 6C | C |
| 2A - 2B - 3C | SD |

---

## Session 8

- [solutions to problem 1 and 2]( https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec09_sol.pdf)

### Problem 1

Proof by induction on n. The inductive hypothesis, P(n), is:

$1 + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2} < 2 - \frac{1}{n}$

We will prove that P(n) for all n > 1.

Base case: P(2):

$1 + \frac{1}{2^2} < 2 - \frac{1}{2}$
$1 \frac{1}{4} < 1 \frac{1}{2}$

Induction step: Assuming P(n) holds, we prove P(n+1) which is defined as:

$1 + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2}+ \frac{1}{(n+1)^2} < 2 - \frac{1}{n+1}$

Starting from P(n) and add $\frac{1}{(n+1)^2}$ to both sides:

$1 + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n} + \frac{1}{(n+1)^2}$

...

$(n + 1)^2 = n^2 + 2n + 1$

($\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{db}$)

$2 - \frac{1}{n} + \frac{1}{(n+1)^2}$

$2 + \frac{-(n+1)^2 + n}{(n)(n+1)^2}$

$2 + \frac{-n^2-2n-1+n}{(n)(n+1)^2}$

$2 + \frac{-n^2-n-1}{(n)(n+1)^2}$

$2 + \frac{-n^2-n}{(n)(n+1)^2} + \frac{-1}{(n)(n+1)^2}$

$2 + \frac{-n(n+1)}{(n)(n+1)^2} + \frac{-1}{(n)(n+1)^2}$

$2 - \frac{n(n+1)}{(n)(n+1)^2} - \frac{1}{(n)(n+1)^2}$

$2 - \frac{1}{(n+1)} - \frac{1}{(n)(n+1)^2}$

which is < $2 - \frac{1}{(n+1)}$

### Problem 2

**Part a.**
Induction hypothesis: Let P(n) be the proposition that for all n >= 0 there exists a tiling of a 2^n x 2^n courtyard with Bill in a corner square.

...

**Part b.**
Official solution: "To put Bill in the middle, tile each of the four quadrants, leaving the empty corner of the quadrant in the middle of the full courtyard. This leaves the four central squares of the full courtyard empty, so fill three of these squares with an L-shaped tile. This leaves a single central square untiled for Bill."

Or... rotate the quadrant with Bill so that he's in the center instead, the rest stays the same.

### Problem 3

... same as example in the book, page 135

### Problem 4

(Bogus proof)

## Session 7

### Problem 1

| R is | $$\text{iff} \ R^{-1} \ \text{is}$$ | Notes |
| -------- | -------- | -------- |
| total | a surjection | |

### Problem 2

a: {0, 1} (m: 2)
b: {2, 3} (n: 2)

2 3
0 (0, 2) (0, 3)
1 (1, 2) (1, 3)

domain: A x B = { (), (), (), () }

codomain = {0, 1, ... mn - 1}


### Problem 3
Assume f : A -> B is a total function, and A is finite.

(a.) $|f(A)| \le |B|$
(b.) If $f$ is a surjective, then $|A| \ge |B|$
(c.) If $f$ is a surjective, then $|f(A)| = |B|$
(d.) If $f$ is a injection, then $|f(A)| = |A|$
(e.) If $f$ is a bijection, then $|A| = |B|$

### Problem 4

R : A -> B
If R is a function, and X is a subset of A, then |X| >= | R(X) |, because the binary relation R could allow multiple values to point to the same $b$ ($b \in B$), and because it is a function it must have at most one arrow for ever $x$ ($x \in X$).

> Solution in [this PDF under problem 2](https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/lecture-notes/MIT6_042JS10_lec06_sol.pdf)

### Problem 5

> Surjective: >= 1 arrows IN

> 
> 

(a.) Prove that if A surj B and B surj C, then A surj C.

A surj B means |A| >= |B|

(b.) Explain why A surj B iff B inj A.

|A| >= |B| IFF |B| <= |A|

(c.) Conclude from (a.) and (b.) that if A inj B and B inj C, then A inj C

|A| $\le$ |B| and |B| $\le$ |C|, then |A| $\le$ |C|

(d.) Explain why A inj B iff **there is** a total injective function([= 1 out, $\le$ 1 in]), from A to B

Footnote: "The official definition of inj is with a total injective relation ([ >= 1 out, <= 1 in])"

Rephrase as: Explain why A $R_1$ B with a total injective relation ([ $\ge$ 1 out, $\le$ 1 in]) iff **there is** A $R_2$ B with a total injective function([= 1 out, $\le$ 1 in]), from A to B

### Problem set 2 ?

> [PDF for problem set 2](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/assignments/MIT6_042JS15_ps2.pdf)

## Session 6

- [In-class questions for session 6](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp6.pdf)
- [Problem set 1](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/assignments/MIT6_042JS15_ps1.pdf)

### Problem 1 b

$A = (A - B) \cup (A \cap B)$
$(x \in A )$ iff $(A - B) \cup (A \cap B)$
$(x \in A ) \ \text{iff} \ (x \in A \ \text{AND} \ x \notin B) \cup (A \cap B)$ -- definition of set diffeerence
$(x \in A ) \ \text{iff} \ (x \in A \ \text{AND} \ x \notin B) \ \text{OR} \ x \in (A \cap B)$ -- def of union as OR
$(x \in A ) \ \text{iff} \ (x \in A \ \text{AND} \ x \notin B) \ \text{OR} \ (x \in A \ \text{AND} \ x \in B)$ -- def of intersection as AND
let P = $(x \in A )$ and Q = ($x \in B$)
$(x \in A ) \ \text{iff} (P \ \text{AND}\ \bar{Q}) OR (P \ \text{AND} \ Q)$
= P and (NOT Q OR Q)
= P and TRUE
= P
= $(x \in A )$

### Problem 2

a.(x = $\emptyset$) := NOT($\exists z \in x$)

// note that this is the same as "x = y", where "y" = "{y, z}"
b. (x = {y, z}) := $\forall e. (e \in x \ \text{iff} \ (y \in e \ OR \ z \in e))$

could be (x = {y, z}) := $\forall e.(e \in x \ \text{iff} \ e \in \{y, z\})$

c. $x \subseteq y$ = $\forall e .(e \in x \implies e \in y)$

d. x = (y $\cup$ z) ::= $\forall e .(e \in x \iff (e \in y \ OR \ e \in z))$

> maybe: $x = y \cup z ::= x \subseteq y \text{ AND } x \subseteq z$

e. (x = y - z) := $\forall e (e \in x \ \text{iff} \ e \in y \ AND \ e \notin z)$

f. x = pow(y) := $\forall s. (s \in x \ \text{iff} \ s \subseteq y)$

g. $x = \bigcup_{z \in y}{z}$. $x = \bigcup{y}$

$x = \bigcup_{z \in y}{z}$ := $\exists s (\exists p)$

$x = \bigcup{y}$ := $\forall e . e \in x \ \text{iff} \ \forall s . ( s \in y \implies e \in s)$

### Problem 3

{a, {a,b}} equiv to {a, {b,a}}

find ordering by taking the length of each set, and taking the set difference of the larger and smaller set to remove the overlapping element

### Problem 4

- [Solution in 2005 class (PDF)](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/lecture-notes/cp2fsol.pdf)
- [Paper: "Counterexamples to conjectures about Subset Takeaway and counting linear extensions of a Boolean lattice"](https://arxiv.org/abs/1702.03018)

{1,2,3,4}

The first player may select sets with 1, 2, or 3 elements.

Game of of {1,2,3,4}

first player selects {1}

second player select {2,3,4}

first player selects {2,3} (or {2,4}, {3,4}, {2}, {3}, {4})

If the first player selects a set with 1 element ...

If the first player selects a set with 2 elements ...

If the first player selects a set with 3 elements ...

> via http://whydomath.org/Reading_Room_Material/ian_stewart/TT/triangulation.html
> 
> 

## Session 5

- [In-class questions for sesion 5](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp5.pdf)
- Note: solutions to the first couple problems are in [this PDF from the 2005 curriculum](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/lecture-notes/cp2wsol.pdf)

### Problem 1

$\exists x . x^2 = 2$
Z = no, Q = no, R = true, C = true?

$\forall x \exists y . x^2 = y$

Z and above

$\forall y \exists x . x^2 = y$

C

$\forall x \neq 0, \exists y . x y = 1$

Q and above

$\exists x \exists y . x + 2y = 2 \ AND \ 2 x + 4y = 5$

False for all

### Problem 2

(a)

$\exists x (xxx = y)$

(b)
$\exists$x (NO-1S(x)(NO-1S(x) = y)

(c )

$\exists$x . NO-1S(x) OR NO-0S(x)

> NO-1s(x) -> not(substring(1,x)) -> NO ($\exists$ x(1y1=x) AND (NO-1S(y))) OR x=1

(e)

prefix(x, 0x) -> $\exists z (xz = 0x)$

### Problem 3

$\exists x \exists s \in$ {a, b} $E(x, s)$

$\exists x \exists y \exists z . E(x, y) E(x, z)$

$\forall y.(y = u \ OR \ y = w \ OR \ y = x) \ OR \ NOT(E(x,y))$

### Problem 4

(see Zulip discussion, also exercise 1.5.8)

### Problem 5

(a.) There are three unique people who are all in the cabal
(b.) Both Siggi and Annie cannot be in the cabal. (either could be)
(c.) if Elizabeth is in the cabal, then everyone is (so **Elizabeth is NOT**)
(d.) If Annie is in the cabal, so is Siggi. If Annie isn't, Siggi is or is not part of the cabal. -- **NOT Annie** (because of b)
(e.) if either Ben or Albert are in, then Tom is not
(f.) if Ben or Siggi are in, then Adam is not

(g.)
i. Because of (b.) and (d.) we know that Annie is not part of the cabal

ii. Because of (c.) we know that Elizabeth is not part of the cabal.

People who could be part part of the cabal are **Adam, Tom, Albert, Ben, Siggi**

**If Ben is part of the cabal, then Tom and Adam cannot be. Leaving only Albert, Ben and Siggi**

### Problem set 1, problem 2

(1) n<= 3^n/3

Proof by contradiction; let's assume (1) is false. Then there is a nonempty set C of counterexamples:

C ::= {n $\in N$ \| n > 3^n/3}

By the WOP, there will be a smallest element, c, in C, such that c > 3^c/3.

...

$(c - 1) \le 3^{\frac{c-1}{3}}$

So (c - 1) is not in the set C of counterexamples.

$((c + 1) - 1) \gt 3^{\frac{(c + 1) -1}{3}}$

$c \gt 3^{\frac{c}{3}}$

But that can't be, because the denominator of the exponent has stayed constant, which means that the RHS is exponentially greater than c, which means that C is empty.

QED

But c is part of C, then: $c > 3^{c/3}$, then
$3^{c/3} < c <= 3^{\frac{c-1}{3}}$
Then
$3^{c/3} < 3^{\frac{c-1}{3}}$
Which is:
$3^{c/3} < 3^{\frac{c-1}{3}}$


when $n \ge 4$
That means that $n = x + 4$
$x + 4 \le 3^{\frac{x + 4}{3}}$
$x + 4 \le 3^{1 + \frac{x + 1}{3}}$
$x + 4 \le 3^{1} \times 3^{\frac{x + 1}{3}}$
$\frac{x + 4}{3} \le 3^{\frac{x + 1}{3}}$

## Session 4

**Links for today:**
- [Session 4 In-Class Questions (PDF)](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/in-class-questions/MIT6_042JS15_cp4.pdf)
- [Chapter 3.1–3.5 (PDF)](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/readings/MIT6_042JS15_Session4.pdf)

**Agenda:**
- Quick intros for any new people :)
- Work through session 4 in-class questions together
- Maybe review our proofs from session 3, for those who've worked on them more since then

## Problems 1 - 4 Shared Notes/Solutions

### **Problem 1:**

Truth Tables! ┬─┬ノ( º _ ºノ)

| P | OR |(Q | AND | R)|
|---|----|---|-----|--|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |

Compare column 2 (OR) above with column 4 (AND) below

| (P | OR |Q) | AND | (P | OR | R)|
|--|--|--|--|--|--| -- | --|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |

### **Problem 2.**
- Note: [solution from 2005 assignment here (PDF)](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/lecture-notes/cp2msol.pdf)

L ::= the filesystem is locked
Q ::= new messages are queued
B ::= new messages are sent to the buffer
N ::= system is normal

1a. NOT(L) $\implies$ Q
1b. NOT(L) $\implies$ B
1c(i). NOT(L) $\implies$ N
1c(ii). NOT(L) $\implies$ N $\implies$ NOT(L)
2. NOT(Q) $\implies$ B
3. NOT(B)

This site: http://www-cs-students.stanford.edu/~csilvers/proof/node4.html seems to imply \iff is equivalence

B = F
Q = T
L = T
N = F

### **Problem 3.**
(a)
$c_0$ = b
$s_0 = a_0$ XOR $c_0$
$c_n = a_{n - 1}$ AND $c_{n - 1}$
$s_n = a_n$ XOR $c_n$
$c_{n + 1} = a_n$ AND $c_n$
$c = c_{n +1}$

(b)
$c_0$ = $a_0$ AND $b_0$
$s_0$ = $a_0$ XOR $b_0$
$c_n$ = $s_{n-1}$ AND $c_{n-1}$
$s_n$ = $c_{n-1}$ XOR $s_{n-1}$
$c$ = $c_{n+1}$

a = 11
b = 11

$c_0$ = 1 AND 1 = 1
$s_0$ = 1 XOR 1 = 0

$c_1$ = 0 AND 1 = 0
$s_1$ = 1 XOR 0 = 1

$c_2$ = 0 AND 1 = 0
$s_2$ = 0 XOR 1 = 1

n = 2
$c$ = $c_{n + 1}$ = $s_2$ AND $c_2$ = 1 AND 0 = 0
$s_2s_1s_0$ = 110

### **Problem 4.**

(discussed difference between IFF and implication)

---
# Problem Set 1

## Problem 3.

(d)

"consistent iff there is an environment in which they are all true"

"valid means always true"

$C = P_1 \ AND \ P_2 \ AND \ ... P_k$
$S = NOT(C)$
> $S = NOT(P_1 \ AND \ P_2 \ AND \ ... P_k)$

$C -> NOT(S)$ $AND$ $S -> NOT(C)$