Math 231 Winter 2020 Final Exam Study Guide Homework Solutions

This document presents solutions to a discrete mathematics homework assignment for a Math 231 course, likely at the university level, focusing on topics covered in chapters 1 through 5. The solutions cover a wide range of problems including set theory, combinatorics, circular arrangements, permutations, combinations, mathematical induction, number theory (base conversions, divisibility rules), and functions (injective, surjective, bijective). The solutions demonstrate the application of various formulas and theorems, providing step-by-step explanations and calculations for each problem. Problems involve calculating set operations, counting arrangements, proving mathematical statements using induction, and solving equations related to number theory and functions. The document offers a comprehensive guide to understanding and solving complex discrete mathematics problems, making it a valuable resource for students studying for the final exam.

Running head: MATHEMATICS 1
Discrete Mathematics
Name
Institution

MATHEMATICS 2
Solutions
Question 1
Let A, B, and C be sets of integers between 1 and 100000(inclusive) which are divisible by 31,
607, and 1901 respectively. As a result, we want to find;
( AUBUC )C
= | AUBUC| = | A| + |B| + |C | -( AnB ) - ( AnC ) -( AnBnC )
Where;
| A| = 100,000
31 = 3225
|B| = 100,000
607 = 164
|C | = 100,000
1901 = 52
( AnB ) = 100,000
18817 =5
( AnC ) = 100,000
58931 =1
|AUBUC| = 3225+164+52-5-1-2
= 96563
Question 2
Using the formula of circular arrangement of n-objects i.e. (n-1)!

MATHEMATICS 3
9 women will be (9-1)! = 8!, r =6, thus;
P (n,r) = n!
(n−r )! = 9 !
3 ! = 60480
=40320*60480
=2438553600 ways
Question 3
The main objective is to find the numbers of ways of different seating arrangements
=( 16
10 )
Circular arrangement for n-objects will therefore be;
(n-1)!
=(10-1)!
Remaining six people to be arranged on the six seats i.e. (6-1)!
Using the rule of product, we get;
(16
10 ) *9!*5! Ways of seating
Question 4
IIIIMPPSSSS
n=11
I=4, M =1, P=2, and S =4

MATHEMATICS 4
a) = 11!
4 !∗2 !∗4 ! 1 ! = 34650
b) Since I= 4, then n=8 we get;
= 8 !
1!∗1 !∗2!∗4 ! = 840
c) n=5
= 5!
2! = 60 words
d) = 11 !
4 ! 4 ! 2 ! = 34650 = = 1
34650 = 0.0002886
Question 5
We use two ways to determine the number of times the statement counted and executed i.e.
(n+3−1
3 ) = (n+ 2
3 ) times (i+1
2 ) executions of the I, j thus;
( n+2 ) ( n+1 ) n
3 =∑
i=1
n
( i+1
2 )
∑
i=1
n
i = ( n+1 ) n
2
∑
i=1
n
i2= ( n+2 ) ( n+1 ) n
3 - ( n+1 ) n
2
= ( n+1 ) n
6 (2n+1)
( n+ 2
3 )= ∑
i=1
n
( i+1
2 )

MATHEMATICS 5
= ( n+ 2 ) !
3! ( n−1 ) !
( n+2 ) ( n+1 ) (n)
6
= ( 2
2 ) + ( 3
2 ) +-------+ ( n+1
2 )
= ½ (2+6+12+------ (n+1)(n))
= ( n+2 ) ( n+1 ) (n)
6
=1/2 ∑
i=1
n
(i+1 )i
Question 6
X1+ X2+ X3+ X4+ X5+ X6+ X7+ X8+ X9= 27
= X1-1+ X2-1+ X3-1+ X4-1+ X5-1+ X6-1+ X7-1+ X8-1+ X9-1=18
=Consider a= X1-1, b= X2-1, c= X3-1, --------, i= X9-1
=a+b+c+ --------------+i =18
=We therefore know that the number of the solution of the first equation where x1 to x9 cannot
be zero thus equation 2 also cannot be zero. As a result, using the fictious partition method;
(n+ p−1
p−1 ) = (18+9−1
9−1 ) where n=18 and p =9
¿ ( 26
8 ) = 26 !
8 !(26−8)!

MATHEMATICS 6
=1562275
Question 7
X1+ X2+ X3+ X4+ X5+ X6+ X7=23
(n+ p−1
p−1 ) = (23+7−1
7−1 ) where n=23 and p =7
¿ ( 26
8 ) = 23 !
6 !(26−4 )!
=10925460
Question 8
∑
j=0
n
(n
j )2j = 3n
By induction, the statement is true when n =0, thus checking on the Left hand side and Right
hand side, we get;
∑
j=0
n
(0
0 )20 =30
This is true since the LHS and the RHS are equal thus holding the claim true to the statement.
∑
j=0
k +1
(k +1
j )20 =3k+1
=3 thus showing that the LHS and the RHS are equal leading to approve of the theorem.
Question 9
A, B, C є U

MATHEMATICS 7
(A-B) є C ≅ (A-C) є B
Let x є (A-B)n C then x єA-B and x єC by definition
In particular, x є (A-C) n B
Question 10
(A n B) u C = An (B u C) ≅ c є A
Let x є (A n B) U C then x є A n B, and that (A n B) U C = A n (B u C) = C є A since x є A and
x є C
Question 11
a) A∆ B =B ∆ A
Let x є B and x є A thus x є (A u B) showing that (A-B) u (B-A) will have A∆ B = B ∆ A
b) A ∆ A’ = U
Let x є A and also since A and A’ є U then A ∆ A’ = U
c) A ∆ U = A’
Let x є A but since we know that A є U and A’ є U then A and A’ є U thus A ∆ U = A’
d) A∆ ∅ =A
Let x є and given that ∅ is null set, then x є A but empty set will not have anything. As a
result,
A∆ ∅ =A
Question 12
( n+ 2
r ) = (n
r ) + 2 ( n
r −1 ) + ( n
r −2 )

MATHEMATICS 8
From the above given combination, the left hand side counts the number of bit strings of the
length n+2 with r ones. The right hand side counts for the same string according to the cases but
depending on the position of the right hand side. As a result, it must be in one of the positions r,
r-1, or n+2. However, if it is in the position t, then r of the t+1 position will hold on the right
hand side to a value equal to 1. A s result, the number of the bit strings where the right hand side
is 1 is in the position t if t-1 where the rightness also holds to 1 at a point where k =t-1. It
therefore follows the rule of the summation from the combination point of view.
Question 13
a) 2017
2017 (base 10) = base 2: 11111100001
2017 (base 10) = base 8: 3741
2017 (base 10) = base 16: 7e1
b) 2018
2018 (base 10) = base 2: 11111100110
2018 (base 10) = base 8: 3742
2018 (base 10) = base 16: 7e2
c) 2019
2019 (base 10) = base 2: 11111100011
2019 (base 10) = base 8: 3743

MATHEMATICS 9
2019 (base 10) = base 16: 7e3
d) 2020
2020 (base 10) = base 2: 11111100011
2020 (base 10) = base 8: 11111100100
2020 (base 10) = base 16: 7e4
Question 14
a) n = apbq for p and q where the powers are included and one
(p+1)
b) n = zpn
n+1 positive integers
c) (p+1) (q+1)
=(p+1)(q+1) = 6 factors
d) Let n =pn*qm where p and q are prime factors, thus positive divisors will be (n+1)(m+1)
e) 34.11 = 4+1 = 5
f) 23.54.73 = (3+4)(3+3)(4+3) = 756
Question 15
a) C(p,r) is a multiple of p
Using Fermat little theorem;
rp= r mode p
rp-1 =mod p = rp-1-1 thus a multiple of p

MATHEMATICS 10
b) If np-n is divisible of p
This can be shown by stating that;
Using the Fermat little theorem, we say that if p is a prime number, then for any positive integer,
n we will have np =n mod p
Question 16
nєZ+, n = rk.10k +ro
2=-1 (mod 3)=10k≡ (-1)k (mod 3) for all k>0
Using the base 10, we will have;
n= rk.10k +……..+r1.10 +r0 which is not equal to zero
Therefore;
3|n=n≡ mod 3
rk(-1)k+ rk-1(-1)k-1+ ………..+r1+r0 ≡0 (mod 3)
Question 17
7|n if and only if 7| n−ro
10 -2ro
If n is an integer, then the unit digit of 7n is 7 if and only if n is odd and 6 is an even number. If
we say that n=1 and ro is 7 respectively, then the final value of the 7|n if and only if 7| n−ro
10 -
2ro will given integer that proves that n>0 thus holding the inequality true.
Question 18

MATHEMATICS 11
Since (a,b) =d, we know that there are x,y є Z such that ax1 +by1 =d, then ( a
d )x1 +( b
d )y1 and a
d ,
and b
d is in Z. As a result, we say that ( a
d , b
d ¿=1 because if we suppose that it is true, then it will
be ( a
d , b
d ¿= ∂>1. From the relationship given, since ∂ divide the LHS, then equation ( a
d )x1 +
( b
d )y1 holds for ( a
d , b
d ¿= ∂>1
Question 19
a,b є Z+ and d =gcd (a,b).
By hypothesis, there exist integers m, n which are in Z such that d = am+bn
However, if c divides both a and b, then by Fermat little theorem, c will also divide d by the
same application thus d=gcd (a,b) and d2 is therefore a divisible of ab
Question 20
2020x+2019y=1
By the Euclidian Algorithm, 2020.1+2019.1=1
Subtracting 2019 by 1, we get 2019
(2019.-1). 2019. (2020.1+2019.1) thus, x=1, and y=-1
Question 21
2020x+1848y=16
By the Euclidian Algorithm,
2020.1+1848.1=172

MATHEMATICS 12
Subtracting 1848 by 172, we get 10 times
(1848.-1). 10. (2020.1+1848.1)
Subtracting 172 by 128, we get it to be once
Thus x=10, y=-33
Question 22
a
7 + b
12 = 1
84
12a+7b =84
By the Euclidian Algorithm,
12.1+7.1 =5
Subtracting 7 by 5, we get 1
(12.1)-1(12.1+7.1)
12.-1(12.1+7.1)
12.-1 +7.3=9
Subtract 5 by 9 we get 1, then;
(12.1 +7.-1) -1 (12.-1+7.3) showing that a=4 and b=-6
Question 23
The function will be;
20x+50y=1020