Discrete Math Homework
MATH 3310 – Meeting Twenty
Topic: ⇤
Flour and Eggs:
Recurrence Relations.
n
(n - 1) (n - 2)
Agenda items:
Pizza-Cutting Problem.
3
7
Question: n †
Optimal Answer: P : N ! N N n P(n)
n
New Question: P(n)
P(n)
P(n) P(k) k < n
Data.
n
P(n)
P(n) = P(n - 1) + n
Observation 1:
L1 ‡
L1
L2 L2
L1 L2 \ L1 6= ⇤ Observation 2:
⇤ † ‡
L1 L2 q L1 L2 L3
q L3 q L3 L2
L1 ⇤
P(n) P(k) k < n
A Subtle Point: P(n) P(n) � X
X P(n) P(n) X Theorem n � 1 P(n) = P(n - 1) + n
n - 1
n - 1 + 1 P(n) � P(n - 1) + n P(n) P(n - 1) + n
n
Calculus-type Method.
f(n) n P(n) f f(n + 1) - f(n) �f(n) k � 1 k f
�
k f(n) = �k-1f(n + 1) - �k-1f(n) f f(n)
P(n)
n
P(n) �P(n) �
2 P(n)
�
3 P(n)
�
3 P(n) P(n) �3P(n) = 0 n
P(n) = An2 + Bn + C P(n) = An2 + Bn + C A, B, C
P(0) = 1, P(1) = 2 P(2) = 4
2
4 4 2 1
1 1 1
0 0 1
3
5
2
4 A
B
C
3
5 =
2
4 4
2
1
3
5 =)
2
4 A
B
C
3
5 =
2
4 1/2
1/2
1
3
5
P(n) = 1 2 n
2 + 1 2 n + 1
Iterate the recurrence.
P(n) = P(n - 1) + n
= P(n - 2) + n - 1 + n
= P(n - 3) + n - 2 + n - 1 + n
= P(0) + 1 + 2 + · · · + n - 2 + n - 1 + n. Pn
i=1 = n(n+1)
2 P(n) = P(0) +
n(n+1) 2
= 1 + n 2
2 + n
2 .
The Calculus-Type Method May not Bear Fruit. k
k
Homework #6: Due March 1, 2019
Measuring Problem. A B c1 c2 c1 c2
N
Question:
state machine
(j1, j2) A j1 B j2 j1 j2 0 j1 c1
0 j2 c2 ! (x, y) ! (z, w) x y z w
(0, 0) ! (c1, 0) (0, 0) ! (0, c2)
(j1, j2) ! (0, j2) (j1, j2) ! (j1, 0) (j1, j2) ! (c1, j2) (j1, j2) ! (j1, c2) (j1, j2) ! (0, j1 + j2) j1 + j2 c2 (j1, j2) ! (j1 - (c2 - j2), c2) c2 j1 + j2 (j1, j2) ! (j1 + j2, 0) j1 + j2 c1 (j1, j2) ! (c1, j2 - (c1 - j1)) c1 j1 + j2
j1 j2
d | c1 d | c2 d | j1 d | j2 d | X X
An Algorithm for measuring water. N N c1 c2
Algorithm Jugs: Algorithm for Precisely Measuring Water with A and B.
One. A
Two. A B B A B
A c1 = 21 B c2 = 26 3
(x, y) x A 21 B 26 y
B A
B
(0, 0) A (21, 0) A B (0, 21) (0, 21) A (21, 21) A B (16, 26) B (16, 0) A B (0, 16) (0, 16) A (21, 16) A B (11, 26) B (11, 0) A B (0, 11)
11 = 21·3+26·(-2) A 3 B 2
12 = 13 · 4 + 20 · (-2) 12 13 20 13
4 4 c1 = 13 c2 = 20 12 B
(0, 0) A (13, 0) A B (0, 13) (0, 13) A (13, 13) A B (6, 20) B (6, 0) A B (0, 6) (0, 6) A (13, 6) A B (0, 19) (0, 19) A (13, 19) A B (12, 20) B (12, 0) A B (0, 12)
Lemma L c1 c2 c1
L = c1x1 + c2x2 x1, x2 2 Z
L = c1x1 + c2x2 = c1(x1 + mc2) + c2(x2 - mc1),
m x1 + mc2 > 0 x x1 + mc2 L = c1x + c2(x2 - mc1)
c1 c2
c1x + c2y x, y 2 Z N c1 c2 c1 c2
0 N c2 N c1 c2