MAT102 Lecture 18

Base Case
- Something is in a set
Constructors
- If something is in a set, then $f (something) \in$ the set.
  - Sets and recursively define other things in the set.
- If $P (x)$ is true then $P (c (x))$ is true.
  - Predicates and recursively define another predicate to be true, based on the last one.

Define a set $S \subseteq N \times N$ such that:
- $(4, 1) \in S$
- $C_{1}$ : If $(a, b) \in S$ then $(a + 3, b + 2) \in S$
- $C_{2}$ : If $(a, b) \in S$ then $(a + 4, b + 6) \in S$
- Show that if $(a, b) \in S$ then $5 ∣ a + b$
- Example:
  - Apply $C_{1}$ to $(4, 1)$
    - $(7, 3)$
    - $C_{1}$
      - $(10, 5)$
    - $C_{2}$
      - $(11, 9)$
  - Apply $C_{2}$ to $(4, 1)$
    - $(8, 7)$
    - $C_{1}$
      - $(11, 9)$
    - $C_{2}$
      - $(12, 13)$
- Base Case:
  - $(4, 1)$
- Constructors:
  - $C_{1}$ : If $(a, b) \in S$ then $(a + 3, b + 2) \in S$
  - $C_{2}$ : If $(a, b) \in S$ then $(a + 4, b + 6) \in S$
- Suppose that $(a, b) \in S$ , then $5 ∣ a + b$ . Let $(c, d) \in S$ based on the constructors ( $C_{1}$ , $C_{2}$ ) from the base case, let's show that $5 ∣ c + d$ .
  - Base Case 1:
    - $(4, 1) \to C_{1}$ : $(7, 3)$
    - $5 ∣ 7 + 3$
    - $5 ∣ 10$
    - True
  - Base Case 2:
    - $(4, 1) \to C_{2}$ : $(8, 7)$
    - $5 ∣ 8 + 7$
    - $5 ∣ 15$
    - True
  - Constructed Cases:
    - $(c, d) \in S$
    - We know that if $5 ∣ a + b ⟹ a + b = 5 k$ for some $k \in Z$ .
      - This means $c + d = 5 k$
      - $C_{1}$
        
        $c = a + 3$
        
        $d = b + 2$
        
        $(a + 3) + (b + 2) = 5 k$
        
        $a + 3 + b + 2 = 5 k$
        
        $a + b + 5 = 5 k$
        
        $a + b = 5 k - 5$
        
        $a + b = 5 (k - 1)$
        
        $k - 1$ is an integer, so we have proved that in the first case $C_{1}$ is true.
      - $C_{2}$
        
        $c = a + 4$
        
        $d = b + 6$
        
        $(a + 4) + (b + 6) = 5 k$
        
        $a + 4 + b + 6 = 5 k$
        
        $a + b + 10 = 5 k$
        
        $a + b = 5 k - 10$
        
        $a + b = 5 (k - 2)$
        
        $k - 2$ is also an integer, so this proves $C_{2}$ 's case is true.
- Solution:
  - Prove that $P (a, b)$ is true and is the base case:
  - Prove the $⟹ P (a + 3, b + 2)$ and $⟹ P (a + 4, b + 6)$
  - Base Case:
    - $5 ∣ (4 + 1)$ is true
  - Case $C_{1}$ :
    - Suppose that $(a, b) \in S$ and $5 ∣ a + b$
    - Apply $C_{1}$
      - $(a + 3, b + 2)$
      - Does $5 ∣ (a + 3 + b + 2)$
      - Yes because:
        
        $5 ∣ a + b$
        
        $5 ∣ 5$
        
        So then $5 ∣ (a + b) + 5$
  - Case $C_{2}$ :
    - Suppose that $(a, b) \in S$ and $5 ∣ a + b$
    - Apply $C_{2}$
      - $(a + 4, b + 6)$
      - Does $5 ∣ (a + 4 + b + 6)$
      - Yes:
        
        $5 ∣ a + b$
        
        $5 ∣ 4 + 6$
        
        $5 ∣ 10$
        
        So then $5 ∣ (a + b) + 10$

1
- b
  - If you go first:
    - Get both stacks to $1$ . By turns, the other player will get the stack down, then you can get the last turn.
    - Try not to get forced to $2$ .
    - If $P_{1}$ gets their turn on a case where it's $2 ∣ 2$ , they will lose if $P_{2}$ knows what to do.
  - If you go second:
    - Get both stacks to $2$ , or to $1$ . Then you get decrement by $1$ or $2$ to win.
    - Doesn't matter what the other person plays in this scenario.
    - Try to force them in a position where the stack is $1 ∣ 1$ and you're the second one to take it to $1$ .
  - Examples:
  - $P_{2}$ tries to win.
    - $5 ∣ 5$ - $P_{1} : (- 2, 0)$
    - $3 ∣ 5$ - $P_{2} : (0, - 2)$
    - $3 ∣ 3$ - $P_{1} : (- 1, 0)$
    - $2 ∣ 3$ - $P_{2} : (0, - 1)$
    - $2 ∣ 2$ - $P_{1} : (0, - 2)$
    - $2 ∣ 0$ - $P_{1} : (- 2, 0)$
    - $0 ∣ 0$
    - $P_{2}$ wins
  - Proof:
    - Case 1:
      - $P_{1}$ 's turn, it's $2 ∣ 2$ , then $P_{2}$ can decrement by $1$ until we get;
      - $P_{1}$ 's turn and it's $1 ∣ 1$
      - Then $P_{2}$ wins, because it was $P_{1}$ 's turn on the $2 ∣ 2$ case.
    - Case 2:
  - Induction
    - Claim: $P_{2}$ has a winning strategy of mimicking $P_{1}$ .
    - Proof:
      - Induct on number of coins.
      - Base Case
        
        $n = 1$
        
        $P_{1} : (- 1, 0)$
        
        $0 ∣ 1$
        
        $P_{2} : (0, - 1)$
        
        $0 ∣ 0$
        
        $P_{2}$ wins
      - Induction Hypothesis:
        
        Suppose any game of $k = 1, 2, \dots, n$ coins results in $P_{2}$ winning.
        
        Prove $P (n + 1)$ :
        
        $P_{1}$ removes $c$ coins from a pile, $P_{2}$ mimics
        
        Thus there are $k + 1 - c \leq k$ coins in each pile.
        
        By $IH$ $P_{2}$ will win.
- c
  - I don't think it changes when the pile of coins are $> 4$ .
  - In this case you can control who gets to the $2 ∣ 2$ or the $1 ∣ 1$ case first.