An explorer is trying to reach the Holy Grail, which she believes is located in a desert shrine d days walk from the nearest oasis. In the desert heat, the explorer must drink continuously. She can carry at most 1 gallon of water, which is enough for 1 day. However, she is free to create water caches out in the desert. For example, if the shrine were 2/3 of day's walk into the desert, then she could recover

1 Sums and approximations Problem 1. Evaluate the following sums Solution. The formula for the sum of an infinite geometric series with ratio 1 /2

1 Bipartite Graphs Graphs that are 2-colorable are important enough to merit a special name; they are called bipartite graphs. Suppose that G is bipartite. Then we can color every vertex in G ei ther black or white so that adjacent vertices get different colors. Then we can put all the

1 RSA In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a highly secure cryp- tosystem(called RSa)based on number theory. Despite decades of attack, no significant weakness has been found (Well, none that you and me would know.)Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted

1 Graphs and Trees The following two definitions of a tree are equivalent Definition 1: A tree is an acyclic graph of n vertices that has n-1 edges Definition 2: A tree is a connected graph such that Vu, v E V, there is a unique path connecting u to u. In general, when we want to show the equivalence of two definitions, we must show

1 The pulverizer We saw in lecture that the greatest common divisor(GCD)of two numbers can be written as a linear combination of them. That is, no matter which pair of integers a and b we are given, there is always a pair of integer coefficients s and t such that

Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural

1 Strong Induction Recall the principle of strong induction: Principle of Strong Induction. Let(n) be a predicate. If ·P() is true,and for all n, P(O)A P(1)...A P(n) implies P(n+1), then P() is true for all n E N. As an example, let's derive the fundamental theorem of arithmetic

1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If ·P(0) is true,an for all nE N, P(n) implies P(n+1), then P(n) is true for all nE N As an example let's try to find a simple expression equal to the following sum and then use induction to prove our guess correct 1·2+2·3+3:4+…+n·(mn+1) To help find an equivalent expression, we could try evaluating the sum for some small n and(with the help of a computer) some larger n sum

1 Logic A proposition is a statement that is either true or false. Propositions can be joined by \and\, \or\, \not\, \implies\, or \if and only if\. For each of these connective, the defini- tion and notational shorthand are given in the table below. Here A and B denote arbitrary propositions