TOC Chapter 1 Exercise

Exercises

1.	Out of a total of 140 students, 60 are wearing hats to class, 51 are wearing scarves, and 30 are wearing both hats and scarves. Of the 54 students who are wearing sweaters, 26 are wearing hats, 21 are wearing scarves, and 12 are wearing both hats and scarves. Every one wearing neither a hat nor a scarf is wearing gloves. How many students are wearing gloves? How many students not wearing a sweater are wearing hats but not scarves? How many students not wearing a sweater are wearing neither a hat nor a scarf?
2.	Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study mathematics and biology, 7 study mathematics and physics, 10 study physics and biology, and 32 do not study any of the three subjects. Find the number of students studying all three subjects. Find the number of students studying exactly one of the three subjects.
3.	At a family group meeting of 30 women, 17 are descended from George, 16 are descended from John, and 5 are not descended from George or John. How many of the 30 women are descended from both George and John?
4.	80 children went to a park where they can ride on three games namely A, B and C. It is known that 20 of them have taken all three rides, and 55 of them have taken at least two of the three rides. Each ride costs $0.50, and the total receipt of the park was $70. Determine the number of children who did not try any of the rides.
5.	Use Induction to prove the following: If an = 5an−1 − 6an−2 for n ≥ 2 and a0 = 12 and a1 = 29 then an = 5(3n) + 7(2n).
6.	Use induction to prove for each integer n ≥ 5, 2n > n2.
7.	Show that Show that Show that
8.	Show that for any integer n, (11)n+2 + (12)2n+1 is divisible by 133.
9.	For each of the following check whether ‘R’ is reflexive, symmetric, antisymmetric, transitive, an equivalence relation. R = {(a, b)|a − b is an odd positive integer}. R = {(a, b)|a = b2 where a, b ∊ I+}. Let P be the set of all people. Let R be a binary relation on P such that (a, b) is in R if a is a brother of b. Let R be a binary relation on the set of all strings of 0’s and 1’s, such that R = {(a, b)|a and b are strings that have same number of 0’s}.
10.	Let A be a set with n elements. Prove that there are 2n unary relations on A. Prove that there are 2n2 binary relations on A. How many ternary relations are there on A?
11.	Let R1 and R2 be arbitrary relations on A. Prove or Disprove the following assertions. if R1 and R2 are reflexive, then R1R2 is reflexive. if R1 and R2 are irreflexive, then R1R2 is irreflexive. if R1 and R2 are symmetric, then R1R2 is symmetric. if R1 and R2 are antisymmetric, then R1R2 is antisymmetric. if R1 and R2 are transitive, then R1R2 is transitive.
12.	Find a set A with n-elements and a relation R on A such that R1, R2, ..., Rn are all distinct. This establishes the bound
13.	Let R1 and R2 be equivalence relations on a set A. Then R1 ∩ R2 is an equivalence relation. Is R1 ∪ R2 an equivalence relation?
14.	Prove that the universal relation on any set A is an equivalence relation. What is the rank of this relation?
15.	Suppose A = {a, b, c, d} and π1 is the following partition of A: π1 = {{a, b, c}, {d}} List the ordered pairs of the equivalence relation induced by π1. Do the same for the partitions π2 = {{a}, {b}, {c}, {d}} π3 = {{a, b, c, d}}
16.	Name five situations (Games, activities, real-life problems etc.,) that can be represented by means of graphs. Explain what the vertices and the edges denote.
17.	Prove that in a group of n-people there are two who have the same number of acquaintances in the group.
18.	Let A = {ε, a}, B = {ab}. List the elements of the following sets. A2 B3 AB A+ B*
19.	Under what conditions is the length function which maps Σ* to N a bijection?
20.	Let A and B finite sets. Suppose |A| = m, |B| = n. State the relationship which must hold between ‘m’ and ‘n’ for each of the following to be true. There exists an injection from A to B. There exists an surjection from A to B. There exists an bijection from A to B.