COMPSCI 120 S2 2019 Assignment 2 Solution: Modular Arithmetic & Sets

This document presents a student's solution to COMPSCI 120 Assignment 2, covering key concepts in discrete mathematics. The solution addresses three problems: modular arithmetic, set theory, and combinatorics. The modular arithmetic section includes proofs and disproofs of statements relate...Read More

COMPUTER SCIENCE
STUDENT ID:
[Pick the date]

Question 1
(a) Here a, b, m, n € Z and also, m>0 and n>0
Let
a = b (mod n)
From definition a- b = k n (for some random integer k)
Now, m | n
n = m p (for some random integer p)
Thus,
a-b = k (m p)
After using associative and commutative properties of the product of the integers.
a-b = m (k p)
Here, as k and p are the integers and k p is also an integer thus, a -b would be integral
multiple of the m. In mathematical expression m | a-b
Therefore,
a = b (mod n)
(b) Prove / Disprove of statements
(i) If a = b mod m, a2=b2 mod m
Here,
a = b mod m → a-b =0 mod m
Such that
a2 – b2 = (a-b) (a+b) = 0 mod m → a2 =b2 mod m
Hence, it can be said that the above statement is true.
2

(ii) If a2= b2 mod m, a = b mod m
As, m| (a2 – b2) and a2 – b2 = (a-b) (a+b)
As a result of this, m | (a-b) or m |(a+b)
Thus,
a = ±b hence, it can be that the above statement is false.
(iii) If a = b mod m, a2 = b2 mod m2
As, m| (a2 – b2) and a2 – b2 = (a-b) (a+b)
As a result of this, m | (a-b) or m |(a+b)
Further squaring a = b mod m, it is apparent that the given statement is true.
(c) The given numbers in the numerator can be represented as follows.
100 = (99+1)
101 = (99+2)
102 = (99+3)
103 = (99+4)
Hence, the given expression is [(99+1)*(99+2)*(99+3)*(99+4)]/99
On multiplying the above four terms in the numerator, all the resultant terms would be
multiple of 99 except the term 1*2*3*4 or 24. Since all the other terms would be multiple of
99, hence these would be perfectly divisible by 99 leaving 24 as the remainder.
Thus, the requisite remainder is 24.
(d) (10011001)/3 = (999+2)1001/3
3

The numerator (999+2)1001 can be expanded using binomial theorem. In the resultant
expression, there is only one term i.e. 21001 which is not divisible by 3 as other terms would
contain non-zero power of 999 which is divisible by 3.
Hence, from the remainder perspective the above expression gets reduced to 21001/3
21001/3 = (3-1)1001/3
Again (3-1)1001 can be expanded using binomial theorem. In the resultant expression, there is
only one term i.e. (-1)1001 which is not divisible by 3 as other terms would contain non-zero
power of 3 which is divisible by 3.
Hence, from the remainder perspective the above expression gets reduced to (-1)1001/3
(-1)1001/3 = (-1)/3
Since remainders cannot be negative, hence the remainder is -1+3 = 2. The addition of 3 can
be explained as the divisor is 3.
Thus, the requisite remainder is 2.
Question 2
(a) Given sets
A= { −3 ,−2 ,−1, 0 , 1 ,2 , 3 }
B= {−4 ,−2 ,2 , 4 }
Cardinality of sets
(i) A U B = {-3, -2, -1, 0, 1, 2, 3, -4, 4} and hence, Cardinality of set = 9
(ii) A B = {-2, 2}⋂ and hence, Cardinality of set =2
(iii) (A B) U A =⋂ {-3,-2, -1, 0, 1, 2, 3}and hence, Cardinality of set = 7
(iv) A\B = A - A B = {-3, -1, 0, 1, 3}⋂ and hence, Cardinality of set = 5
(v) B\A = B – A B = {-4, 4}⋂ and hence, Cardinality of set = 2
(vi) A U A U A = {-3, -2, -1, 0, 1, 2, 3}and hence, Cardinality of set = 7
4

(b) A, B and C are the three sets and |A U B| = |A| + |B| - |A B|⋂ and the cardinality of
union A U B U C needs to be determined.
Set of elements exists in A can be represented as (A-B)
Set of elements exists in B can be represented as (B-A)
Set of elements exists in both A and B can be represented asA B⋂
Therefore,
A U B = (A-B) U (B-A) U (A B)⋂
Now, cardinalities of the two sides of the equation would be equated and then with the help
of simple pull for the cardinality of disjoint union is computed as shown below.
|A U B| = |A-B| + |B-A| + |A B| …………………. (eq. 1)⋂
Here,
A is a disjoint union of the A- B and A B and therefore,⋂
|A| = |A-B| + |A B|⋂
Now,
|A-B| = |A|- |A B|⋂
Similarly,
|B-A| = |B| - |A B|⋂
From eq. 1
|A U B| = |A| - |A B| + |B| - |A B|⋂ ⋂ + |A B|⋂
|A U B| = |A| + |B| - |A B|⋂
Further,
A U B U C = A U (B U C)
Hence,
|A U B U C| = |A U (B U C) | = |A| + |B U C| - | A (B U) |⋂
Here,
5

|B U C| = |B| + |C| - | B C|⋂
Thus,
|A U B U C| =|A| + |B| + |C| - | B C| - | A (B U) | …………………….. (eq.2)⋂ ⋂
Also,
|A U (B U C) | = (A B) U (A C) = | (A B) U (A C) |⋂ ⋂ ⋂ ⋂
|A U (B U C) | = |A B| + | A C| - |A B C|⋂ ⋂ ⋂ ⋂
From equation 2
|A U B U C| = |A| + |B| + |C| - | B C| -|A B| - | A C| + |A B C|⋂ ⋂ ⋂ ⋂ ⋂
Hence, thecardinality of union A U B U C
|A U B U C| = |A| + |B| + |C| - | B C| - |A B| - | A C| + |A B C|⋂ ⋂ ⋂ ⋂ ⋂
(c) A and B are the two sets and A (A U B) = A needs to be proven⋂
Let
x € A (A U B)⋂
Hence,
x € A and x € (A U B)
x € A and x € A or x € B
x € A
Therefore,
x € A (A U B) = x € A⋂
Now,
A (A U B)⋂ C A ………………….. (eq. 1)
Let
y € A
6

y € A and (y € A or y € B)
y € A and y € (A U B)
y € A (A U B)⋂
y € A = y € A (A U B⋂
A C A (A U B)………………….. (eq. 2)⋂
Based on equations 1 and 2
A (A U B) = A (Proved)⋂
Question 3
(a) User-codes on computer consist 3 letters which are followed by the three digits and
followed by a letter.
Assumption: No distinction between lower and upper-case letters.
(i) Number of different user-codes that can be constructed altogether
The first character of user-codes would be selected among the 26 letters of the alphabets.
Similarly, the second character and third character would be chosen. Further, the fourth
character, fifth character and the sixth character would also be selected from 10 digits.
Finally, the seventh character would be chosen from 26 letters. Hence, the total number of
different user-codes is computed as shown below.
Different user−codes=26∗26∗26∗10∗10∗10∗26=456,976,000
(ii) Number of user-codes that digits 0 would occur at least once
In order to find the number of user-codes that contain at least one zero would be determined
by eliminating the number of user-codes which do not have zeroes from total number of
different user-codes computed in part (i). Here, when no zeroes are permissible then there
would be nine choices would be left for each of the digit. Hence, the total number of user-
codes with has no zeroes is computed as shown below.
7

User−codes with no zeroes=26∗26∗26∗9∗9∗9∗26=333,135,504
Therefore,
Number of user-codes contains at least one zero = 456,976,000−333,135,504=123,840,496
(b) The requisite condition to be met is that the birth month ought to be same.
P(two or more share the same birth month) + P(two or more do not share the same birth
month) = 1
Hence, P(two or more share the same birth month) = 1- P(two or more do not share the same
birth month)
Requisite probability = 1- [(12/12)*(11/12)*(10/12)…..]
For requisite probability to be 0.5, [(12/12)*(11/12)*(10/12)…..] = 0.5
For this to happen, (12Cn)/12n = 0.5
Solving the above, minimum value of n =3
(c) There are 5 alphabets in QUIRK without repetition and these can be arranged in 5! ways
or 120.
(d) Consider Q and U to be a single entity as QU. Besides there are three other alphabets
namely I,R and K. The four entities can be arranged in 4! or 24 ways.
(e) In the given case Q and U can be arranged in 2 ways namely QU and UQ. Hence, the total
possible arrangements would be 4!*2= 24*2= 48 ways
8