Discrete Mathematics, Summer 2002

 

Quiz #2

 

Problem 1.

 

Prove or give counterexample to the following statement: The sum of any even and odd integer is odd

 

Solution.

 

The statement is true. We take any even number, which can be written as 2a, then we take any odd number, which can be written as 2b+1. The sum of these two numbers is 2a + 2b+1 = 2(a + b) + 1, which is an odd number.

 

Problem 2.

 

Show that 6.3215215215… is a rational number.

 

Solution.

 

Let n = 6.3215215215… Then 10n = 63.215215215… and 10000n = 63215.215215… Subtracting 10n from 10000n, we obtain: 9990n = 63152, thus n = 63152 / 9990, which shows that n is rational. It is true that the fraction representing n could be simplified further, but what we have done is enough to establish that n is rational as required.

 

Problem 3.

 

Two athletes run a circular track at a steady pace so that the first completes one round in eight minutes and the second in 10 minutes. If they both start from the same spot at 9 am, when will be the first time they return to the start together?

 

Solution.

 

We just need to find the least common multiplier of 8 and 10 and this will tell us when two athletes will meet again. Hence, the answer is 9:40am.

 

Problem 4.

 

Show that the square of any integer can never have remainder 2 when divided by 3.

 

Solution.

 

Any number n can have one of the following three representations:

1)      n = 3q

2)      n = 3q + 1

3)      n = 3q + 2

 

First case gives: n2 = 9q2 = 3 * (3q2) + 0

Second case gives: n2 = 9q2 + 6q + 1 = 3 * (3q2 + 2q) + 1

Third case gives: n2 = 9q2 + 12q + 4 = 3 * (3q2 + 4q + 1) + 1

 

As we can see in all three cases we never get a remainder which equals 2.

 

Problem 5.

 

Is it true or false that for all real numbers x: λx2ϋ = λxϋ2?

 

Solution.

 

The statement is false: Counter-example: x = 1.5

 

λ1.52ϋ = λ2.25ϋ = 2

λ1.5ϋ2 = 12 = 1

 

Problem 6.

 

Prove or give counterexample to the following statement: The product of any two irrational numbers is irrational.

 

Solution.

 

The statement is false: Counter example: sqrt(2) * sqrt(2) = 2, where sqrt is a square root

 

Problem 7.

 

Given that a, b, and c are odd integers, can the following equation have rational solutions: ax2 + bx + c = 0?

 

Solution.

 

Suppose that there exists rational solution to the equation x = p/q. We note that since gcd(p, q) = 1, we conclude that p and q both cannot be even numbers.

a(p/q)2 + b(p/q) + c = 0 or ap2 + bpq + cq2 = 0

 

Let’s consider three possible cases:

1)      p is odd, q is odd: ap2 is odd, bpq is odd, cq2 is odd, some of three odd numbers is odd, but 0 is even

2)      p is odd, q is even: ap2 is odd, bpq is even, cq2 is even, some of one odd number and two even numbers is odd, but 0 is even

3)      p is even, q is odd: ap2 is even, bpq is even, cq2 is odd, some of one odd number and two even numbers is odd, but 0 is even

 

Thus, we conclude that all possibilities lead to a contradiction, hence the assumption about the existence of a rational solution is false.

 

Problem 8.

 

Find lcm(24, 36).

 

Solution.

 

72

 

Problem 9.

 

Simplify: n!/(n-2)!

 

Solution.

 

n(n – 1)

 

Problem 10.

 

Prove using mathematical induction that for all integers n greater than 1:

 

(1 – 1/22)(1 – 1/32)…(1 – 1/n2) = (n + 1) / 2n

 

Solution.

 

Base case n = 2: left hand side = (1 – 1/22) = Ύ, right hand side = (2 + 1) / (2 * 2 ) = Ύ

Assumption is that (1 – 1/22)(1 – 1/32)…(1 – 1/n2) = (n + 1) / 2n

We need to show that (1 – 1/22)(1 – 1/32)…(1 – 1/n2) (1 – 1/(n+1)2) = (n + 2) / 2(n+1)

 

(1 – 1/22)(1 – 1/32)…(1 – 1/n2) (1 – 1/(n+1)2) = ((n + 1) / 2n) * (1 – 1/(n+1)2) =

((n + 1) / 2n) * (n2 + 2n) / (n+1)2) = (n + 2) / 2(n+1) as needed

 

Problem 11.

 

Prove any way possible that for all integers greater than 1:

 

sqrt(n) < 1 / sqrt(1) + 1 / sqrt(2) + … + 1 / sqrt(n), where sqrt stands for the square root.

 

Solution 1 (Mathematical Induction)

 

Base case n = 2: left hand side = sqrt(2), right hand side = 1 + 1 /sqrt(2) = (sqrt(2) + 1) / sqrt(2) > (1 + 1) / sqrt(2) = sqrt(2) = left hand side

Assumption is that sqrt(n) < 1 / sqrt(1) + 1 / sqrt(2) + … + 1/ sqrt(n)

We need to show that sqrt(n + 1) < 1 / sqrt(1) + 1 / sqrt(2) + … + 1 / sqrt(n) + 1 / sqrt(n + 1)

 

1 / sqrt(1) + 1 / sqrt(2) + … + 1 / sqrt(n) + 1 / sqrt(n + 1) > sqrt(n) + 1 / sqrt(n + 1)

 

Thus, it is enough for us to show that sqrt(n) + 1 / sqrt(n + 1) > sqrt(n + 1) or equivalently sqrt(n + 1) - sqrt(n) < 1 / sqrt(n + 1)

 

sqrt(n + 1) - sqrt(n) = (sqrt(n + 1) - sqrt(n)) * (sqrt(n + 1) + sqrt(n)) / (sqrt(n + 1) + sqrt(n)) = 1 / (sqrt(n + 1) + sqrt(n)) < 1 / sqrt(n + 1)

 

Solution 2.

 

Simple algebra leads to a much faster proof:

 

1 / sqrt(1) + 1 / sqrt(2) + … + 1 / sqrt(n) > 1 / sqrt(n) + 1 / sqrt(n) + … + 1 / sqrt(n) = n / sqrt(n) = sqrt(n)

 

Problem 12.

 

Explain why the following cannot be a valid principal of a mathematical induction:

 

We are given predicate P(n)

 

  1. Base case: P(0), P(1), P(2) are all true
  2. Given that P(k) is true, one can show that P(3k) is true as well for all positive k

 

Conclusion: P(n) is true for all n

 

Solution.

 

The proposed above is not a valid principal of mathematical induction, because there is no way to show that P(4) is true.