380 ;;!. Solutions (or Hints) to Chapter-end Exercises
2.12 Suppose f(x) :::: fey). Then eLY :::: ay. So, x :::: y. Therefore, f is one-one.
f is not onto as any string with b as the first symbol cannot be written
as f(x) for any x E {a, b} *.
2.14 (a) Tree given in Fig. 2.9.
2.15 (a) Yes.
(b) 4. 5. 6 and 8
(c) L 2, 3 and 7
(d) 3 (The longest path is 1 -7 3 -7 7 -7 8)
(e) 4-5-6-8
(f) 2
(g) 6 and 7
2.16 Form a graph G whose vertices are persons. There is an edge
connecting A and B if A knows B. Apply Theorem 2.3 to graph G.
2.17 Proof is by induction on IXI. When IXI : : : : L Xis a singleton. Then
2 x :::: {0. X}. There is basis for induction. Assume !2
X
I : : : : 2 1X1 when
X has 11 - 1 ·elements. Let Y :::: {aj. a~, ... , an}
Y:::: X U {a"L where X:::: {al' a~, ., .. an-d. Then X has 11 - 1
elements. As X has 11 - 1 elements. !2 X
j :::: 2[X] by induction hypothesis.
Take any subset Y 1 of Y. Either Y I is a subset of X or Y I - {an}
is a subset of X. So each subset of Y gives rise to two subsets of X.
Thus. !2
Y
\ :::: 2!2 x l. But 12
X \ :::: i
X . Hence !2
Y
\ :::: 2[Yi. By induction the
result is true for all sets X.
2.18 Ca) When /1 :::: L 1~:::: 1(1 + 1)(1 + 2) :::: L Thus there is basis for
6
induction. Assume the result for 11 - 1. Then
n-l
: : : : I k~ -+- 11~
k=1
::::
(11 - 1)(/1 - 1 + 1)(211 - 1)
~
6
+11
[by induction hypothesis]
11(11 + 1)(2/1 + 2)
. . . .
::::
6
on slmphflCatlOn.
Thus the result is true for 11.
(cl When 11 :::: 2, lo~n - 1 :::: 9999 which is divisible by 11. Thus
there is basis for induction. Assume lO~(n-l) - 1 is divisible by 11.
Then, lO~n - 1 :::: lO~lO~(n - I) - 1 :::: 1O~[10~(n - 1) - 1] + 10~ - L As
1O~' 11-1, - 1 and 10~ - 1 are divisible by 11, 1O~" - 1 is divisible by
11. Thus the result is true for 11.