# Mat1348 Assignment Solutions

## Discrete Mathematics MAT 2348 - Fall 2017

Under construction. This web page is updated regularly. Last update: 10/12/2017**Class Time:**Mondays 16:00 - 17:30 KED B005

Wednesdays 14:30 - 16:00 KED B005

**Office Hours** : Mondays 13:30-15:00

Wednesdays 12:00-13:30

or by appointment (please email me)**Exam period office hours:**Thu. Dec. 7, 13:00-14:00

Fri. Dec. 8, 12:30-13:30

Mon. Dec. 11, 13:30-14:30

Wed. Dec. 13, 9:30-11:30

**Review/group office hours:**Tue. Dec. 12, KED B004, 14:30-16:30

**Professor:**Mateja Sajna

**Office:**585 KED, 301B

**Phone:**562-5800 ext. 3522

**E-mail:**msajna@uottawa.ca

Important: Please include MAT2348 in the subject line of every email you send me and sign your message. Otherwise your email may be deleted unread.

**Course Web Page:**http://mysite.science.uottawa.ca/msajna//MAT2348/main.html

This web page contains detailed and up-to-date information on the course, including a detailed course outline and course policies, homework assignments, handouts to download etc. You are responsible for this information. Consult this page regularly.

This web page contains detailed and up-to-date information on the course, including a detailed course outline and course policies, homework assignments, handouts to download etc. You are responsible for this information. Consult this page regularly.

**Virtual Campus:**All your grades, as well as solutions to assignments and exams, will be posted on Virtual Campus, however, I will not be using it to communicate with the students. Please check your university email account regularly and refer to this web site for current course information.

**Required Textbook:**Ralph P. Grimaldi,

*Discrete and Combinatorial Mathematics*, 5th Edition

*We'll be covering parts of Chapters 1, 3, 4, 5, 7, 8, 9, 10, and 11. Additional handouts will be posted on this website.*

Course Outline: Quick review of sets, functions, relations, induction, basic counting techniques. An in-depth treatment of recurrence relations, generating functions, and principle of inclusion-exclusion. Aspects of graph theory.

Prerequisites: MAT 1341, (MAT 1348 or MAT 1325 or MAT 1362 or MAT 2362 or MAT 2141).

**Coursework Evaluation:**The final grade will be calculated as follows:

5 homework assignments : 20%

Midterm exam: 25%

Final exam: 55%

*A mark of 40% or higher on the final exam is required for a pass in the course. In the exceptional case that the student missed a midterm exam for a valid reason, the weight of the final exam will increase to 80%.*

**Homework Assignments:** There will be 5 assignments, in total worth 20% of the final grade. The lowest assignment mark will be replaced by the final exam mark if this is to the student's advantage. Assignments are due on the following dates: 25 Sep., 11 Oct., 8 and 22 Nov., and 6 Dec. Assignments are to be submitted by 3:00pm in the appropriate submission box in the Department of Mathematics and Statistics. Links to the assignments will appear in the table below.

**Course policies:** Please carefully read the following policies posted on the course web site. You are responsible for this information.

Students are permitted, and indeed encouraged, to discuss homework problems with others, but are not permitted to help each other write the final solution. Once you understand a solution, you must write it out entirely by yourself. For each question, any help from other people must be clearly acknowledged, as well as any sources used (e.g. textbooks, websites, videos), if that source contains a solution to a very similar question, or a new method or idea that you used that was not in the course materials. Failure to follow these rules constitutes plagiarism (academic fraud). Note that if one student copies from the other, both students have committed academic fraud. If I believe plagiarism has occurred, the students will receive:

- a mark of 0 for the current assignment if this is the first offence;
- a mark of 0 for the whole assignment component of the course if this is the second offence.

**Important dates:**** **

- 6 Sep. - first class
- 9 Oct. - Thanksgiving (no class)
- 23-27 Oct. - Reading Break
- 30 Oct. - Midterm Exam
- 17 Nov. - last day to withdraw
- 6 Dec. - last class (Monday schedule)
- 8-21 Dec.- final exam period

Interesting Links (more to come)

**What's going on in class these days?**

Date | Topics covered | Reading material (sections from Grimaldi or GTN) | Recommended exercises: G - Grimaldi SE - Supplemental Exercises | Assignments |

6 Sep | Introduction to the course. Review topics: set concepts and set operations Review of set concepts and operations (revised 6/9) | 3.1-3.2 | 3.1: 1-6, 15, 17, 18, 273.2: 1-7, 14 | |

11 Sep | More on sets (Venn diagrams, using set identities, generalized union and intersection); functions Sets (review + generalized union and intersection) Functions + bijective proofs (updated 11/9) | 3.2, 5.2, 5.3 | 3.2: 8, 10, 11, 13, 15-195.2: 2, 7-13, 15-165.3: 1-3SE1: allSE2:1, 3-7, 10 | |

13 Sep | More on functions, bijective proofs, basic counting Product and Sum Rules | 5.2-5.3, 1.1 | Exercises on bijective proofs: 1a-dSE5: 1-3, 10 | |

18 Sep | Basic counting (more examples), permutations (with repetition) | 1.1, 1.2 | 1.2: 4-6, 9, 15, 21-23, 25, 27, 31, 34, 35 (also suitable: 1-27, 30-38)SE5: 1-3, 4a-d, 5, 10-12SE7: 1, 11, 12 | Assignment 1 is posted |

20 Sep | Combinations, counting strings (of given weight) On overcounting | 1.3 | 1.3: 3-5, 7, 11, 13, 15, 19, 21SE7: 1, 3, 4, 10, 12 (also 1-13) | |

25 Sep | Binomial Theorem, Pascal's Identity (combinatorial proof), Multinomial Theorem, combinations with repetition | 1.3 | 1.3: 22-23, 25-32SE7: 3, 5Exercises on bijective proofs: 1e, 2abe | Assignment 1 is due |

27 Sep | Combinations with repetition (cont'd), the Pigeonhole Principle | 1.4, 5.5 | 1.4: 1-10, 12-13, 15-18, 23, 27-28ab5.5: 1-16, 19-24SE6: 1-12 | |

2 Oct | Mathematical Induction Mathematical Induction | 4.1 | 4.1: 1-3, 7-9, 12-19SE8: 1-5, 7-10, 14 | |

4 Oct | Strong Induction, properties of relations Relations | 4.1-4.2, 7.1 | 4.1: 23, 274.2: 6, 7, 10-15, 19SE8: 6, 11-137.1: 1-3, 5-9, 13 | Assignment 2 is posted |

9 Oct | Thanksgiving - no class | |||

11 Oct | Counting relations; equivalence relations and partitions | 7.1, 7.4 | 7.1: 10, 14, 16, 177.4: 1,3-5, 8-10SE3: 1-9SE4: 1-11 | Assignment 2 is due |

16 Oct | Equivalence relations and partitions (cont'd) | 7.4, 14.3 (congruences only) | 14.3: 1-9, 18-197.4: 2, 6-17 | |

18 Oct | Principle of Inclusion-Exclusion (PIE) Notes on PIE | 8.1, 5.3 | 8.1: 5, 6, 8, 10-13, 16-17, 20-235.3: 4, 5, 7, 8, 10 | |

23-27 Oct | Reading Break | |||

30 Oct | Midterm Exam (up to and including equivalence relations; no PIE)A list of practice questions Midterm Exam front page | |||

1 Nov | More on counting surjective functions, intro to generating functions Generating Functions | 5.3, 9.1, 9.2 | 5.3: 8, 109.1: 1-5 | Assignment 3 is posted |

6 Nov | Techniques for generating functions | 9.2 | ||

8 Nov | Generating functions - examples (including composition and partition of integers) | 9.2-9.3 | 9.2: 1-12, 15-18, 31-339.3: 1-8 | Assignment 3 is due |

13 Nov | Intro to recurrence relations; first-order linear RRs with constant coefficients, back substitution; second-order linear homogeneous RRs with constant coefficients, the method of characteristic roots The Method of Characteristic Roots | 10.1-10.3 | 10.1: 1-610.2: 110.3: 1, 4 | |

15 Nov | The method of characteristic roots (cont'd), setting up recurrence relations, solving non-homogeneous RRs Setting up a particular solution in a non-homogeneous RR | 10.1-10.3 | 10.2: 2-6, 9, 12-16, 20-25, 30, 32 | Assignment 4 is posted |

20 Nov | Solving non-homogeneous RRs (cont'd), solving RRs using generating functions Notes on recurrence relations | 10.3-10.4 | 10.3: 3, 5, 6, 8, 10, 12, 1410.4: 1 | |

22 Nov | Intro to graphs, degrees, Handshaking Lemma, special graphs Graph Theory Notes (GTN) | GTN 1.1-2.2 | GTN 1.4: allGTN 2.6: 1-3, 6, 9, 10 | Assignment 4 is due |

27 Nov | Special graphs (cont'd), subgraphs, bipartite graphs, isomorphism | GTN 2.2-2.4, 3.2 | GTN 2.6: 4, 5, 7, 8, 11-13 | Assignment 5 is posted (best to wait until Nov. 29 before working on Q3 and Q4) |

29 Nov | Graph isomorphism (cont'd), walks, connectivity | GTN 3.2, 4.1-4.2 | GTN 3.3: 8, 9, 11, 12GTN 4.4: 2-5GTN 2.6: 14-15 | |

4 Dec | Connectivity, Euler tours and trails, distance, complements | GTN 4.2-4.3, 2.5, 5 | GTN 2.6: 14, 15GTN 3.3: 12GTN 4.4: 6-7GTN 5.1: 1-7SE 9: 1-15 | |

6 Dec | Last class - Monday scheduleTentative: Planar graphs (optional material) | GTN 6 (optional material) | Assignment 5 is due | |

13 Dec | Final exam at 7pm in DMS 1150Emphasis on the second half of the course | |||

Review Questions Review Sheet A longer list of review questions |

MAT 1348/1748 SOLUTIONS TO SUPPLEMENTAL EXERCISES ˇ by J. Khoury, L. Dumitrescu, and M. Sajna 1 Propositional Logic 1. p T T F F q T F T F P1 T T T F P2 T F F T P3 T F T T P4 F T F T P5 F F T F P6 F F F T (a) From the table, the corresponding DNFs are P1 ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) P2 ≡ (p ∧ q) ∨ (¬p ∧ ¬q) P3 ≡ (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q) P4 ≡ (p ∧ ¬q) ∨ (¬p ∧ ¬q) P5 ≡ ¬p ∧ q P6 ≡ ¬p ∧ ¬q (b) Analyzing each compound proposition and then using equivalence laws we have P1 ≡ p ∨ q ≡ ¬(¬p ∧ ¬q) P2 ≡ p ↔ q ≡ (p → q) ∧ (q → p) ≡ (¬p ∨ q) ∧ (¬q ∨ p) ≡ ¬(p ∧ ¬q) ∧ ¬(q ∧ ¬p) P3 ≡ p → q ≡ ¬p ∨ q ≡ ¬(p ∧ ¬q) P4 ≡ ¬q P5 ≡ ¬p ∧ q P6 ≡ ¬p ∧ ¬q. (c) Using the form of each compound proposition and then equivalence laws, P1 ≡ p ∨ q ≡ ¬¬p ∨ q ≡ ¬p → q P2 ≡ p ↔ q ≡ (p → q) ∧ (q → p) ≡ ¬¬(p → q) ∧ (q → p) ≡ ¬(¬(p → q) ∨ ¬(q → p)) ≡ ¬((p → q) → ¬(q → p)) P3 ≡ p → q P4 ≡ ¬q P5 ≡ ¬p ∧ q ≡ ¬(p ∨ ¬q) ≡ ¬(q → p) P6 ≡ ¬(¬p → q). 1 2. (a) p T T F F q T F T F p⊕q F T T F p T T T (b) The truth table T F F F F q T T F F T T F F r T F T F T F T F p⊕q F F T T T T F F (p ⊕ q) ⊕ r T F F T F T T F q⊕r F T T F F T T F p ⊕ (q ⊕ r) T F F T F T T F Since the ﬁfth and the seventh columns are the same, we conclude that the corresponding propositions, (p ⊕ q) ⊕ r and p ⊕ (q ⊕ r), are equivalent. (c) p T T F F q T F T F p⊕q F T T F p↔q T F F T ¬(p ↔ q) F T T F Since the third and the ﬁfth columns are the same, we conclude that p ⊕ q ≡ ¬(p ↔ q). 3. Using equivalence laws, ¬(a → b) → c ≡ ¬(¬(a → b)) ∨ c ≡ (a → b) ∨ c ≡ (¬a ∨ b) ∨ c. 4. (a) Truth tables. (i) Denote P1 = (x ∨ y) ∧ (¬x ∨ z) and note that the compound proposition ((x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)) → z can be written as (P1 ∧ (y → z)) → z. x T T T T F F F F y T T F F T T F F z T F T F T F T F x∨y T T T T T T F F ¬x ∨ z T F T F T T T T P1 T F T F T T F F y→z T F T F T F T T 2 P1 ∧ (y → z) (P1 ∧ (y T F T F T F F F → z)) → z T T T T T T T T Hence, ((x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)) → z is a tautology. (ii) Denote P2 = (x → y) ∧ (x → z) and note that the proposition (x → (y ∨ z)) → ((x → y) ∧ (x → z)) can be written as (x → (y ∨ z)) → P2 . x T T T T F F F F y T T F F T T F F z T F T F T F T F y∨z T T T F T T T F x → (y ∨ z) x → y T T T T T F F F T T T T T T T T x→z T F T F T T T T P2 T F F F T T T T (x → (y ∨ z)) → P2 T F F T T T T T Hence, (x → (y ∨ z)) → ((x → y) ∧ (x → z)) is not a tautology. If either (x is T, y is T and z is F) or (x is T, y is F and z is T), then the proposition (x → (y ∨ z)) → ((x → y) ∧ (x → z)) is F. (b) Truth trees. (i) Consider the negation of the given compound proposition, ¬(((x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)) → z) ≡ ¬(¬((x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)) ∨ z), and apply the truth trees method. ¬(¬((x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)) ∨ z)X (x ∨ y) ∧ (¬x ∨ z) ∧ (y → z)X ¬z x ∨ yX ¬x ∨ zX y → zX x ¬x × y z × ¬x ¬y × z × z × Since all the paths are inactive, we conclude that the negation proposition considered is a contradiction. This implies that the initial given compound proposition is a tautology. (ii) Consider the negation of the given compound proposition is ¬((x → (y ∨ z)) → ((x → y) ∧ (x → z))), and apply the method of truth trees. 3 ¬((x → (y ∨ z)) → ((x → y) ∧ (x → z)))X x → (y ∨ z)X ¬((x → y) ∧ (x → z))X ¬x y ∨ zX ¬(x → y)X ¬(x → z)X ¬(x → y)X ¬(x → z)X x ¬y × x ¬z × x ¬y x ¬z y z × y z × Since there are complete active paths, we conclude that the negation proposition is not a contradiction and therefore, the initial proposition is not a tautology. The active paths provide the two counterexamples, i.e. truth values of x, y and z for which the x y z proposition (x → (y ∨ z)) → ((x → y) ∧ (x → z)) is false: T T F . T F T 5. The argument can be written as Hypothesis Hypothesis Hypothesis Hypothesis (P → J) → (¬C → M ) ¬J → ¬P ¬J ∧ E → ¬C ¬M → P 1: 2: 3: 4: Conclusion: ¬(J ∧ ¬P ) → C Using truth tables or truth trees the above argument can be shown to be invalid. The P M J E C following is a counterexample. If , then each hypothesis is true F T F T F whereas the conclusion is false. 6. The argument can be written as Hypothesis Hypothesis Hypothesis Hypothesis 1: 2: 3: 4: B → (D → S) ¬D → P (D ∨ S) → B P → (¬D ∧ ¬S) Conclusion: B ∧ D 4 Using truth tables or truth trees the above argument can be shown to be invalid. B D P S The following is a counterexample. If , then each hypothesis is true F F T F whereas the conclusion is false. 7. For each compound proposition, we construct its truth table and also ﬁnd its DNF by algebraic manipulations. For the truth trees method - see other ﬁle. (i) A T T F F B T F T F A→B F F T T B→A T T F T (A → B) → (B → A) T T F T Hence, a DNF for (A → B) → (B → A) is (A ∧ B) ∨ (A ∧ ¬B) ∨ (¬A ∧ ¬B). Algebraically, (A → B) → (B → A) ≡ ¬(A → B) ∨ (B → A) ≡ ¬(¬A ∨ B) ∨ (¬B ∨ A) ≡ (A ∧ ¬B) ∨ ¬B ∨ A. Apply the truth trees method. (A → B) → (B → A)X ¬(A → B)X B → AX ¬B A A ¬B Therefore, a DNF of the compound proposition (A → B) → (B → A) is (A ∧ ¬B) ∨ ¬B ∨ A. (ii) P T T T T F F F F Q T T F F T T F F R T F T F T F T F P →Q R∨Q T T T T F T F F T T T T T T T F P → (R ∨ Q) T T T F T T T T (P → Q) ↔ (P → (R ∨ Q)) T T F T T T T T Then, a DNF for (P → Q) ↔ (P → R ∨ Q) is (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ ¬R) ∨ (¬P ∧ ¬Q ∧ R) ∨ (¬P ∧ ¬Q ∧ ¬R). 5 Algebraically, (P → Q) ↔ (P → R ∨ Q) ≡ ((P → Q) ∧ (P → R ∨ Q)) ∨ (¬(P → Q) ∧ ¬(P → R ∨ Q)) ≡ ((¬P ∨ Q) ∧ (¬P ∨ (R ∨ Q))) ∨ (¬(¬P ∨ Q) ∧ ¬(¬P ∨ (R ∨ Q))) ≡ ((¬P ∨ Q) ∧ (¬P ∨ R ∨ Q)) ∨ ((P ∧ ¬Q) ∧ (P ∧ ¬R ∧ ¬Q)) ≡ ((¬P ∨ Q) ∧ ((¬P ∨ Q) ∨ R)) ∨ ((P ∧ ¬Q) ∧ ((P ∧ ¬Q) ∧ ¬R)) ≡ ((¬P ∨ Q) ∧ ((¬P ∨ Q) ∨ R)) ∨ ((P ∧ ¬Q) ∧ ((P ∧ ¬Q) ∧ ¬R)) ≡ (¬P ∨ Q) ∨ ((P ∧ ¬Q) ∧ ¬R) ≡ ¬P ∨ Q ∨ (P ∧ ¬Q ∧ ¬R). Apply the truth tree method. (P → Q) ↔ (P → R ∨ Q)X P → QX P → R ∨ QX ¬P ¬P ¬(P → Q)X ¬(P → R ∨ Q)X P ¬Q Q R ∨ QX ¬P R Q R ∨ QX R Q P ¬(R ∨ Q)X ¬R ¬Q It follows that a DNF of the compound proposition (P → Q) ↔ (P → R ∨ Q) is ¬P ∨ (¬P ∧ R) ∨ (¬P ∧ Q) ∨ (Q ∧ R) ∨ Q ∨ (P ∧ ¬R ∧ ¬Q). (iii) Let P denote the proposition ¬A → (B → (A → (B ∧ C))). A T T T T F F F F B T T F F T T F F C T F T F T F T F B∧C T F F F T F F F A → (B ∧ C) T F F F T T T T B → (A → (B ∧ C)) T F T T T T T T Since P is a tautology, a DNF of it is T. 6 P T T T T T T T T Algebraically, ¬A → (B → (A → (B ∧ C))) ≡ ¬¬A ∨ (B → (A → (B ∧ C))) ≡ A ∨ (¬B ∨ (A → (B ∧ C))) ≡ A ∨ (¬B ∨ (¬A ∨ (B ∧ C))) ≡ A ∨ ¬B ∨ ¬A ∨ (B ∧ C) ≡ T. Apply the truth tree method. ¬A → (B → (A → (B ∧ C)))X A B → (A → (B ∧ C))X ¬B A → (B ∧ C)X ¬A B ∧ CX B C It follows that a DNF of ¬A → (B → (A → (B∧C))) is A∨¬B∨¬A∨(B∧C) ≡ T. 8. From the truth table, the compound proposition F is T only in the following cases. x y T T T F F F z T F T F T T T Hence, a DNF for F is (x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z). 2 Knights and Knaves Unless otherwise stated, the following propositional variables are used: a: “Person A is a knight.” b: “Person B is a knight.” c: “Person C is a knight.” 1. A says ¬a ∧ ¬b ∧ ¬c, and B says (¬a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c). For a and A’s statement, as well as b and B’s statement to be logically equivalent, the only possibility is that A is a knave and C is a knight, while B can be either. 2. See the handout A Method of Solving Knights-And-Knaves Questions. 3. A says ¬b, and B says a ↔ c. For a and A’s statement, as well as b and B’s statement to be logically equivalent, the only possibility is that C is a knave, and A and B are of opposite types. 7 4. A says b ↔ c, and C says either a ↔ b or ¬(a ↔ b). A truth table shows that a and A’s statement, as well as c and C statement, can be simultaneously logically equivalent only in the ﬁrst case, that is, if C says a ↔ b. In other words, C answers yes. 5. See the handout A Method of Solving Knights-And-Knaves Questions. 6. Let h be the proposition “A eats his hat.” Then A says a → h. For a and A’s statement to have the same truth value, we must have a and h both true, that is, A eats his hat. 7. A says a → T. For a and A’s statement to have the same truth value, a must be true. 8. A says a → F. For a and A’s statement can not have the same truth value; A can not be an Islander. 9. See the handout A Method of Solving Knights-And-Knaves Questions. 10. Let x be the proposition “X is innocent,” and y be the proposition “Y is innocent.” Then A says ¬x → ¬y and B says x ⊕ ¬y. Assuming A and B are of distinct types, proposition a and A’s statement, as well as proposition b and B’s statement, will be simultaneously equivalent precisely when a and x are true, and b and y are false. Hence A and B need not be of the same type. 11. A says b and B says a → c. This is possible only when A, B, C are all knights. 12. Let b be the proposition “I love Betty,” and j be the proposition “I love Jane.” It is given that b ∨ j and b → j are both true propositions. From a truth table we see that j must be true, while b can be either. 13. The speaker makes the statement (b → j) → b. Assuming this is true, b must be true, while j can be either. 14. Let l be the proposition “I love Linda,” and k be the proposition “I love Kathy.” The speaker (say A) says l as well as l → k. For a and his two statements to all be logically equivalent, the propositions a, l, k must all be true. That is, the speaker is a knight. 15. Let g be the proposition “There is gold on the island.” Then A says a ↔ g. This is equivalent to a if and only if g is true and a is either. Hence there is gold on the island. 16. Now A says ¬(a ↔ g). This is equivalent to a if and only if g is false and a is either. Hence there is no gold on the island. 17. Let m be the proposition “This is the island of Maya.” Then A said b ∧ m and B said ¬a ∧ m. Since a must be logically equivalent to A’s statement, and at the same time, b logically equivalent to B’s statement, we ﬁnd that a, b, m must all be false. Thus it is not Maya. 18. Now A and B both say ¬a ∧ ¬b ∧ m. As above, we ﬁnd that a, b, m must all be false. Thus it is not Maya. 8 19. Now A and B both say ¬(a ∧ b) ∧ m. As above, we ﬁnd that a, b, m must all be false. Thus it is not Maya. 20. Omitted (question unclear). 3 Proofs 1. The statement is equivalent with the following conditional: ”If r is a rational number and x is an irrational number, then r + x is an irrational number.” Let p : ”r is a rational number and x is an irrational number” q : ”r + x is an irrational number”. We need to prove p → q. To construct a proof by contradiction we assume that the negation, ¬(p → q) is true. Note that ¬(p → q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q. Hence, we assume p is true and ¬q is true. Since p is true, r and r + x are rational numbers. However, the diﬀerence between two rational numbers is always rational. Hence, (r + x) − r is a rational number (or x is a rational number). This statement gives a contradiction because p is true (x is irrational). Therefore, ¬(p → q) is false and hence p → q is true. √ 2. Deﬁne the propositional variable p : ” 3 3 is irrational”. To show p is true we construct a proof by contradiction. Assume ¬p is true. Then, there exist integers m and n (that have only 1 as a common √ m 3 divisor), with n ̸= 0 such that 3 = . This implies that m3 = 3n3 from where it n follows that 3 is a divisor of m3 . Hence, 3 is a divisor of m: there exists an integer k such that m = 3k. We have 27k 3 = 3n3 , or 9k 3 = n3 . Then, 3 is a divisor of n3 and so 3 is a divisor of n. It follows that 3 is a divisor of m and n which gives a contradiction with the fact that m and n have only 1 as a common divisor. Therefore, p is true. 3. Note that • max(x, y) = x, when x ≥ y and max(x, y) = y, when y > x • min(x, y) = x, when x ≤ y and max(x, y) = y, when y < x. Hence, we need to consider two cases x < y and x ≥ y. Deﬁne the propositional variables 9 p1 : ”x < y” p2 : ”x ≥ y” q : max(x, y) + min(x, y) = x + y. We need to prove that q is true in each of the two cases (note that the two cases cover all possible situations). Hence, we prove: p1 → q and p2 → q. Case (i). Assume p1 is true. Then, max(x, y) = y and min(x, y) = x. This implies that q is true. Case (ii). Assume p2 is true. Then, max(x, y) = x and min(x, y) = y. This implies that q is true. 4. We construct a proof by cases. Deﬁne the propositional variables p1 : ”aa is rational” p2 : ”aa is irrational”. Case (i). Assume p1 is true, i.e. aa is rational. Then the statement: ”at least one of the numbers aa and (aa )a is rational” is true. √ √2 √ √ 2 Case (ii). Assume that p2 is true, i.e. aa is irrational. Note that ( 2 ) 2 = 2 = 2 is rational. Hence, the statement: ”at least one of the numbers aa and (aa )a is rational” is true. 5. We construct a proof by contradiction. Assume that the statement is not true, i.e. each number a1 , a2 , ..., an is smaller than the average. Denote this average by a1 + . . . an m= . Hence, we assume that a1 < m and a2 < m, . . . , and an < m. n a1 + . . . an It follows that a1 + . . . an < m + . . . + m = n · m. This implies that < m, n which means m < m. This is a contradiction. Therefore, at least one number must be grater or equal than the average. 6. Let m and n (with m < n) be two distinct rational numbers. To construct a proof by contradiction, we consider the negation of the given proposition and assume it is true. This means we assume that between m and n there is a ﬁnite number (p) of distinct rational numbers q1 , . . . , qp . m + q1 m + q1 . Clearly, this is a rational number and m < < q1 . Consider the number 2 2 Hence, we found another distinct rational that is between m and n (and the procedure can be repeated). This contradicts the fact that we assumed there were only p distinct rationals between m and n. 7. Deﬁne the propositional variables p : ”0 < a < 1” q : ”a > a2 ”. We need to prove that p → q. Remember that the implication is equivalent to ¬q → ¬p. To construct an indirect proof, we assume that ¬q is true and prove that ¬p is true. 10 If ¬q is true then a ≤ a2 . This implies that a2 − a ≥ 0, or a(a − 1) ≥ 0. The solution of the inequality is (−∞, 0] ∪ [1, ∞). Hence, ¬p is true. 8. Deﬁne the propositional variables p : ”n5 + 7 is even” q : ”n is odd”. To prove p → q using an indirect proof, we assume ¬q is true and show that ¬p is true. If ¬q is true, then n is even: there exists an integer k such that n = 2k. Hence, n5 + 7 = (2k)5 + 7 = 32k 5 + 7 = 2(16k 5 + 3) + 1. If we denote by m = 16k 5 + 3, we can write n5 + 7 = 2m + 1, with m an integer. Therefore, n5 + 7 is odd, and consequently, ¬p is true. 9. Note that |x| = x, when x ≥ 0 and |x| = −x, when x < 0. We have −|x| ≤ x ≤ |x| and similarly, −|y| ≤ y ≤ |y|. These imply −|x| − |y| ≤ x + y ≤ |x| + |y|. (1) We consider two cases corresponding to the sign of the sum x + y. Note that these cases cover all possible situations. Deﬁne the propositional variables p1 : ”x + y ≥ 0” p2 : ”x + y < 0” q : ”|x + y| ≤ |x| + |y|”. To prove that q is true, we use a proof by cases and show that p1 → q and p2 → q. Case (i). Assume p1 is true, x + y ≥ 0. Then |x + y| = x + y which together with the right hand side of (1) implies that q is true. Case (ii). Assume p2 is true, x + y < 0. Then |x + y| = −(x + y) which together with the left hand side of (1) implies that q is true. 10. Deﬁne the propositional variables p : 3 divides n2 q : 3 divides n. We need to prove that p → q. We use the method of contradiction: we assume that the negation ¬(p → q) is true. Since ¬(p → q) ≡ p ∧ ¬q we assume p is true and ¬q is true. This implies that 3 is not a divisor of n. Hence, there exists an integer m such that n = 3m + 1 or n = 3m + 2. We continue using the method of proof by cases. Case (i). Assume n = 3m + 1 is true. Then n2 = 9m2 + 6m + 1 = 3(3m2 + 2m) + 1 = 3k + 1, with k = 3m2 + 2m - integer. This gives a contradiction with the fact that p is true (3 divides n2 ). Case (ii). Assume n = 3m+2 is true. Then n2 = 9m2 +12m+4 = 3(3m2 +4m+1)+1 = 3l + 1, with l = 3m2 + 4m + 1 - integer. This gives a contradiction with the fact that p is true. Since each case leads to a contradiction we conclude that ¬(p → q) is false (or p → q is true). 11 11. The statement of the theorem is of type p → q, where p : ”x2 does not divide a2 + b2 ” q : ”x does not divide a or x does not divide b”. To construct an indirect proof, we assume that ¬q is true: x divides a and x divides b. We need to prove that ¬p is true: ”x2 divides a2 + b2 . Since x divides a and x divides b, there exist integers k and l such that a = kx and b = lx. It follows that a2 + b2 = k 2 x2 + l2 x2 = (k 2 + l2 )x2 , where (k 2 + l2 ) is an integer. This proves that x2 divides a2 + b2 . 12. Deﬁne p : ”x3 + 3x + 5 = 0 has no rational roots”. The proof can be done by contradiction and then use a proof by cases. Assume the ¬p is true, i.e. the equation x3 + 3x + 5 = 0 has at least one rational root. m Denote it by r = , where m and n are integers, n ̸= 0 and m and n have no common n divisors other than 1. Then, the initial cubic equation can be written as m3 + 3mn2 + 5n3 = 0. (2) For the rest of the proof we consider 4 cases, corresponding to the parity of m and n. Deﬁne the propositional variables p1 : ”m and n are both even” p2 : ”m is even and n is odd” p3 : ”m is odd and n is even” p4 : ”m and n are both odd”. Note that the 4 cases cover all possible situations. To prove that ¬p leads to a contradiction, we prove that each case gives a contradiction. Case (i). Assume p1 is true. This implies that 2 is a divisor of m and also 2 is a divisor of n. This is a contradiction with the fact that m and n have no other common divisor but 1. Case (ii). Assume p2 is true. Since n is odd, 5n3 is odd. Since m is even, it follows that m3 and 3mn2 are even and therefore, their sum is even. Hence, the left hand side of (2) is odd. This is a contradiction since 0 is even. Case (iii). Assume p3 is true. Since m is odd, m3 is odd. Since n is even, it follows that 3mn2 , 5n3 are even and therefore their sum is even. These imply that the left hand side of (2) is odd. This is a contradiction since 0 is even. Case (iv). Assume p4 is true. Then, each term of the sum appearing at the left hand side of (2) is odd. It follows that the sum is odd which contradicts the fact that 0 is even. Therefore, ¬p is false (and p is true). 12 4 Sets 1. (a) A ∩ B = {1, 3, 4} (b) A ∪ B = {1, 2, 3, 4, 5, 6, 9} (c) A − B = {2, 5} (d) B − A = {6, 9} (e) A ⊕ B = (A − B) ∪ (B − A) = {2, 5, 6, 9} (f) (A ⊕ B) ∩ A = {2, 5} (g) (A ⊕ B) ∪ B = {1, 2, 3, 4, 5, 6, 9} 2. (a) ∅ ⊆ A is true (b) ∅ ∈ A is true (c) {∅} ∈ A is true (d) {∅} ⊆ A is true (e) {∅, {∅}} ∈ A is true (f) {{∅, {∅}}} ∈ A is false (g) {{∅}} ∈ A is false (h) {{∅}} ⊆ A is true (i) {{∅}, {∅, {∅}}} ⊆ A is true (j) {∅, {∅}, {{{∅}}}} ⊆ A is false (k) {∅, {{∅}}} ∈ P(A) is false (l) {{{{∅}}}} ⊆ P(A) is false 3. (a) (i) |A| = 3, P(A) = {∅, {a}, {b}, {{a, b}}, {a, b}, {a, {a, b}}, {b, {a, b}}, {a, b, {a, b}}}, |P(A)| = 23 = 8 (b) (ii) |B| = 2, P(B) = {∅, {∅}, {{∅}}, {∅, {∅}}} and |P(B)| = 22 = 4 4. To prove that B = C, we need to show B ⊆ C and C ⊆ B. Proof B ⊆ C. Let x ∈ B. Remember that A ⊕ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B). There are two cases. Case 1. Assume x ∈ A. Since x ∈ B, it follows that x ∈ A ∩ B and hence, x ∈ / A ⊕ B. Since A ⊕ B = A ⊕ C, we obtain x ∈ / A ⊕ C and hence, it follows that x ∈ / A − C and x∈ / C − A. From x ∈ / C − A and x ∈ A, we obtain x ∈ A ∩ C. This concludes the proof of x ∈ C. Case 2. Assume x ∈ / A. Since x ∈ B, this implies x ∈ B − A and hence x ∈ A ⊕ B. From the last relation it follows that x ∈ A ⊕ C and hence x ∈ (A − C) ∪ (C − A). 13 Therefore, we have x ∈ (A − C) or x ∈ (C − A) and since x ∈ / A we conclude that x ∈ C − A and so x ∈ C. Proof C ⊆ B follows similarly if we replace B by C in the previous proof. 5. (a) (A − B) ∩ B = = = = (A ∩ B) ∩ B (A ∪ B) ∩ B (A ∩ B) ∪ (B ∩ B) (A ∩ B) ∪ ∅ = (A ∩ B) = (A − B). (b) (A − B) ∩ C = (A ∩ B) ∩ C = (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) (c) (A − C) − (B − C) = (A ∩ C) ∩ (B ∩ C) = (A ∩ C) ∩ (B ∪ C) = (A ∩ B ∩ C) ∪ (A ∩ C ∩ C) = ((A − B) ∩ C) ∩ ∅ = (A − B) − C (d) A ∩ (B − A) = A ∩ (B ∩ A) = A∩B∩A = ∅ (e) (B − A) ∪ (C − A) = (B ∩ A) ∪ (C ∩ A) = (B ∪ C) ∩ A = (B ∪ C) − A 6. To prove that the two sets are equal, we ﬁrst prove that A×(B∩C) ⊆ (A×B)∩(A×C). Let (x, y) ∈ A × (B ∩ C). Then x ∈ A and y ∈ B ∩ C. Since y ∈ B ∩ C, it follows that y ∈ B and y ∈ C. Therefore, (x, y) ∈ A × B and (x, y) ∈ A × C. These imply (x, y) ∈ (A × B) ∩ (A × C). A similar argument can be used to prove (A × B) ∩ (A × C) ⊆ A × (B ∩ C). 14 7. (a) [−3, 6] ∩ (−2, 7] = (−2, 6] (b) (−5, 7] ∩ Z = {−4, −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, 7} 8. We construct proof by contradiction. Assume that there exist sets A ⊆ N and B ⊆ N such that A × B = {(0, 0), (1, 1)}. It follows that (0, 0) ∈ A × B and (1, 1) ∈ A × B. Hence, {0, 1} ⊆ A and {0, 1} ⊆ B. Take x = 0 and y = 1. We know that x ∈ A and y ∈ B. However, (x, y) = (0, 1) ∈ / A × B which is a contradiction. 9. The left hand side of the set identity is (A − B) − C = (A ∩ B) ∩ C = A ∩ (B ∩ C). The right hand side is A − (B − C) = A ∩ (B − C) = A ∩ (B − C) = A ∩ (B ∩ C) = A ∩ (B ∪ C). In general, the identity is not true. The following is a counterexample. Let U = {1, 2, 3, 4}, A = {4}, B = {1, 2, 3, 4} and C = {3, 4}. Then, A − B = ∅ and so (A − B) − C = ∅. However, B − C = {1, 2} and so A − (B − C) = {4}. 10. We have |A ∪ B| = |A| + |B| − |A ∩ B| = 6 + 8 − 3 = 11. Hence, |P(A ∪ B)| = 211 . 11. (a) The statement is false since A∩B = ∅ implies that they have no common elements. E.g. Take A = {1} and B = {2}. Here, A ∩ B = ∅, however, A ̸= B. (b) The statement is false since A−B = ∅ implies that A∩B = ∅. E.g. Take A = {1} and B = {1, 2}. Here, A − B = ∅, however, A ̸= B. (c) The statement is true. To prove this let x ∈ A. We need to prove that x ∈ B. We construct a proof by contradiction. Assume that x ∈ A but x ∈ / B. Then x ∈ A and x ∈ B and hence x ∈ A − B. This is a contradiction with the fact that A − B = ∅. Hence, A ⊆ B. (d) The statement is true. If A ∪ B = ∅, then each set A and B is empty. Hence, A = B = ∅. (e) The statement is true. Note that since A⊕B = (A−B)∪(B −A), then A⊕B = ∅ implies (see part (d)) that i. A − B = ∅. This gives A ⊆ B (see part (c)). ii. B − A = ∅. This gives B ⊆ A (see part (c)). Hence, A = B. (f) The statement is true. Since A × B = ∅, then A = B = ∅. (g) The statement is false. If A − B = ∅, then (see part (c)) A ⊆ B and therefore B ⊆ A. The following is a counterexample. Let U = {1, 2, 3}, A = {1, 2} and B = {2}. Then, A = {3} and therefore, A − B = A ∩ B = ∅. However, A ̸= B. 15 (h) The statement is false. Note that A − B = A implies A ∩ B = A and hence, A ⊆ B. The following is a counterexample. Let A = {1}, B = ∅ and U = {1, 2}. Then A − B = A ∩ B = A ∩ U = A. However, A is not a subset of B. (i) The statement is false. A ∪ B = A implies that B ⊂ A. Let A = {1, 2}, B = {1} and U = {1, 2, 3}. Note that A ∪ B = {1, 2} = A but B ̸= ∅. (j) The statement is true. Let x ∈ A. We prove that x ∈ B. Assume, by contradiction that x ∈ A but x ∈ / B. Then x ∈ B and since B ⊆ A then x ∈ A. This is a contradiction with the fact that x ∈ A. Hence, A ⊆ B. 12. Note that −x2 + x + 2 = −(x2 − x − 2) = −(x − 2)(x + 1). The solutions of the equation −x2 + x + 2 = 0 are x = −1 and x = 2. The quadratic function −x2 + x + 2 has a positive sign between its roots. Therefore, S = [−1, 2]. Then, S ∩ Z = {−1, 0, 1, 2} and so |S ∩ Z| = 4. 13. (a) A100 = {−100, . . . , −1, 0, 1, 2, 3, . . .} and A96 = {−96, . . . , −1, 0, 1, 2, 3, . . .} and so A100 − A96 = {−100, −99, −98, −97}. ∞ (b) ∪∞ n=1 An = Z. To see this, note that since each set An ⊆ Z, then ∪n=1 An ⊆ Z. It is left to prove that Z ⊆ ∪∞ n=1 An . Let n ∈ Z. We split the rest of the proof into three cases, according to the sign of n. Case 1. Assume that n > 0 then n ∈ An and so n ∈ ∪∞ n=1 An . ∞ Case 2. Assume that n < 0 so n ∈ A−n . Hence, n ∈ ∪n=1 An . Case 3. If n = 0, then n ∈ A1 and therefore n ∈ ∪∞ n=1 An . ∞ This concludes the proof of Z ⊆ ∪n=1 An , and so Z = ∪∞ n=1 An . (c) We claim that ∩∞ n=1 An = A1 , with A1 = {−1, 0, 1, . . .}. To prove it we should prove both inclusions. ∞ Clearly, ∩∞ n=1 An ⊆ A1 (if x ∈ ∩n=1 An , then x ∈ An , for every n ≥ 1 and so x ∈ A1 ). We need to prove that A1 ⊆ ∩∞ n=1 An . Let x ∈ A1 . Then, x ∈ An , for each n ≥ 2 (in addition, note that A1 ⊆ A2 ⊆ . . . An ⊆ . . ..). Hence, x ∈ ∩∞ n=1 An . 5 Functions 1. (a) f (n) = n + 5 is not onto. To see this, take m = 1 ∈ N. There is no n ∈ N such that f (n) = 1. However, the function is one-to-one. If f (n1 ) = f (n2 ), i.e. n1 + 5 = n2 + 5 then n1 = n2 . [n] is not one-to-one. Take n1 = 0 and n2 = 1. Then g(n1 ) = [0] = 0 and (b) g(n) = [2 ] 1 g(n2 ) = = 0. But g is onto. Let m ∈ N. Then there exists n ∈ N such that 2 g(n) = m. (You may take n = 2m, for example). 16 (c) Let f : N −→ N be given by { n + 1, if n is even f (n) = n − 1, if n is odd To show that f is one-to-one we consider n1 ∈ N and n2 ∈ N such that f (n1 ) = f (n2 ). Then, we consider the following cases. Case 1. Assume that n1 + 1 = n2 + 1. Then n1 = n2 . Case 2. Assume that n1 − 1 = n2 − 1. Then n1 = n2 . To show that f is onto, take any m ∈ N. There are two cases. Case 1. If m is even, then m + 1 is odd and f (m + 1) = (m + 1) − 1 = m. Hence, there exists n ∈ N, (n = m + 1) such that f (n) = m. Case 2. If m is odd, then m − 1 is even and f (m − 1) = (m − 1) + 1 = m. Hence, there exists n ∈ N, (n = m − 1) such that f (n) = m. Hence, f is bijective. (d) Let f : N −→ N be given by f (n) = 1. Clearly, f is not bijective (is neither a one-to-one function nor onto.) 2. Let g : A −→ B and f : B −→ C be two functions. (a) Let x1 ∈ A and x2 ∈ A such that g(x1 ) = g(x2 ). Then f (g(x1 )) = f (g(x2 )), or (f ◦ g)(x1 ) = (f ◦ g)(x2 ). Since f ◦ g is one-to-one, it follows that x1 = x2 . Hence, g is one-to-one. (b) The statement is not true, in general. The following provides a counterexample. Let A = {a}, B = {b1 , b2 } and C = {c}. We deﬁne the functions as follows. Let g(a) = b1 , f (b1 ) = f (b2 ) = c. Then (f ◦ g)(a) = c and f are clearly onto. However, g is not onto since there is no element in the domain that is mapped into b2 (or b2 ∈ / Image(g)). 3. Let f : A −→ B be a function, and S and T two subsets of A. Show that: (a) The equality of the two sets can be proved using the deﬁnition. Let y ∈ f (S ∪ T ). Then there exists x ∈ S ∪ T such that f (x) = y. It follows that x ∈ S or x ∈ T , and f (x) = y. This gives y ∈ f (S) or y ∈ f (T ) which proves f (S ∪ T ) ⊆ f (S) ∪ f (T ). The proof of f (S) ∪ f (T ) ⊆ f (S ∪ T ) can be done similarly. (b) Let y ∈ f (S ∩ T ). Then, there exists x ∈ S ∩ T such that f (x) = y. This implies that x ∈ S and x ∈ T , and f (x) = y. Hence, y ∈ f (S) ∩ f (T ). 4. We show that f is not one-to-one. Take m1 = 1, n1 = 1, m2 = 2 and n2 = 2. Clearly, (m1 , n1 ) ̸= (m2 , n2 ) but f (m1 , n1 ) = 1 and f (m2 , n2 ) = 1. 17 We show that f is onto. Let q ∈ Q. From the deﬁnition of a rational number, there m exist integers m and n, with n ̸= 0 such that q = . This proves that for any q ∈ Q, n m there exist (m, n) ∈ Z × (Z − {0}) such that f (m, n) = . n 5. For each of the following assignments, determine whether it is a function or not. If it is a function, is it one-to-one? Is it onto? (a) f1 : R −→ R, f1 (x) = −x3 +1 is a bijective function (one-to-one since −x31 +1 = −x32 + 1 implies x1 = x2 and onto since for any y ∈ R, there exist x ∈ R: √ x = 3 1 − y such that f (x) = y). (b) f2 : N −→ Z, f2 (n) = n2 + 3 is one-to-one (n21 + 3 = n22 + 3 implies n1 = n2 since they are both natural numbers) but not onto (If z = 0 ∈ Z, there is no n ∈ N such that f (n) = 0). (c) f3 : R −→ [0, +∞), f3 (x) = 2x is one-to-one (2x1 = 2x2 implies x1 = x2 ) but not onto (for y = 0, there does not exist x ∈ R such that 2x = 0). √ √ / N. (d) f4 : N −→ N, f4 (n) = n + 1 is not a function since n + 1 ∈ (e) f5 : R × R −→ R, f5 (x, y) = x + y is not one-to-one (if (x1 , y1 ) = (0, 0) and (x2 , y2 ) = (1, −1), f (x1 , y1 ) = f (x2 , y2 ) = 0) but f is onto (if y ∈ R, there exists a pair, e.g. (0, y) ∈ R × R, with f (0, y) = y). (f) f5 : R × R −→ R × N, f6 (x, y) = (2x, 0) is not on-to-one ((1, 2) and (1, 3) are both mapped into (2, 0)) and not onto (for (1, 5) ∈ R × N there does not exist a pair (x, y) ∈ R × R such that f (x, y) = (1, 5)). 6. Let (a1 , b1 ) ∈ A × B and (a2 , b2 ) ∈ A × B with λ(a1 , b1 ) = λ(a2 , b2 ). Then, 2ϕ(a1 ) 3ψ(b1 ) = 2ϕ(a2 ) 3ψ(b2 ) and so 2ϕ(a1 )−ϕ(a2 ) = 3ψ(b1 )−ψ(b2 ) . It follows that ϕ(a1 )−ϕ(a2 ) = ψ(b1 ) − ψ(b2 ) = 0. Since ϕ and ψ are one-to-one functions, we obtain a1 = a2 and b1 = b2 and so (a1 , b1 ) = (a2 , b2 ). 7. (a) Let x1 ∈ (0, +∞) and x2 ∈ (0, +∞) be such that f (x1 ) = f (x2 ). Then, 2x21 + 3 = 2x22 +3. This implies x21 = x22 and since they are positive numbers, we can conclude that x1 = x2 . Hence, f is one-to-one. (b) For any x ∈ (0, +∞), we have x2 > 0 and so 2x2 + 3 > 3. Hence, Image(f ) = (3, ∞). Since Image(f ) ̸= (0, ∞), we conclude that f is not onto. 8. The function f ◦ g : R −→ R is given by (f ◦ g)(x) = f (g(x)) = f (x3 − 2) = √ 3 (x3 − 2) + 2 = x, for any x ∈ R. √ The function g ◦ f : R −→ R is given by (g ◦ f )(x) = g(f (x)) = g( 3 x + 2) = √ ( 3 x + 2)3 − 2 = x, for any x ∈ R. Since f ◦ g = 1R and g ◦ f = 1R we conclude that f −1 = g. This implies that f is a bijection and henceg is also a bijection. 9. (a) Since |A| = 4 < |B| = 6 the statement is true. 18 (b) Since |P(A)| = 24 < 26 = |P(B)| the statement is false. (c) Since |P(A)| = 24 > 6 = |B| the statement is true. (d) Since |A × B| = |A| · |B| = 4 · 6 = 24 < 26 |P(B)| the statement is true. (e) Since |P(P(A))| = 22 = 216 < 224 = |P(A × B)| the statement is false. 4 10. The functions are not one-to-one. If (x1 = 1.2 and x2 = 1.5) then (f (x1 ) = ⌊1.2⌋ = 1 and f (x2 ) = ⌊1.5⌋ = 1) and (g(x1 ) = ⌈1.2⌉ = 2 and g(x2 ) = ⌈1.5⌉ = 2). However, the functions are onto. Let m ∈ Z be arbitrary. Then there exists x ∈ R such that the equation f (x) = m has at least one solution in R (x = m is one solution). Similarly, there exists x ∈ R such that the equation g(x) = m has at least one solution in R (x = m is one solution). 11. (a) The conclusion follows once we prove that g ◦ f and (g ◦ f )−1 are invertible. We show this by actually identifying their inverses. Since (g ◦ f ) ◦ (f −1 ◦ g −1 ) = g ◦ f ◦ f −1 ◦ g −1 = g ◦ 1B ◦ g −1 = g ◦ g −1 = 1C , and similarly, (f −1 ◦ g −1 ) ◦ (g ◦ f ) = 1A , it follows that (g ◦ f )−1 = (f −1 ◦ g −1 ) and hence, g ◦ f and f −1 ◦ g −1 are invertible (f −1 and g −1 exist since f and g are assumed to be bijective). √ (b) Let f : [0, ∞) −→ R, f (x) = x and g : R −→ [0, ∞), g(x) = x2 . The functions f and g are not bijective since f is not onto (for y = −1 ∈ R the equation f (x) = −1 has no solution in [0, ∞)) and g is not one-to-one (g(−1) = g(1) = 1). √ √ However, (g ◦ f )(x) = g(f (x)) = g( x) = ( x)2 = x is bijective. (Note that in this case, (f ◦ g)(x) = |x|, for x ∈ R.) 6 Relations 1. R1 is reﬂexive since (x, x) ∈ R1 , for any x ∈ A R1 is symmetric since (x, y) ∈ R1 implies (y, x) ∈ R1 , for any x ∈ A and y ∈ A (or equivalently, there is no pair (x, y) ∈ A × A such that (x, y) ∈ R1 and (y, x) ∈ / R1 ) (details are omitted) R1 is transitive since (x, y) ∈ R1 and (y, z) ∈ R1 implies (x, z) ∈ R1 (details are omitted) R1 is not antisymmetric since (1, 2) ∈ R1 and (2, 2) ∈ R1 but 1 ̸= 2 R2 is reﬂexive since (x, x) ∈ R2 , for any x ∈ A 19 R2 is symmetric since (x, y) ∈ R2 implies (y, x) ∈ R2 , for any x ∈ A and y ∈ A (details are omitted) R2 is transitive since (x, y) ∈ R2 and (y, z) ∈ R2 implies (x, z) ∈ R2 R2 is antisymmetric since (x, y) ∈ R2 and (y, x) ∈ R2 implies x = y R3 is not reﬂexive since (1, 1) ∈ / R3 , and 1 ∈ A R3 is not symmetric since (1, 4) ∈ R3 but (4, 1) ∈ R3 / R3 R3 is not transitive since (1, 3) ∈ R3 and (3, 1) ∈ R3 but (1, 1) ∈ R3 is not antisymmetric since (1, 3) ∈ R3 and (3, 1) ∈ R3 but 1 ̸= 3 2. R1 is not reﬂexive since (a, a) ∈ / R1 R1 is symmetric: if (x, y) ∈ R1 then (y, x) ∈ R1 is true vacuously R1 is transitive: if (x, y) ∈ R1 and (y, z) ∈ R1 then (x, z) ∈ R1 is true vacuously R1 is antisymmetric: if (x, y) ∈ R1 and (y, x) ∈ R1 then x = y is true vacuously R2 is not reﬂexive, not symmetric, transitive and antisymmetric R3 is not reﬂexive, symmetric, not transitive and not antisymmetric R4 is reﬂexive, not symmetric, transitive and antisymmetric 3. R1 is not reﬂexive since e.g. (1, 1) ∈ / R1 R1 is not symmetric since e.g. (1, 2) ∈ R1 but (2, 1) ∈ / R1 R1 is transitive since (a, b) ∈ R1 and (b, c) ∈ R1 implies (a, c) ∈ R1 (that is if a < b and b < c then a < c) R1 is antisymmetric since (a, b) ∈ R1 and (b, a) ∈ R1 implies a = b vacuously R2 is not reﬂexive since e.g. (4, 4) ∈ / R2 R2 is not symmetric since e.g. (4, 2) ∈ R2 but (2, 4) ∈ / R2 R2 is not transitive since e.g. (−3, −2) ∈ R2 and (−2, 0) ∈ R2 but (−3, 0) ∈ / R2 R2 is not antisymmetric since e.g. (−1, −2) ∈ R2 and (−2, −1) ∈ R2 but −1 ̸= −2 4. (a) The statement is true since |P(A × B)| = 215 = 32768 (b) The statement is false. The number of binary relations from B to A equals to the number of binary relations from A to B (c) The statement is false. A binary relation from P(A) to P(B) is a subset of P(P(A) × P(B)) which is not equal to P(A × B). (d) The statement is true since the number of binary relation from A to B that contain the subset {(x, 0); x ∈ A} is equal to the number of binary relations that can be deﬁned from A to the set {1, 2, 3, 4}, which is 23·5 = 4096. 20 (e) The statement is false. The number of binary relation from A to B that contain the subset {(a, y); y ∈ B} is equal to the number of binary relations that can be deﬁned from the set {b, c} to B, which is 22·5 ̸= 4096. 5. R1 is not a function since (1, a) ∈ R1 and (1, b) ∈ R1 (the element 1 would be mapped into two diﬀerent values). R1 is a function. It is not one-to-one since (0, c) ∈ R2 and (1, c) ∈ R2 (two diﬀerent inputs have the same output). It is not onto since there is no x ∈ A such that (x, b) ∈ R2 (or (x, e) ∈ R2 ) R3 is a function. It is not one-to-one since e.g. (0, c) ∈ R3 and (1, c) ∈ R3 . It is not onto since there is no x ∈ A such that (x, b) ∈ R3 (or (x, e) ∈ R3 ) R4 is a function. It is not one-to-one since (1, a) ∈ R4 and (3, a) ∈ R4 . It is not onto since there is no x ∈ A such that (x, e) ∈ R4 . R5 is not a function since it does not contain an element of the form (1, y) (the element 1 is not mapped into an element on B). R6 is a function. It is one-to-one and onto (and therefore bijective). / R1 . 6. (a) R1 is not reﬂexive since e.g. (1, 1) ∈ R1 is symmetric R1 is not transitive e.g. (1, 2) ∈ R1 and (2, 3) ∈ R1 but (1, 3) ∈ / R1 (b) R1 is not reﬂexive since e.g. (2, 2) ∈ / R2 . R2 is symmetric R2 is transitive (x, y) ∈ R2 and (y, z) ∈ R2 implies (x, z) ∈ R2 (c) R3 is reﬂexive since for any x ∈ Z we have xR3 x = x + x2 = x(x + 1) which is an even integer R3 is not symmetric. Let (2, 1) ∈ Z × Z. Since 2 + 2 · 1 = 4 is even, 2R3 1. However, (1, 2) ∈ / R since 1 + 1 · 2 = 3 is not even R3 is transitive. Let (x, y) ∈ R3 and (y, z) ∈ R3 . Then x + xy is even and y + yz is even. The proof continues by considering two cases, according to the parity of y. Case 1. Assume that y is even. Then xy is even and since x +xy is even, it follows that x is even. Hence, x + xz is even. Case 2. Assume that y is odd. Then, since y + yz is even it follows that z is odd and so x + xz is even. 7. (a) R1 is reﬂexive (A ⊆ A, for any A ∈ P(U )), not symmetric (A ⊆ B does not imply B ⊆ A), transitive (A ⊆ B and B ⊆ C implies A ⊆ C) and antisymmetric (A ⊆ B and B ⊆ A implies A = B) (b) R2 is not reﬂexive (A ∩ A = A ̸= ∅ not true for any A ∈ P(U )), symmetric (A ∩ B = ∅ implies B ∩ A = ∅), not transitive (e.g. if A = {1, 2}, B = {4} and 21 C = {2, 3}, then A ∩ B = ∅, B ∩ C = ∅ but A ∩ C = {2}) and not antisymmetric (e.g. A ={1}, B = {2} and A ∩ B = B ∩ A = ∅) (c) First show that A − B = ∅ if and only if A ⊆ B. To prove the equivalence, we ﬁrst assume A − B = ∅ is true and show that A ⊆ B holds (see also Exercise 11, part (c) in Section 4). Let x ∈ A. Then, since A − B = A ∩ B = ∅, it follows that x ∈ / B and hence x ∈ B. This proves A ⊆ B. Now we assume that A ⊆ B holds and show A − B = ∅. Case 1. If A = ∅, then A − B = ∅ is true. Case 2. Assume A ̸= ∅. Let x ∈ A. Then, since A ⊆ B, we have x ∈ B and so x∈ / B. This implies A − B = A ∩ B = ∅. Therefore, A R3 B ⇔ A ⊆ B. Therefore, R3 is equivalent to R1 and so it has the same properties. (d) Using Exercise 11, part (e) in Section 4, we conclude that A ⊕ B = ∅ if and only if A = B. Therefore, R4 becomes A R4 B ⇔ A = B. R4 is reﬂexive (A = A for any A ∈ P(U )), symmetric, transitive (A = B and B = C implies A = C) and antisymmetric (if A = B and B = A, then A = B) 8. (a) We ﬁrst show that R is symmetric. Let (a, b) ∈ R. Since R is reﬂexive, (b, b) ∈ R. Now, since R is cyclic, we apply the deﬁnition (with c = b) and obtain that (b, a) ∈ R which proves that R is symmetric. We now prove that R is transitive. Let (a, b) ∈ R and (b, c) ∈ R. Since R is cyclic we obtain (c, a) ∈ R which together with the fact that R is symmetric (proved before) proves that (a, c) ∈ R. (b) Let (a, b) ∈ R and (b, c) ∈ R. Then, since R is transitive, (a, c) ∈ R. This together with the fact that R is symmetric implies that (c, a) ∈ R which proves that R is cyclic. 9. (a) Let R = {(2, 2), (2, 3), (3, 2), (3, 3)}. R is symmetric and transitive but not reﬂexive since (1, 1) ∈ / R. (b) The proof in not correct since the following assumption is used at the beginning of the argument: for any a ∈ A, there exists b ∈ A such that (a, b) ∈ R. This statement is not true in general (see example given at the previous part: for a = 1 ∈ A there is no element b ∈ A such that (1, b) ∈ R). 7 Equivalence Relations x 1. (a) The relation R is reﬂexive (for any x ∈ A, xRx, since = 30 ), symmetric (for x x y any x, y ∈ A, xRy implies yRx, since = 3k implies = 3−k for some k ∈ Z) y x 22 x and transitive (for any x, y, z ∈ A, xRy and yRz imply xRz, since = 3k and y y x l k+l = 3 imply = 3 for some k ∈ Z and l ∈ Z). z z { } { } { } { } 1 1 1 1 9 2 (b) The partition is {1}, , , 3 , , , , {2}, , {5}. 3 27 4 36 4 9 2. (a) The relation R is reﬂexive (for any f ∈ A, f Rf , since f (x)−f (x) = 0), symmetric (for any f, g ∈ A, f Rg implies gRf , since f (x)−g(x) = c implies g(x)−f (x) = −c for some constant c ∈ Z) and transitive (for any f, g, h ∈ A, f Rg and gRh imply f Rh, since f (x) − g(x) = c and g(x) − h(x) = d imply f (x) − h(x) = c + d for some c ∈ Z and d ∈ Z). (b) [f (x)]R = {g : Z → R, g is a function such that f (x)−g(x) = c, for some constant c ∈ Z} = {g : Z → R, g is a function such that g(x) = 2x + c, for some constant c ∈ Z}. Hence, f1 ,f5 ∈ [f (x)]R 3. (a) The fact that R is an equivalence relation on W follows from properties of real numbers. Note that two pairs are included in R if and only if their components have same sign, respectively, i.e. (x, y)R(a, b) if and only if (x and a have same sign and y and b have same sign) (b) There are four equivalence classes on W (corresponding to the four quadrants in the plane): [(1, 1)]R , [(1, −1)]R , [(−1, 1)]R , [(−1, −1)]R . 4. (a) Follows easily from properties of real numbers. (b) The following two sets form the partition on A deﬁned by R. {( {( 1 0 0 0 1 0 0 1 )} ) ( 2 1 , , 3 2 ) ( ) ( ) ( )} 2 4 0 1 0 0 , , , . 3 6 0 0 0 0 5. The given binary relation on R2 can be equivalently deﬁned as (x, y)R (x′ , y ′ ) ⇔ x − y = x′ − y ′ . (a) Follows easily from properties of real numbers. (b) [(1, 1)]R = {(x, y) ∈ R2 , x − y = 0} = {(x, x) ∈ R2 }. The equivalence class of the vector (1, 1) represents the points located on the ﬁrst diagonal, i.e the points located on the line y = x. 6. (a) R is an equivalence relation since it is: - reﬂexive (a = a · 1) 23 1 - symmetric (if b = a · c then a = b, for some c > 0) c - transitive (if b = a · c and d = b · e, for some c > 0 and e > 0, then d = a · (ce), with ce > 0) (b) The partition consists of [1]R = (0, ∞), [−1]R = (−∞, 0) and [0]R = {0}. 7. (a) Note that κ(a) ∈ N∗ , for any a ∈ N∗ . R is an equivalence relation since it is: - reﬂexive (κ(a) = κ(a)) - symmetric (if κ(a) = κ(b) then κ(b) = κ(a)) - transitive (if κ(a) = κ(b) and κ(b) = κ(c), then κ(a) = κ(c)) (b) [2]R = {n ∈ N∗ , κ(2) = κ(n)}. Since κ(2) = 2, [2]R = {n ∈ N∗ , n is even}. 8. (a) omitted (b) The partition is the following sequence of sets. {011, 111} , {010, 110} , {001, 101} , {000, 100} 9. (a) omitted (b) [(0, 2)]R = {(x, y) ∈ R2 , x2 + y 2 = 4}. The sets consists of the points located on the circle of radius 2 and origin (0, 0). Other elements in the equivalence class of (0, 2) are e.g. (2, 0), (−2, 0), (0, −2). 10. (a) R is an equivalence relation since it is - reﬂexive: ARA since A = 1 · A 1 A, for some λ ∈ R∗ λ - transitive: ARB and BRC imply ARC, since A = λB and B = γC imply A = δC, where δ = λ · γ ∈ R∗ - symmetric: ARB implies BRA, since A = λB implies B = (b) The partition is {A1 , A5 , A8 }, {A2 , A6 }, {A3 , A7 } and {A4 }. a b = . Hence aRb if a and b have |a| |b| the same sign, so the given relation can be equivalently written as 11. Let a, b ∈ R∗ such that aRb. Then |a|b = a|b|, or aR b ⇔ a and b have the same sign. (a) omitted (b) [1]R = (0, ∞). 8 Basic Counting Techniques 1. Note that in this question we assume that a license plate has six characters. Let A be the set of license plates that can be made with three digits followed by three letters and B be the set of license plates that can be made with three letters followed by three digits. We need to compute the cardinality of A ∪ B. 24 Since A ∩ B = ∅, using the principle of exclusion-inclusion, we have |A ∪ B| = |A| + |B|. Using the product rule, |A| = 10 · 10 · 10 · 26 · 26 · 26 = 2603 , |B| = 2603 and hence |A ∪ B| = 2 · 2603 = 35152000. 2. Assume that n is even. Then, there exists k ∈ N∗ such that n = 2k. Hence, we only need to count the number of binary strings of length k that can be formed. This n number is equal to 2k , using the product rule. Therefore, there are 2 2 palindromes of length n, if n is even. Assume that n is odd. Then, there exists k ∈ Nk such that n = 2k + 1. The number of binary strings of length k that can be formed is 2k , but since n is odd, we need to multiply by 2 (at position k + 1 we can have either 0 or 1). Therefore, there are n−1 n+1 2 2 +1 = 2 2 palindromes of length n, if n is odd. 3. There are 5 odd digits and 26 letters in total. Using the product rule and excluding repetitions, the number of postal codes of the given form is 5 · 26 · 4 · 25 · 3 · 24 = 936000. 4. Assume that A = {x1 , . . . , x7 } and B = {y1 , . . . , y4 }. (a) There are 4 ways in which f (x1 ) can be deﬁned, 4 ways in which f (x2 ) can be deﬁned, etc. In total, using the product rule, there are 47 = 16384 ways in which a function from A to B can be deﬁned. (b) There are 7 ways in which f (y1 ) can be deﬁned, 7 ways in which f (y2 ) can be deﬁned, etc. In total, using the product rule, there are 74 = 2401 ways in which a function from B to A can be deﬁned. (c) Since |A| > |B|, we cannot deﬁne an one-to-one function from A to B. (d) There are 7 ways in which f (x1 ) can be deﬁned. Since the function must be one-to-one, there are 6 ways in which f (x2 ) can be deﬁned (after choosing the value of f (x1 )). After specifying the values of f (x1 ) and f (x2 ), there are 5 ways of deﬁning f (x3 ) and ﬁnally, using the same procedure, there are 4 ways of deﬁning f (x4 ). In total, using the product rule, there are 7 · 6 · 5 · 4 = 840 ways in which a one-to-one function from B to A can be deﬁned. (e) We ﬁrst compute the number of functions that can be deﬁned from A to B that are not onto. For every 1 ≤ i ≤ 4, we deﬁne the set Fi = {f : A → B, yi ∈ / Image(f )}. The number of functions that can be deﬁned from A to B that are not onto is |F1 ∪ F2 ∪ F3 ∪ F4 | = |F1 | + |F2 | + |F3 | + |F4 | − |F1 ∩ F2 | − |F1 ∩ F3 | − + − = |F1 ∩ F4 | − |F2 ∩ F3 | − |F2 ∩ F4 | − |F3 ∩ F4 | |F1 ∩ F2 ∩ F3 | + |F1 ∩ F2 ∩ F4 | + |F1 ∩ F3 ∩ F4 | + |F2 ∩ F3 ∩ F4 | |F1 ∩ F2 ∩ F3 ∩ F4 | 37 + 37 + 37 + 37 − 27 − 27 − 27 − 27 − 27 − 27 + 17 + 17 + 17 + 17 − 0 = 7984. 25 Now, the number of onto functions that can be deﬁned from A to B is equal to 16384 − 7984 = 8400. (f) Since |B| < |A|, we cannot deﬁne an onto function from B to A. 5. Note that there are 9 digits that can be placed on the ﬁrst position of the number (corresponding to the cardinality of {1, . . . 9}), 9 digits that can be placed on the second position, after the ﬁrst position was occupied (that is 10 − 1), etc. The number of integers with the given property is 9 · 9 · 8 · 7 · 6 = 27216. 6. Let A = {n ∈ N : 7 ≤ n ≤ 2125, n is divisible by 3} and B = {n ∈ N : 7 ≤ n ≤ 2125, n is divisible by 11}. Then A∩B = {n ∈ N : 7 ≤ n ≤ 2125, n is divisible by 33}. (a) The number of integers between 7 and 2125 (inclusive) that are divisible by 3 or 11 is |A ∪ B|. To compute it we need |A| = ⌊ 2125 ⌋ − ⌊ 63 ⌋ = 708 − 2 = 706, 3 6 6 |B| = ⌊ 2125 ⌋ − ⌊ 11 ⌋ = 193 − 0 = 193, and |A ∩ B| = ⌊ 2125 ⌋ − ⌊ 33 ⌋ = 64 − 0 = 64. 11 33 Using the Principle of Inclusion-Exclusion, |A ∪ B| = |A| + |B| − |A ∩ B| = 706 + 193 − 64 = 835. (b) Let U = {n ∈ N : 7 ≤ n ≤ 2125} be our universal set. This question is asking for the number of integers between 7 and 2125 (inclusive) that are not divisible by 11 (since 11 is a prime, an integer n is co-prime with 11 — that is, has no common divisors with 11 except 1 — precisely when n is not divisible by 11). This number is |U − B| = |U | − |B| = (2125 − 6) − 193 = 1926. (c) We need to compute |A − B|. We write A = (A − B) ∪ (A ∩ B), and since (A − B) ∩ (A ∩ B) = ∅, using the Sum Rule we obtain |A| = |A − B| + |A ∩ B|. From here, we conclude that |A − B| = |A| − |A ∩ B| = 706 − 64 = 642. 7. Let A-be the set of length 13 binary strings that begin with 0110 and B-be the set of length 13 binary strings that end with 1000. We need |A ∪ B|. Using the principle of inclusion-exclusion, |A ∪ B| = |A| + |B| + |A ∩ B|. We have |A| = 29 , |B| = 29 and |A ∩ B| = 25 and so |A ∪ B| = 29 + 29 − 25 = 992. 8. Let A = {n ∈ N : 1 ≤ n ≤ 250, n is divisible by 4} and B = {n ∈ N : 1 ≤ n ≤ 250, n is divisible by 6}. Then A ∩ B = {n ∈ N : 1 ≤ n ≤ 250, n is divisible by 12}. We need |A ∪ B|. We have |A| = ⌊ 250 ⌋ = 62, |B| = ⌊ 250 ⌋ = 41 and |A ∩ B| = ⌊ 250 ⌋ = 20. It follows that 4 6 12 |A ∪ B| = 62 + 41 − 20 = 83. 9. For every 0 ≤ i ≤ n we deﬁne Ai = {the set of binary strings of length i}. Note that the binary string of length 0 is the empty string so A0 = {empty string} and |A0 | = 1. Since the sets Ai are mutually disjoint, the number of binary strings of length at most 26 n is |A0 ∪ . . . An | = |A0 | + |A1 | + . . . + |An | = 1 + 2 + 2 + 2 . . . + 2 = 2 3 n n ∑ 2i i=0 −1 = 2n+1 − 1. 2−1 n+1 = 2 10. In this question it is assumed that the plates can have either 4, 5 or 6 characters. Let A be the set consisting of all 4 characters license plates that are formed using 2 letters followed by 2 digits B be the set consisting of all 5 characters license plates that are formed using 2 letters followed by 3 digits C be the set consisting of all 5 characters license plates that are formed using 3 letters followed by 2 digits D be the set consisting of all 6 characters license plates that are formed using 3 letters followed by 3 digits. We need to ﬁnd A ∪ B ∪ C ∪ D. Using the product rule, |A| = 262 · 102 = 67600, |B| = 262 · 103 = 676000, |C| = 263 · 102 = 1757600 and |D| = 263 · 103 = 17576000. Since the sets are mutually disjoint, it follows that A∪B∪C ∪D = |A|+|B|+|C|+|D| = 20077200. 11. For 6 ≤ i ≤ 9, we deﬁne Pi = {i characters passwords that contain at least two distinct characters}. We need to ﬁnd |P6 ∪ P7 ∪ P8 ∪ P9 |. For 6 ≤ i ≤ 9, since the length i password can contain characters that are either a lower letter, an upper case or a digit, it follows that there are 2 · 26 + 10 options for a certain position. Because a password cannot have identical characters it follows that |Pi | = 62i − 62. Therefore, since Pi are mutually disjoint, for 6 ≤ i ≤ 9, we have |P6 ∪ P7 ∪ P8 ∪ P9 | = |P6 | + |P7 | + |P8 | + |P9 | = (626 − 62) + (627 − 62) + (628 − 62) + (629 − 62) =. 12. (a) Since the bride should stand next to the groom (i.e. either to the left or to the right), the number of ways the group of 6 people can be arranged equals to twice the number of ways in which we can arrange a group of 5 people. Hence, there are 2 · 5! = 240 ways in which a group with the given property can be arranged. (b) There are 6! ways in which a group of 6 can be arranged and so, using part (a), there are 6! − 2 · 5! = 480 ways to arrange the group so that the bride does not stand next to the groom. (c) The arranging procedure can be divided into the following steps. 27 T1 : arrange the 4 people in the group that are neither the bride neither the groom nor the bride T2 : arrange the groom in one of the 5 gaps between the guests and the bride to the left of groom There are 4! ways to perform T1 . According to the position of the groom, there are diﬀerent ways in which the bride can be placed. Using the summation rule, the number of ways T2 can be performed is 1 + 2 + 3 + 4 + 5. The ﬁrst term corresponds to the situation when the groom is placed on the ﬁfth position and the bride is placed on the sixth, the second term corresponds to the situation when the groom is placed on the fourth position, and hence the bride can be placed either on the ﬁfth or on the sixth position, etc. Using the product rule, there are 15 · 24 = 360 ways to arrange people in a picture such that the bride is situated to left of the groom. 9 The Pigeonhole Principle 1. Draw the three diagonals to divide the regular hexagon into 5 equilateral triangles, each with side of length 1. In each triangle, any two points in the interior or on the perimeter are at distance at most one. Since there are 6 triangles and 7 points, by PP, two points will have to lie in the same triangle, and hence be at distance at most 1. 2. For each computer, the number of computers it is directly linked to (call them neighbours) is in the set {1, 2, 3, 4, 5}. There are 6 computers and 5 possible numbers of neighbours; hence by PP, at least two computers must have the same number of neighbours. 3. There are 7 · 12 = 84 possible pairs (day of the week, month). Hence by PP, we need at least 85 people to guarantee that at least two among them were born on the same day of the week and in the same month. 4. Assuming that every package contains 20 distinct cards, we need at least 28 packages, since 27 · 20 < 551 ≤ 28 · 20. 5. There are 14 possible remainders (0, 1, 2, . . . , 13) when dividing by 14. Hence any set of 15 integers will contain two that give the same remainder when divided by 14. The diﬀerence of these numbers will be then divisible by 14. 6. There are 9 possible remainders (0, 1, 2, . . . , 8) when dividing by 9. The “worst-case scenario” is to have 9 · 5 = 45 integers such that no 6 have the same remainder. However, by PP, any set of 46 integers will contain 6 that have the same remainder. 7. The number of such birth certiﬁcate codes is n = 104 · 263 . By PP, to guarantee that at least 26 certiﬁcates carry the same code, we need at least 25n + 1 certiﬁcates. Hence the number of people (certiﬁcates) is at least 25 · 104 · 263 + 1 = 4, 394, 000, 001. 28 () () () () 8. The number of subsets of A of cardinality at most 3 is 90 + 91 + 92 + 93 = 1 + 9 + 36 + 84 = 130. The sum of the elements that such a set can have is in the set {0, 1, 2, . . . , 24}. Since 130 > 24 · 5, any there exist 6 subsets of cardinality at most 3 that have the same sum of elements. 9. Draw a grid that divides the rectangle into squares of side length 10cm. There will be 200 such squares. Any three points within (or on the perimeter) of one of these squares deﬁne a triangle of area at most half the area of the square, that is, at most 50cm2 . Since there are 500 points and 200 squares, by PP, some square indeed contains at least 3 points (otherwise there would be at most 400 points). 10. Consider the integers 1, 11, 111, ..., up to the integer with 7778 repeated ones, and their remainders when divided by 7777. Since there are only 7777 possible remainders when divided by 7777, two of these 7778 integers (say x with a ones and y with b ones, for x < y) have the same remainder. Hence their diﬀerence y − x is divisible by 7777. But y − x has b − a ones followed by a zeros. Let z be the number with b − a repeated ones. Then y − x = z · 10a . So 7777 divides z · 10a , but since 7777and 10a have no common divisors, 7777 must in fact divide z. Hence z is the integer with repeated ones that is divisible by 7777. 11. The possible numbers of mistakes are 0, 1, 2, . . . , 12 (boxes). Placing the 30 objects (students) into 12 boxes, by PP, we’ll end up with at least one box with at least 3 objects. x +x y +y z +z 12. For each pair i, j ∈ {1, 2, . . . , 9}, i < j, let Mij = ( i 2 j , i 2 j , i 2 j ) denote the midpoint of the line segment joining points Pi = (xi , yi , zi ) and Pj = (xj , yj , zj ). Mij will have integer coordinates if and only if xi and xj , yi and j , and zi and zj have equal parity. There are 8 possible triples (q1 , q2 , q3 ) where each qi is either “odd” or “even”; these are our boxes. Placing the 9 points into these 8 boxes we’ll end up with a box with at least two points, say Pi and Pj . Then their midpoint Mij will have integer coordinates as explained above. 10 Permutations and Combinations 1. 2 · (n!)2 ( ) 2. 40 17 3. The coeﬃcient of xk is 0 if k is odd, and ( 100 50− k2 ) if k is even. 4. Essentially, we have 2 symbols, (9)ﬁve 011s (which jointly contain ten 1s) and four more 1s. These can be arranged in 5 ways. (200) 99 101 5. (a) − (24)1012 2 3 (b) ( 2) 2 (c) 84 24 and 0, respectively. 29 () 6. (a) (94 ) ( ) ( ) ( ) ( ) (b) 90 +((91) + (92) + (93) + (94)) (c) 29 − 90 + 91 + 92 + 93 7. (a) 2(44) (b) ( 44 14 )( ) (c) 63 44 9 (12)(13) 8. (a) 3 2 (since S contains 12 even and 13 odd elements) ∑ ( )( ) (b) 9i=1 10i 9i ( ) 9. (a) (13 4) (b) 12 ∑4 ( )( 8 ) (c) 3i=0 5i 5−i ( ) (d) 10 4 (38) ∑2 (10)( 28 ) 10. (a) 6 − i=0 i 6−i ( )( ) (b) ( 83 )(30 3 ) 20 (c) (10 4 )( 2)( ) (28)(4)(14) 5 15 (d) 28 − 2 2 2 2 1 1 11. P (26, 3)P (10, 3) = 26 · 25 · 24 · 10 · 9 · 8 12. omitted ( )(47)(42)(37)(32)(27) 13. 52 5 5 5 5 5 5 11 Mathematical Induction 1. For all n ∈ Z+ , deﬁne the proposition P (n) as 12 + 22 + . . . + n2 = n(n + 1)(2n + 1) . 6 BI: to prove P (1). The LHS of (*) is 1 and the RHS is holds. 1(1+1)(2·1+1) 6 (∗) = 1 Hence P (1) IS: We must show P (k) → P (k + 1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (k) . Now consider P (k + 1). The LHS is holds; that is, 12 + 22 + . . . + k 2 = k(k+1)(2k+1) 6 (using IH) k(k + 1)(2k + 1) + (k + 1)2 6 1 = (k + 1)(2k 2 + k + 6k + 6) 6 1 = (k + 1)(k + 2)(2(k + 1) + 1), 6 30 12 + 22 + . . . + k 2 + (k + 1)2 = which is the RHS of P (k + 1). Thus P (k) → P (k + 1) holds. By Mathematical induction, since P (1) holds and P (k) → P (k+1) holds for all k ∈ Z+ , we conclude that P (n) holds for all n ∈ Z+ . 2. omitted 3. Let n = 2m − 1. We thus have to show that P (n) : (2m − 1)2 − 1 is divisible by 8 for all m ∈ Z+ . BI: to prove P (1). Now (2 · 1 − 1)2 − 1 = 0, which is divisible by 8. Hence P (1) holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (k) holds; that is, (2k − 1)2 − 1 is divisible by 8. Consider P (k + 1). (2(k + 1) − 1)2 − 1 = ((2k − 1) + 2)2 − 1 = (2k − 1)2 + 4(2k − 1) + 4 − 1 = ((2k − 1)2 − 1) + 8k Since (2k−1)2 −1 is divisible by 8 by IH, and 8k is clearly divisible by 8, (2(k+1)−1)2 −1 is divisible by 8. Thus P (k) → P (k + 1) holds. By Mathematical induction, since P (1) holds and P (k) → P (k+1) holds for all k ∈ Z+ , we conclude that P (m) holds for all m ∈ Z+ . 4. We thus have to show that P (n) : 4n+1 + 52n−1 is divisible by 21 for all m ∈ Z+ . BI: to prove P (1). Now 41+1 + 52·1−1 = 42 + 51 = 21, which is divisible by 21. Hence P (1) holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (k) holds; that is, 4k+1 + 52k−1 is divisible by 21. Consider P (k + 1). 4(k+1)+1 + 52(k+1)−1 = 4k+2 + 52k+1 = 4 · 4k+1 + 25 · 52k−1 = 4(4k+1 + 52k−1 ) + 21 · 52k−1 Since 4k+1 + 52k−1 is divisible by 21 by IH, and 21 · 52k−1 is clearly divisible by 21, 4(k+1)+1 + 52(k+1)−1 is divisible by 21. Thus P (k) → P (k + 1) holds. By Mathematical induction, since P (1) holds and P (k) → P (k+1) holds for all k ∈ Z+ , we conclude that P (n) holds for all n ∈ Z+ . 5. It can be checked that 2n < n3 for n ∈ {1, 2, . . . , 9}. We shall prove P (n) : 2n > n3 31 for all n ∈ Z, n ≥ 10. BI: to prove P (10). Now 210 = 1024 > 1000 = 103 . Hence P (10) holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z, k ≥ 10. Take any k ∈ Z, k ≥ 10 and assume P (k) holds; that is, 2k > k 3 . Consider P (k + 1). ( 3 ) k3 k3 k3 k k+1 k 3 3 3 3 3 2 = 2·2 >2·k =k +k =k +3· =k + + + 3 3 3 3 ( 3 ) ( 2 ) 2 k k k k k > k3 + + + > k 3 + 9 + 9 + 1 = (k + 1)3 3 3 3 3 3 Thus P (k) → P (k + 1) holds. By Mathematical Induction, since P (1) holds and P (k) → P (k + 1) holds for all k ∈ Z, k ≥ 10, we conclude that P (n) holds for all n ∈ Z, n ≥ 10. 6. We must prove ( P (n) : fn > √ )n−2 1+ 5 2 for all n ∈ Z, n ≥ 3. We shall use Strong Induction. BI: to prove P (3). Note f3 = f2 + f1 = f1 + f0 + f1 = 3 and √ 1+ 9 2 ( √ )3−2 1+ 5 2 = √ 1+ 5 2 < = 2. Hence P (3) holds. IS: We must show (P (3) ∧ P (4) ∧ . . . ∧ P (k)) → P (k + 1) for all k ∈ Z, k ≥ 3. Take ( √ )i−2 any k ∈ Z, k ≥ 3 and assume P (3), P (4), . . . , P (k) all hold; that is, fi > 1+2 5 for all i ∈ {3, 4, . . . , k}. Examine fk+1 . If k = 3, then fk+1 = f4 = f3 + f2 = 3 + 2 = 5 and ( √ )4−2 ( √ )2 √ √ 1+ 5 3+ 9 3+ 5 1+ 5 < = 3. Hence P (4) holds. = = 2 2 2 2 Otherwise, k ≥ 4 and by IH we obtain ( fk+1 √ )k−2 ( √ )k−3 1+ 5 1+ 5 = fk + fk−1 > + 2 2 ( ) ( ( √ )k−3 ( √ )k−3 √ )k−1 √ √ 1+ 5 1+ 5 1+ 5 3+ 5 1+ 5 = +1 = = 2 2 2 2 2 Thus (P (3) ∧ P (4) ∧ . . . ∧ P (k)) → P (k + 1) holds. By Strong Induction, since P (3) holds and (P (3) ∧ P (4) ∧ . . . ∧ P (k)) → P (k + 1) holds for all k ∈ Z, k ≥ 3, we conclude that P (n) holds for all n ∈ Z, n ≥ 3. 7. We shall prove P (n) : n2 ≥ 2n + 3 for all n ∈ Z, n ≥ 3. 32 BI: to prove P (3). Now 32 = 9 ≥ 2 · 3 + 3. Hence P (3) holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z, k ≥ 3. Take any k ∈ Z, k ≥ 3 and assume P (k) holds; that is, k 2 ≥ 2k + 3. Consider P (k + 1). Using the IH we obtain (k + 1)2 = k 2 + 2k + 1 ≥ (2k + 3) + (2k + 1) = 4k + 4 = 2(k + 1) + 3 + (2k − 1) > 2(k + 1) + 3 Thus P (k) → P (k + 1) holds. By Mathematical Induction, since P (1) holds and P (k) → P (k + 1) holds for all k ∈ Z, k ≥ 3, we conclude that P (n) holds for all n ∈ Z, n ≥ 3. 8. We shall prove P (n) : 7n − 2n is divisible by 5 for all n ∈ N. BI: to prove P (0). Now 70 − 20 = 0, which is divisible by 5. Hence P (0) holds. IS: We must show P (k) → P (k + 1) for all k ∈ N. Take any k ∈ N and assume P (k) holds; that is, 7k − 2k is divisible by 5. Consider P (k + 1). Using the IH we obtain 7k+1 − 2k+1 = 7 · 7k − 2 · 2k = 7(7k − 2k ) + 5 · 2k Since 7k − 2k is divisible by 5 by IH, and 5 · 2k is clearly divisible by 5, we conclude that 7k+1 − 2k+1 is divisible by 5. Thus P (k) → P (k + 1) holds. By Mathematical Induction, since P (0) holds and P (k) → P (k + 1) holds for all k ∈ N, we conclude that P (n) holds for all n ∈ N. 9. omitted (this is very similar to Question 1). 10. We shall prove P (n) : 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1 for all n ∈ Z+ . BI: to prove P (1). Now 1 · 1! = 1 = (1 + 1)! − 1. Hence P (1) holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (k) holds; that is, 1 · 1! + 2 · 2! + . . . + k · k! = (k + 1)! − 1. Consider P (k + 1). Using the IH we obtain 1 · 1! + 2 · 2! + . . . + k · k! + (k + 1) · (k + 1)! = (k + 1)! − 1 + (k + 1) · (k + 1)! = (1 + k + 1) · (k + 1)! − 1 = (k + 2)! − 1 Thus P (k) → P (k + 1) holds. By Mathematical Induction, since P (1) holds and P (k) → P (k+1) holds for all k ∈ Z+ , we conclude that P (n) holds for all n ∈ Z+ . 33 11. We must prove P (n) : an = 2n + (−1)n for all n ∈ N. We shall use Strong Induction. BI: to prove P (0). Note a0 = 2 = 20 + (−1)0 . Hence P (0) holds. IS: We must show (P (0) ∧ P (1) ∧ . . . ∧ P (k)) → P (k + 1) for all k ∈ N. Take any k ∈ N and assume P (0), P (1), . . . , P (k) all hold; that is, ai = 2i +(−1)i for all i ∈ {0, 1, . . . , k}. Examine ak+1 . If k = 0, then ak+1 = a1 = 1 by deﬁnition, and 21 + (−1)1 = 1, so P (1) holds. Otherwise, k ≥ 1 and by IH we obtain ak+1 = ak + 2ak−1 = 2k + (−1)k + 2(2k−1 + (−1)k−1 ) = 2k + (−1)k + 2k − 2 · (−1)k = 2k+1 + (−1)k+1 Thus (P (0) ∧ P (1) ∧ . . . ∧ P (k)) → P (k + 1) holds. By Strong Induction, since P (0) holds and (P (0) ∧ P (1) ∧ . . . ∧ P (k)) → P (k + 1) holds for all k ∈ N, we conclude that P (n) holds for all n ∈ N. 12. (1) a1 = a3 = a5 = a + 7 = 2, a2 = 4, a4 = 16, a6 = 4, a8 = 256 (2) We must prove P (n) : an ≤ 2n for all n ∈ Z+ . We shall use Strong Induction. BI: to prove P (1). Clearly a1 = 2 ≤ 21 . Hence P (1) holds. IS: We must show (P (1)∧P (2)∧. . .∧P (k)) → P (k+1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (1), P (2), . . . , P (k) all hold; that is, ai ≤ 2i for all i ∈ {1, 2, . . . , k}. Examine ak+1 . If k is even, then ak+1 = 2 ≤ 2k+1 and so P (k + 1) holds. Otherwise, k is odd and k ≥ 1, and by IH we obtain ( k+1 )2 ak+1 = a2k+1 ≤ 2 2 = 2k+1 2 Thus (P (1) ∧ P (2) ∧ . . . ∧ P (k)) → P (k + 1) holds. By Strong Induction, since P (1) holds and (P (1) ∧ P (2) ∧ . . . ∧ P (k)) → P (k + 1) holds for all k ∈ Z+ , we conclude that P (n) holds for all n ∈ Z+ . 13. omitted 14. omitted 34 12 Graphs 1. (a) Does not exist, as every graph has an even number of vertices of odd degree. (b) Does not exist. Such a graph would have a vertex of degree 5, but there are only 4 other vertices it can be adjacent to. (c) Exists: this is a star on 5 vertices. (d) Does not exist: if u and v are 2 vertices of degree 3, then each must be adjacent to the remaining two vertices. Hence there can not be a vertex of degree 1. (e) Exists. (f) Does not exist: if u and v are 2 vertices of degree 6, then each must be adjacent to the remaining ﬁve vertices. Hence there can not be a vertex of degree 1. (g) Exists: C3 . (h) Does not exist: the maximum degree a simple graph with 6 vertices can have is 5. ( ) 2. (i) n2 = n(n−1) . The complete graph Kn achieves this upper bound. 2 (ii) 12 (2 + 2 + 3 + 3 + 4) = 7. ∑ ∑ (iii) |E| = 12 v∈V deg(v) ≥ 12 v∈V 3 = 32 n. 3. Let G be a simple graph with n ≥ 2 vertices. The possible degrees for a vertex in G are 0, 1, 2, . . . , n − 1. However, if there is a vertex of degree n − 1, there can not be a vertex of degree 0. Hence there are at most n − 1 possible degrees. By the Pigeonhole Principle, at least two of the n vertices must hence have the same degree. () 4. (1) |V (G)| = 94 = 126. (2) Let A be a vertex in G. To construct a subset B of S such that |A ∩ B| = 1, we choose(1)vertex from A for the intersection, and then 3 out of S − A for B − A. There are 4 · 53 = 40 such subsets. Hence A as a vertex in G has degree 40, and G is regular ∑ of degree 40. By the Handshaking Theorem, |E| = 21 v∈V deg(v) = 12 126 · 40 = 2520. 5. For all n ∈ Z+ , deﬁne a proposition P (n) : “Kn has n(n−1) edges.” 2 1(1−1) BI: n = 1. Clearly K1 has 0 edges, and 2 = 0. Hence BI holds. IS: We must show P (k) → P (k + 1) for all k ∈ Z+ . Take any k ∈ Z+ and assume P (k) holds; that is, Kk has k(k−1) edges. Now consider Kk+1 . Take any vertex in 2 Kk+1 . Removing this vertex and all edges incident with it (observe there are k of them) we obtain a graph H isomorphic to Kk . By IH, H has k(k−1) edges. Hence G 2 k(k−1) (k+1)k has 2 + k = 2 edges, and P (k + 1) holds. Thus P (k) → P (k + 1) holds. By Mathematical induction, since P (1) holds and P (k) → P (k+1) holds for all k ∈ Z+ , we conclude that P (n) holds for all n ∈ Z+ . 6. (1) Let G = (V, E) be a graph with n vertices that is regular of odd degree k. We have ∑ ∑ |E| = 12 v∈V deg(v) = 12 v∈V k = 12 nk. Since k is odd, and |E| is an integer, n must be even. (2) Since n must be even from (1), n = 2m for an integer m. Then |E| = mk as seen above, and E is a multiple of k. 35 7. omitted 8. omitted 9. Isomorphic with the indicated isomorphism. 0 0 5 4 5 1 4 1 9 6 6 9 8 8 3 7 7 2 3 2 10. The ﬁrst and third graph are isomorphic (with the indicated isomorphism), and they are bipartite graphs. The second graph is not bipartite (it contains C3 as a subgraph) and hence not isomorphic to the other two. 1 6 1 3 5 2 4 6 2 5 3 4 11. The ﬁrst and third graph are isomorphic, and they are bipartite graphs. The second graph is not bipartite (it contains C5 as a subgraph) and hence not isomorphic to the other two. 1 2 1 7 5 6 6 2 8 7 4 4 3 5 8 3 12. Bipartite. Not bipartite (it contains C5 as a subgraph). Bipartite. Not bipartite (it contains C3 as a subgraph). 13. (a) No as it has vertices of odd degree. (b) Yes since it has exactly two vertices of odd degree, namely, u and v. An open Euler trail has to start at u and end at v or vice-versa. Example of an open Euler tour: uacdabcvdubv. 36 (c) In G + uv, all vertices have even degree. Hence, G + uv has an Euler tour, but no open Euler trail. Example of an Euler tour: uacdabcvdubvu. 14. Consider the graph G whose vertices are the ﬁve quarters and he edges are the fourteen bridges. (a) Here we are looking for an Euler tour in G. Since G has vertices of odd degree (A and B), it has no Euler tour. (b) Yes, an open Euler tour exists since G has exactly two vertices of odd degree, A and B. An open Euler tour must have these two vertices and endpoints. One possible open Euler tour: b2 b1 b5 b6 b7 b8 b12 b4 b3 b14 b13 b10 b9 b11 . 15. omitted 16. omitted 17. (a) Let n and e be the number of vertices and edges, respectively, in a full 5-ary tree T with 101 leaves. Then n = 5i + 1 = i + 101, where i is the number of internal vertices. Solving for i we obtain i = 25. Now e = n − 1 = (i + 101) − 1 = 125. (b) Since in a full m-ary tree of height h the number of leaves is at most mh , we have 51 ≤ m3 . That gives m ≥ 4. On the other hand, n = ℓ + i = mi + 1 (where n is the number of vertices, ℓ the number of leaves, an di the number of internal vertices). From here we obtain ℓ − 1 = (m − 1)i. In our case, 50 = (m − 1)i or 2 · 52 = (m − 1)i. Since m − 1 is an integer, m − 1 ∈ {1, 2, 5, 10, 25, 50}. Since m ≥ 4 from above, we have m ∈ {6, 11, 26, 51}. It can be veriﬁed that m = 51 and m = 26 can not give a tree of height 3, while trees with m = 6 and m = 11 can be easily constructed. 37

Help

## 0 Replies to “Mat1348 Assignment Solutions”