Maths for Computing

Tutorial 3
1. Prove that if a is rational and a b is irrational, then b is irrational.
Solution: We will prove it by contradiction. Assume that a is rational and a b is irrational and b is
rational. But if a and b are rational, then a b is also rational, which is a contradiction as we have
assumed that a b is irrational. Hence, if a is rational and a b is irrational, then b is irrational.

2. Prove that 3 is irrational.

Solution: Assume 3 is rational. Then,
3 = a /b, (1)
+
where a, b ∈ ℤ such that a and b have no common factors.

Squaring (1) on both sides and rearranging gives us 3b 2 = a 2. This implies that 3 is a factor of
a 2. Since 3 is a prime, 3 should also a be a factor of a, i.e., a = 3k. Replace a with 3k in
3b 2 = a 2. We will get b 2 = 3k 2, which implies that b has 3 as a factor using similar reasoning as
we did for a. But this is a contradiction. In (1) we assumed that a and b have no common factors,
but now we have shown that they have a common factor 3. Hence, 3 is irrational.

3. Prove that if n is a perfect square, then n

+ 2 is not a perfect square.
Solution: We will do a proof by contradiction. Assume that n and n + 2 are perfect squares.

Then,
n = k2 (1)
n + 2 = l2 (2)
where k and l and non-negative integers.

Subtracting (2) from (1) gives us:

2 = l2 − k2
2 = (l + k)(l − k)

This implies that (l+ k) is a divisor of 2. But among all possible values of l and k where l + k is a
divisor of 2, none gives l 2 − k 2 = 2. Hence, we have found a contradiction. Therefore, if n is a
perfect square, then n + 2 is not a perfect square.

4. Suppose a, b, c ∈ ℤ. Prove that if a 2 + b 2 = c 2, then at least one of a and b must be even.

Solution: We will do a proof by contradiction. Assume that a 2 + b 2 = c 2 and both a and b are
odd. Let a = 2k + 1 and b = 2k′ + 1 and replace a and b in a 2 + b 2 = c 2.















































































 a2 + b2 = c2
(2k + 1)2 + (2k′ + 1)2 = c 2
4k 2 + 4k + 1 + 4k ′2 + 4k′ + 1 = c 2
4(k 2 + k + k ′2 + k′) + 2 = c 2
2.(2l + 1) = c 2

This implies that c 2 is even and hence c is also even. Let c = 2j for some j ∈ ℤ and replace c
with 2j in 2.(2l + 1) = c 2.
2.(2l + 1) = (2j )2
(2l + 1) = 2j 2

The above equation is a contradiction as LHS is odd and RHS is even. Hence, if a 2 + b 2 = c 2,
then at least one of a and b must be even.

5. Prove that if the rst 10 positive integers are placed around a circle, in any order, there exist
three integers in consecutive locations around the circle that have a sum greater than or equal to
17.
Solution: (The ow of the proof is di erent from the one we discussed. The one given below was
shown to me by one student in the second session.)
A long exhaustive proof is possible but there is a better proof by contradiction. Suppose we can
arrange rst 10 positive integers around a circle such that no three consecutive integers’ sum ≥
17. Suppose the 10 integers are named as a1, a2, a3, …, a10 such that ai+1 has ai before it and
ai+2 after it (a1 is after a10). Since no three consecutive integers’ sum is more than 17, we can
say that ai + ai+1 + ai+2 ≤ 16, for i ∈ [1,8], a 9 + a10 + a1 ≤ 16 and a10 + a1 + a 2 ≤ 16.
If we sum these eight inequalities we will get 3(a1 + a 2 + … + a10 ) ≤ 160 as every ai appears in
three inequalities, which is a contradiction as a1 + a 2 + … + a10 = 55.

6. Suppose that ve ones and four zeros are arranged around a circle. Between any two equal bits
you insert a 0 and between any two unequal bits you insert a 1 to produce nine new bits. Then
you erase the nine original bits. Show that when you iterate this procedure, you can never get nine
zeros.
Solution: It’s a proof by contradiction. Suppose we reach nine zeros for the rst time by
repeatedly applying the given operation. Now, we can get nine zeros only if in the previous step
we had nine zeros or nine ones. Nine zeros in the previous step is not possible as we have got
nine zeros for the rst time. Let’s name the nine ones in the previous step as b1, b2, …, b9 in
clockwise order and the bits in the step before the previous steps as a1, a 2…, a 9 such that bi was
inserted between ai and ai+1 (b9 was inserted between a 9 and a1). Clearly, ais should be
alternation bits. But, if a1 is 0, then a 9 will also be 0 and if a1 is 1, then a 9 will also be 1. In both
the cases b9 cannot be 1. Hence, it is a contradiction. Therefore, we can never get nine zeros.















fi





fl
fi


fi
fi













ff





















fi









 7. Write the numbers 1,2,3,…,2n on a board, where n is an odd integer. Pick any two of the
numbers, j and k, write | j − k | on the board and erase j and k. Continue this process until only
one integer is written on the board. Prove that this integer must be odd.
Solution: For any odd integer n, the sum of integers from 1 to 2n is odd as (2n * (2n + 1))/2 is
an odd number. We will now prove that the sum of integers will remain odd after every operation,
that is, erasing two numbers j and k and writing | j − k | . This is su cient to prove that the last
integer will be an odd integer as when a single number is written on the board the sum of the
numbers and the single number will have the same parity.

We will only analyse the two cases when both j and k are odd and j is odd and k is even. The
other cases are very similar to them.

Case 1: Both j and k are odd

Let sum denote the sum of all the numbers before the operation. Then the sum of all the numbers
after the operation is sum− ( j + k) + | j − k | which is clearly an odd number as we are
subtracting and adding even numbers to sum.

Case 2: j is an odd number and k is an even number

Again, let sum denote the sum of all the numbers before the operation. Then the sum of all the
numbers after the operation is sum− ( j + k) + | j − k | which is clearly an odd number as we
are subtracting and adding odd numbers to sum.


























ffi