MTL180: Discrete Mathematical Structures
Tutorial Sheet 2 (2024)
1. What rules of inference are used in this argument? “No man is an island. Manhat-
tan is an island. Therefore, Manhattan is not a man.”
2. Determine whether these are valid arguments. a) Ifx is a positive real number,then
x2 is a positive real number. Therefore, if a2 is positive, where a is a real number,
then a is a positive real number. b) If x2 ̸= 0, where x is a real number,then
x ̸= 0.Let a be a real number with a2 ̸= 0; then a ̸= 0.
3. Use rules of inference to show that if ∀x(P (x) ∨ Q(x)) and ∀x(¬P (x) ∧ Q(x)) →
R(x)) are true, then ∀x(¬R(x) → P (x)) is also true, where the domains of all
quantifiers are the same.
4. Show that if n is an integer and n3 + 5 is odd, then n is even using a) a proof by
contraposition. b) a proof by contradiction.
5. Prove that these four statements about the integer n are equivalent: (i) n2 is odd,
(ii) 1 − n is even, (iii) n3 is odd, (iv)n2 + 1 is even.
6. Prove that either 2.10500 + 15 or 2.10500 + 16 is not a perfect square. Is your proof
constructive or nonconstructive?
7. Prove that there are no solutions in integers x and y to the equation 2x2 + 5y 2 = 14.
8. Prove that there is an irrational number between every two rational numbers.
9. Prove that between every rational number and every irrational number there is an
irrational number.
10. Show that if r is an irrational number, there is a unique integer n such that the
distance between r and n is less than 1/2.
11. Prove that n2 − 1 is divisible by 8 whenever n is an odd positive integer.
12. Prove that n3 − n is divisible by 3 whenever n is a positive integer.
13. Prove that 21 divides 4n+1 + 52n−1 whenever n is a positive integer.
14. A simple polygon with n sides, where n is an integer with n ≥ 3, can be triangulated
into n − 2 triangles.
15. Prove that the first player has a winning strategy for the game of Chomp, intro-
duced in the class, if the initial board is square (i.e., n × n for any positive integer
n).
16. Use mathematical induction to show that a rectangular checkerboard with an even
number of cells and two squares missing, one white and one black, can be covered
by dominoes.
