CS 154 Introduction to Automata and Complexity Theory Handout 5

Winter 1996  R. van Glabbeek  January 24

Solution Set 1

1. (a) T (b) F

(c) T

(d) T

(e) T

(f) T

2. Let L_{1} = (a ∪ b)∗ and L_{2} be the respective language in each part. (a) Not Equal. L_{1} forms ”ab” but L_{2} doesn’t.

(b) Not Equal. L_{1} forms the empty string but L_{2} doesn’t.

(c) Not Equal L_{1} forms ”a” but L_{2} doesn’t

(d) Equal The left half of L_{2} (i.e. a*) forms all sequences with no ”b”’s. The right half forms all

other sequences (that L_{1} can form). 3.

\begin{matrix}f = O(g) ⟺ (∃c_{1})(∃N_{1})(∀n ≥ N_{1})[f(n) ≤ c_{1} ∗ g(n)] \\ g = O(h) ⟺ (∃c_{2})(∃N_{2})(∀n ≥ N_{2})[g(n) ≤ c_{2} ∗ h(n)] \end{matrix}

combining the two sentences and noting the transitive property of ≤, we have:

(∃c_{1})(∃c_{2})(∃N_{1})(∃N_{2})(∀n)[(n ≥ N_{1} ∧ n ≥ N_{2}) ⇒ f(n) ≤ c_{1} ∗ c_{2} ∗ h(n)]

thus

(∃c_{3})(∃N_{3})(∀n ≥ N_{3})[f(n) ≤ c_{3} ∗ h(n)] where c_{3} = c_{1} ∗ c_{2} and N_{3} = max(N_{1}, N_{2})

and hence f(n) = O(h(n))

4. (Graded by David Rieber, William Toves, and Johnathan Joseph Hart) Let p be an integer greater than or equal to 2. The p-adic representation of a positive integer n is unique. Existence: For fixed, but arbitrary p ≥ 2 we prove that every natural n has a p-adic representation by induction. Let P (n) denote that the natural number n > 0 has a p-adic representation.

Base case Prove P (1): Since p^{0} = 1, the p-adic representation of the natural number 1 is 1. Inductive step Assume P (k) and show P (k + 1), (where 1 ≤ k) By our inductive hypothesis, which

states that P (k) holds, we know that k has a p-adic representation. This representation is:

a_{m}a_{m−1} … a_{1}a_{0} m ≥ 0

such that:

k = Σ_{i=0}^{m}a_{i}p^{i} where 1 ≤ a_{i} ≤ p

Either for every i = 0, …, m, a_{i} = p, or there is a smallest j, such that a_{j} < p, and a_{i} = p for i < j. In the first case:

k + 1 = Σ_{i=0}^{m+1}1 · p^{i}

thus, the p-adic representation of k + 1 is \underbrace{111 … 1}_{m+1}. In the second case:

k + 1 = Σ_{i=0}^{j−1}p^{i} + (a_{j} + 1)p^{j} + Σ_{i=j+1}^{m}a_{i}p^{i}

thus, the p-adic representation of k + 1 in this case is ma_{m−1} … a_{j+1}(a_{j} + 1)1 … 1. Thus P (k + 1) holds, and so all natural numbers n > 0 have a p-adic representation.

Since our proof assumes nothing specific about our choice of p, we can generalize to say that for all p ≥ 2, all natural numbers n > 0 have a p-adic representation.

Uniqueness: Let a_{r}a_{r−1} … a_{1}a_{0} and b_{s}b_{s−1} … b_{1}b_{0} be two representations of the same integer n. We show that they are equal. As they both represent n we have

Σ_{i=0}^{r}a_{i}p^{i} = Σ_{j=0}^{s}b_{j}p^{j}

We first show that r = s. To prove this suppose r > s. Since 1 ≤ a_{i}, b_{j} ≤ p for i = 0 … r and j = 0 … s, then

Σ_{i=0}^{r}a_{i}p^{i} ≥ Σ_{i=0}^{r}p^{i} = \frac{p^{r+1} − 1}{p − 1},

and

Σ_{j=0}^{s}b_{j}p^{j} ≤ Σ_{j=0}^{s}p^{j+1} = p\frac{p^{s+1} − 1}{p − 1}.

Now, since s < r:

Σ_{j=0}^{s}b_{j}p^{j} ≤ p\frac{p^{s+1} − 1}{p − 1} ≤ p\frac{p^{r} − 1}{p − 1} = \frac{p^{r+1} − p}{p − 1} < \frac{p^{r+1} − 1}{p − 1} ≤ Σ_{i=0}^{r}a_{i}p^{i}

which contradicts our assumption, thus r = s.

Let k be the largest integer such that a_{i} ≠ b_{i}. Then:

a_{k}p^{k} + Σ_{i=0}^{k−1}a_{i}p^{i} = b_{k}p^{k} + Σ_{i=0}^{k−1}b_{i}p^{i}

and

(a_{k} − b_{k})p^{k} = Σ_{i=0}^{k−1}(b_{i} − a_{i})p^{i}

Suppose (without loss of generality) that a_{k} > b_{k}. Then a_{k} − b_{k} ≥ 1 and

(a_{k} − b_{k})p^{k} ≥ p^{k}

On the other hand, b_{i} − a_{i} ≤ (p − 1) for i = 0 … k − 1. Thus,

Σ_{i=0}^{k−1}(b_{i} − a_{i})p^{i} ≤ Σ_{i=0}^{k−1}(p − 1)p^{i} = p^{k} − 1

but this is a contradiction. Thus, we have proved that for every positive integer n, if it has a p-adic representation, that representation is unique.

5. Solutions to Problems 5 & 6 exist only in hardcopy form. Copies are in the Theory Handout Hangout.

Extra credit problem

1. Prove that in any group of six students taking this class, there is a group of three people who are all either mutual strangers or all mutual acquaintences. You may assume that all pairs of students in this class are either mutual strangers or mutual acquaintences.

Consider any student (call her A). Every one of the other 5 students is either a friend or an acquaintance, by assumption. By the pigeon-hole principle, she should therefore have at least 3 friends or at least 3 acquaintances (otherwise it wouldn’t add up to 5). Let us assume, without loss of generality that she has at least 3 friends. Choose some 3 of them, and consider the nature of relationships between them. If there is at least one friend-friend pair between them, we are done, as the group consisting of A and these two form a threesome of mutual friends. If, on the other hand, the friends of A are all mutual acquaintances (no friend-friend pair among them) we are again done.

2. Prove that in a class of infinitely many students, either there is an infinite subset of mutual strangers or there is an infinite subset of mutual aquaintances.

This is a famous theorem known as Ramsey’s theorem. One can formulate and verify a version of this theorem within monadic second order logic of one successor (S1S) which is a decidable logic. The decision procedure for S1S is by the way obtained using regular automaton on infinite words (introduced in problem 4.10-10). Thus, one can make a computer solve this problem “easily”.

An informal proof of the theorem can take the following lines:

First color all the students pink and pick one pink student. By the pigeon hole principle this student has either infintely many acquaintances (A) or infinitely many strangers (S) among the other students. If S is infinite, then color the students in A green, put the chosen student in a bucket labeled σ. On the other hand if S is finite, then A is infinite, color the S-students green, and put the chosen student in a bucket labeled α. Continue this process transfinitely with the remaining infinite set of pink students at each step picking a pink student and partitioning the rest of according to whether they are in A or in S relative to the chosen student. In the end either the bucket labeled α or the bucket labeled σ will contain infinitely many students. The students in α will all be mutual aquaintances, and the students in σ will all be mutual strangers by the construction. □