Massachusetts Institute of Technology Handout 37 6.042J/18.062J: Mathematics for Computer Science October 23, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 7

Problem 1. Let S be the set of numbers 7, 77, 777, . . .. Prove that there is an element of S that is divisible by 1997.

Problem 2. Show that in any sequence of n integers, there is either an increasing subsequence of length \sqrt{n} or a decreasing subsequence of length \sqrt{n}.

1. Show that every DAG has a chain of length > \sqrt{n} or an antichain of size ≥ \sqrt{n}.

2. Define a DAG based on a given sequence of numbers so that chains correspond to increasing subsequences and antichains correspond to decreasing subsequences.

3. Put the above together to solve the problem.