SKKU Discrete Mathematics

(Ch. 5, Introduction to Number Theory)

Prof : Sang-Gu Lee  at SKKU

http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm  Discrete Math Labs (실습실)

http://matrix.skku.ac.kr/2018-DM-PBL/      (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/  (PBL report Eng, 영문 보고서)

DM Ch. 3, Functions, Sequences, and Relations

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-3/
DM-Ch-3-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html
DM Ch. 3, 동영상강의
Functions, Sequences, and Relations 1
https://youtu.be/MhM_9ZuGAis
Functions, Sequences, and Relations 2  https://youtu.be/ZjAtN9HkZwM
Functions, Sequences, and Relations 3  https://youtu.be/Uuwsx2aiEPI

Midterm Exam Solutions : https://youtu.be/iAfQCycd6ac

 유형 Q & A 제목 P198 problem13 참여자 Answered by 칭기즈, finalized by 전종문, refinalized by 백선민 질문 Q. Is the relation {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)} an equivalence relation on {1,2,3,4}? Explain. 답변 A. Let, R = {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}​, X = {1,2,3,4}​. 1. ∀x ∈X, (x,x)​∈ R  ⇒   (1,1),(2,2),(3,3),(4,4)          ⇒ R​  is reflexive (a loop at every vertex).   2. (x,y)​∈ R ​,(y,x)​∈ R ​​​  ⇒  (1,2),(2,1) / (1,1) / (2,2) / (3,3) / (4,4)      ⇒​ R​  is symmetric (for every directed edge from v to w, there is a directed edge from w to v).​   3. (x,y)​∈ R ​,(y,z)​∈ R​  are (x,z)​∈ R ​ ⇒ (1,2) (2,1) are (1,1) /​ (1,2)(2,2)  are (1,2) ​/​ (1,1)(1,2) are (1,2)​  /​ (2,2)(2,1) are (2,1)​  ⇒​ R​  is transitive (there is a directed edge from x to y and a directed edge from y to z , there is a directed edge from x to z). ​ R​  is reflexive​, symmetric​, and transitive​.   ∴ {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)} is an equivalence relation on {1,2,3,4}.■​

 유형 Q & A 제목 Problem 6(Computer Exercises) 참여자 Solved by 칭기즈 Revised by 김정주 Finalized by 김희성 Final OK by SGLee 답변 Discussion For and are in the domain of the sequence. ,  sequence is increasing   Solution Python code: A=[int(x) for x in input("enter a sequence of numbers:\n").split()] count=1 count1=1 for i in range(len(A)-1): count+=1 if A[i]1]: count1+=1 if count==count1:  print("increasing") else: print("not increasing") Examples: because second and third elements are 2 -------------------------------------- When we check whether the given sequence is increasing, we have to check ​. But if ∃n such that ​ is not true, then we can tell it is not increasing. So if we find   ∃n such that ​ is not true, we quickly exit and print "not increasing".  If our program execute all n with all loops, and it doesn't find any exception, then we will print " increasing". Our syntax for that argument can be seen in the line 6. Our modified code is as following. import sys A=[int(x) for x in input("enter a sequence of numbers:\n").split()] for i in range(len(A)-1):   if A[i]>=A[i+1]:     print("not increasing")     sys.exit(0) print("increasing")

 유형 Q & A 제목 Problem 9(Computer Exercises) 참여자 Solved by 칭기즈 Finalized by 전종문 Re-Finalized by 칭기즈 질문 Q Write a program that tests whether A is nondecreasing 답변 A. Discussion  For and are in the domain of the sequence. ,  sequence is nondecreasing  increasing is replaced by nondecreasing : “ ” is replaced by “ ”  Solution: Python code:  A=[int(x) for x in input("enter a sequence of numbers:\n").split()] count=1 count1=1 for i in range(len(A)-1):   count+=1   if A[i]<=A[i+1]:     count1+=1 if count==count1:   print("nondecreasing") else:   print("not nondecreasing") Right Example Wrong example C code: #include int A, N, answer = 1; int main() { printf("Enter the number of sequence: "); scanf("%d", &N); printf("Enter a sequence: "); for (int i = 1; i < N; i++) { scanf("%d", &A[i]);} for (int i = 1; i < N; i++) { if (A[i - 1] > A[i]) { answer = -1; break; } } if (answer == 1) { printf("nondecreasing\n"); } else {  printf("not nondecreasing\n"); } return 0; }​

 유형 Q & A 제목 Problem 20 참여자 Solved by 오동찬 Finalized by Muhammad/모하메드​  Re-Finalized by 오동찬  Final OK by SGLee 질문 Q. Use the result of Exercise 19 to find the matrix of the relation R₂° R₁.​ +) Result of Exercise 19 ​ 답변 A. ​

 유형 Q & A 제목 Problem 19 참여자 Solved by 오동찬 Finalized by 만우흠 Re-Finalized by 오동찬 질문 Q. Use the result of Exercise 19 to find the matrix of the relation R₂° R₁.​ +) Result of Exercise 19  Find the matrix product A₁A₂. 답변 A. ​

 유형 Q & A 제목 Problem 18 참여자 Solved by 만우흠 Date: 2018.09.28 Finalized by 서명원 Date: 2018.09.29 Final OK by SGLee ​ 질문 Q. Exercises 18 and 19 refer to the sequence c1,c2,… defined by the equations. 답변 A. ​ When put n=2,  2C​2/2+2 = 2C​1 +2 = 2C​1 +​2 = 0+2 = 2    (because C​1 = 0)  Therefore, C​2​=2 When put n=3,  2C​​​3/2+2 = 2C​1.5​+3 = 2C​1​+3 = 0+3 = 3 (because C​1.5 = C​1 = 0)  Therefore, C​3=​3 When put n=4,  2C​4/2​​﻿​+4 = 2C​2+​4 = 2C​2​+4 = 2*2+4=8 (because C​2 = 2)  Therefore, C​4​=8 When put n=5,  2C​5/2​​+5 = 2C​2.5​+5 = 2C​2​+5 =2*2+5 = 9 (because C​2.5 = C​2 = 2)  Therefore, C​5​=9​ ​Solution:  C​2​=2, C​3=​3, C​4​=8, C​5​=9.

 유형 Q & A 제목 Problem 17 참여자 Solved by 만우흠 Date: 2018.09.28  Finalized by 서명원 Date: 2018.09.29 Final OK by SGLee 질문 Q. Exercises 17-20 refer to the relations R1 = {(1,x),(2,x),(2,y),(3,y)} R2 = {(x,a),(x,b),(y,a),(y,c)} 17. Find the matrix A1 of the relation R1 relative to the orderings 1, 2, 3; x, y. 답변 A. Let x={1,2,3}, y={x, y} and R1={(1, x),(2, x), (2, y), (3, y)} ∴A​1 =​ □

 유형 Q & A 제목 Problem 16 참여자 Solved by 김은율 Finalized by ​유가이 올렉산드르 Final OK by SGLee 질문 Let R be the relation defined on the set of eight-bit strings by s1 R s2 provided that s1 and s2 have the same number of zeros. ​(a) Show that R is an equivalence relation. (b) How many equivalence classes are there? (c) List one member of each equivalence class. 답변 A. (a) R is reflexive because any eight-bit string has the same number of zeros as itself.      R is symmetric because, if s1 and s2 have the same number of zeros, then s2   and s1 have the same number of zeros.     R is transitive. [Proof) Suppose that s1 and s2 have the same number of zeros and that s2 and s3 have the same number of zeros. Then s1 and s3 have the same number of zeros.]      Therefore, R is an equivalence relation.  (b) ​ There are nine equivalence ​classes.  (the set of eight-bit strings, The number of zeros can be   0, 1, 2, 3, 4, 5, 6, 7, 8) Small Supplement: You are right. There are nine equivalence classes - the class of strings with no zeros, the class of strings with 1 zero, the class of strings with 2 zeroes and so on. The number of zeros can be   0, 1, 2, 3, 4, 5, 6, 7, 8, so we have nine equivalence classes in general. (c) And now we can list one member of each equivalence class       11111111   is the only member of the class with no zeros.       11111110   is a member of the class with 1 zero.       11111100   is a member of the class with 2 zero.       11111000   is a member of the class with 3 zero.       11110000   is a member of the class with 4 zero.       11100000   is a member of the class with 5 zero.       11000000   is a member of the class with 6 zero.       10000000   is a member of the class with 7 zero.        00000000   is a member of the class with all zero members. ■

 유형 Q & A 제목 Problem 15 참여자 Solved by 정호진 Finalized by 엄자균 Final OK by SGLee 질문 Q. Find the equivalence relation (as a set of ordered pairs) on {a, b, c, d, e} whose equivalence classes are {a}, {b, d, e}, {c}. 답변 A. Given set is {a, b, c, d, e}.   Let R be an equivalence relation whose equivalence classes are {a}, {b, d, e}, {c} where ​ [a] = {a/(a,a) ∈ R}  [b] = [d] = [e] = {x/(b,x), (d,x), (e,x)∈ R} = {b, d, e}     [c] = {c/(c,c)∈ R } => R {(a,a), (b,b), (d,b), (e,b), (b,d), (d,d), (e,d), (b,e), (d,e), (e,e), (c,c) } ,  is an equivalence relation.

 유형 Q & A 제목 Problem 14 참여자 solved by 서명원finalized by 오동찬 Final OK by SGLee​ 질문 Q. Given that the relation {(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)} is an equivalence relation on {1,2,3,4}, find , the equivalence class containing 3. How many (distinct) equivalence classes are there? 답변 A. Draw graph with above problem set. In the graph above, we can see that we have two possible set can go to {3}. So,  = {3,4} =  and  = {1, 2} = .  There are two equivalence classes.

 유형 Q & A 제목 Problem 11 참여자 Solved by 정호진 Finalized by 칭기즈 Final OK by TA  2018.10.02​ 질문 Q. Give an example of a relation on {1, 2, 3, 4} that is reflexive, not antisymmetric, and not transitive. 답변 A. reflexive: (x,x) ∈ ​R​ for every x ∈​ X antisymmetric: for all x, y ∈​ X, if (x,y) ∈​ R and (y,x) ∈​ R, then x=y transitive: for all x, y, z ∈​ X, if (x,y) and (y,z) ∈​ R, then (x,z) ∈​ R So, (1,1), (2,2), (3,3), (4,4) ∈​ R​ (Reflexive)​ (2,3), (3,2) ∈ ​​R (not antisymmetirc) (1,2) ​∈​ R (not transitive)​ R = {(1,1), (2,2), (3,3), (4,4)​, (2,3), (3,2)​, (1,2)​} Digraph: 1. Every vertex has a loop so  R is reflexive ​2. (2,3) (3,2) ∈ ​​R:Directed line from 2 to 3 , Directed line from 3 to 2 but x≠y  R is not antisymmetric ​3.(1,2),(2,3) ∈ ​​R Directed line from 1 to 2, Directed line from 2 to 3 but there is no line from 1 to 3 R is not transitive

 유형 Q & A 제목 Problem 10 참여자 Solved by 김정주 Date:2018.09.30 Finalized by 칭기즈 Date:2018.09.30​ Re-Finalized by 전종문 Date:2018.09.30 Final OK by SGLee 질문 Q In Exercises 9 and 10, determine whether the relation defined on the set of positive integers is reflexive, symmetric, antisymmetric, transitive, and/or a partial order. 10. (x,y)∈R if 3 divides x + y 답변 A. *​   (1,1)∉ R  ⇒ R  ​is not reflexive​ *   If  3|x +y  then  3|y +x ​ ⇒ R  ​is symmetric ​*   ​R  is symmetric but R  is not reflexive ⇒  R ​is not antisymmetric *   ​(1,2)∈R , ​(2,1)∈R ⇒​  (1,1)∉ R  ⇒ R  ​is not transitive *   R is antisymmetric, transitive​ but R is not reflexive ⇒ R ​is not a partial order​ ∴ R is symmetric, not ​reflexive​,​ not antisymmetric, not transitive​, not a partial order

 유형 Q & A 제목 Problem 8 참여자 Solved by 엄자균 Date 2018.09.27 Revised by 정호진 Date 2018.09.28 Finalized by 전종문 Date 2018.09.28 Final OK by SGLee 질문 Q 8. Let α = ccddc and β = c³d². Find  (a) αβ   (b) βα   (c) |α​|   (d) |ααβα| 답변 A. α = ccddc ​, β = c³d² ​=​c​ccdd​ (a) αβ  = ccddc​c​ccdd​ (b) βα  = c​ccdd​​ccddc​ (c) |α|=  |ccddc| = 5 (d) |ααβα|= |ccddcccddcc​ccdd​​ccddc| =  20 Answer  (a) αβ ​= ccddc​c​ccdd​​  (b) βα  = c​ccdd​​ccddc​​  (c)  |α|= 5​  (d) |ααβα| ​=  20

 유형 Q & A 제목 Problem 7 참여자 Solved by 유가이 올렉산드르 Finalized by 오동찬 Final OK by SGLee 질문 Q Let bn = .    (a) Find b5 and b10     (b) Find a formula for bn      (c) Is bn  increasing?    (d) Is bn  decreasing? 답변 A. (a)  b5  = (1+1)2 – 12 + (2+1)2 – 22 + (3+1)2 – 32 + (4+1)2 – 42+ (5+1)2 – 52 = 35; b10  = (1+1)2 – 12 + (2+1)2 – 22 + (3+1)2 – 32 + (4+1)2 – 42 + +(5+1)2 – 52 +…… + (9+1)2 – 92 + (10+1)2 – 102 = 120; ■  (b) bn = (1+1)2 – 12 + (2+1)2 – 22 +…+ (in+1)2 – in2;         bn = = = = = n(2+n) = 2n + n2 = + 2n + 1 – 1  = (n+1)2 – 1;       ■​ (c)  Yes, because bn < bn+1 , for all n which n and n+1 are in domain of the sequence. ■​ (d)  No, because bn > bn+1 (bn is no bigger than bn+1), for all n which n and n+1 are in domain of the sequence. Or, since we show that bn  is increasing in question (c), so bn  is not decreasing.

 유형 Q & A 제목 Problem 6 참여자 solved by 엄자균 revised by 오동찬 Finalized by 오동찬 Final OK by SGLee 질문 답변 A. ​    유형 Q & A 제목 Problem 5 참여자 solved by 칭기즈 finalized by 신혜수 Final OK by SGLee 질문 For the sequence a defined by = 2*n + 2, find    (a) (b) (c) 답변 A.​ Solution : The answer: a) 14 b) 18 c) 192 유형 Q & A 제목 Problem 4 참여자 Solved by 오동찬 Date: 2018.09.27 Finalized by 서명원 Date: 2018.09.27 Re-Finalized by 오동찬 Date: 2018.09.29 Final OK by TA Date :  2018. 10. 02 질문 Q For the Hash function (                      h(x) = x  mod 13, show how the data  784, 281, 1141, 18, 1, 329, 620, 43, 31, 684 would be inserted in the order given in initially empty cells indexed 0 to 12.   ​+) In hash function, my using modulo operation, we can get output h(x) by input x. This means that we can index inputs to different outputs. Additionally, by choosing modulo number, in this case 13, we can put data to certain range of indexed(in this case 13-1 = 12 cases).  So, in this problem we get hash outputs(empty cells) from given data and stored them to 13 different empty cells. 답변 A. ​ By mod operation, we insert data as an x and get h(x) (or y) result. (x,y means "store item x in cell y.")  (784, 4), (281, 8), (1141,10) (18,5), (1,1), (329, 6), (620, 9), (43, 7), (31, 11), (684,12)   □ Hashing variable-length data[https://en.wikipedia.org/wiki/Hash_function) When the data values are long (or variable-length) character strings—such as personal names, web page addresses, or mail messages—their distribution is usually very uneven, with complicated dependencies. For example, text in any natural language has highly non-uniform distributions of characters, and character pairs, very characteristic of the language. For such data, it is prudent to use a hash function that depends on all characters of the string—and depends on each character in a different way. In cryptographic hash functions, a Merkle–Damgård construction is usually used. In general, the scheme for hashing such data is to break the input into a sequence of small units (bits, bytes, words, etc.) and combine all the units b, b, …, b[m] sequentially, as follows S ← S0;                         // Initialize the state. for k in 1, 2, ..., m do        // Scan the input data units:   S ← F(S, b[k]);               // Combine data unit k into the state. return G(S, n)                  // Extract the hash value from the state.  This schema is also used in many text checksum and fingerprint algorithms. The state variable S may be a 32- or 64-bit unsigned integer; in that case, S0 can be 0, and G(S,n) can be just S mod n. The best choice of F is a complex issue and depends on the nature of the data.

 유형 Q & A 제목 Problem 3 참여자 Solved by 유가이 올렉산드르 inalized by 유가이 올렉산드르 Final OK by SGLee 질문 Give examples of functions f and g such that f∘g   is onto, but g is not onto. 답변 A. ​ Define ​f: {0,1}→{0} by f (0) = f (1) = 0, and g: {0}→{0,1} by g (0) = 0. Then g is not onto because there is no preimage in the domain {0} of the value 1 which is in its range.  But f∘g is onto.   ​( because f∘g  : {0}→{0}  by   f∘g  (0) = f (0) = 0. which is a trivial bijective function.)

 유형 Q & A 제목 Problem 2 참여자 Solved by 유가이 올렉산드르, Date: 2018.09.30 Finalized by 오동찬, Date: 2018.09.30 Final OK by SGLee 질문 Find real numbfloor(x) * floor(y) = floor(xy) – 1 답변 A. ​  By definition, the floor of x, denoted , is the greatest integer less than or equal to x.  Therefore, we must choose two numbers (x and y), that satisfy the conditions floor(x) * floor(y) < floor(xy) -1. ​This means that when we multiply two numbers, their result should be unless '1' bigger then floor(x) * floor(y)​.  We may choose real numbers x=2.3 and y=5.1.  Since floor(2.3)  = 2 and floor(5.3)  = 5, ​ LHS = floor(x) * floor(y)​ becomes 10​  Since floor(xy) = floor(12.19) = 12 , RHS becomes 12-1 = 11.​​ We have found real numbers x=2.3 and y=5.1 satisfying floor(x) * floor(y) = floor(xy) – 1

## 코딩관련 solve한문제들

 유형 Q & A 제목 Ch 3 Problem 1 참여자 Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23 질문 Implement a hashing system for storing integers in an array. 답변 #include #include int main()​ {            int num;            printf("배열원소의 갯수를 입력하시오 : ");            scanf_s("%d", &num);            printf("배열을 입력하시오 : ");            int *arr = (int*)malloc(sizeof(int)*num);             //배열 동적할당            for (int i = 0; i < num; i++) {                      scanf_s("%d", &arr[i]);                        //반복문을 통한 배열입력            }            for (int i = 0; i < num; i++) {                      printf("%d", arr[i]);                      if (i != num - 1)                                 printf(" , ");                      else                                 printf("\n");            }            free(arr); }          ​  ​comment​   Hash function A hash function is any function that can be used to map data of arbitrary size to data of a fixed size. 해쉬 시스템에 대해서 공부하게 되었고, 해쉬함수가 무엇인지 알게 되었습니다.  유형 Q & A 제목 Ch 3 Problem 3 참여자 Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23 질문 Write a program that generates pse​udorandom Integers. pseudorandom : 의사난수​ 답변 #include int main()  {            int num = rand();            for(int i =0;i<5;i++)            printf("생성된 의사 난수 : %d\n", rand());            return 0; } but we can make Time-dependent random number​s.(Not pseudorandom​)   #include #include int main() {            srand((int)time(NULL));            for(int i=0;i<5;i++)            printf("생성된 난수 : %d\n",rand());   }  Comment Pseudo random number(의사 난수) 의사 난수란 컴퓨터에 의해 만들어지는 난수로서. (어떤 유한 개수의 조립된 수의 주기성 없는 계열을 난수라 한다) 산술 난수를 컴퓨터에 발생시키면 커다란 주기를 가지게 되는데 이와 같이 진정한 의미로는 난수가 아니지만 사용상 난수로 간주해도 지장이 없는 난수를 의사 난수라고 한다. 의사 난수를 무엇인지 이해했고 이를 이용해 문제를 풀어볼 수 있었다. 유형 Q & A 제목 Ch 3 Problem 8 참여자 Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23 질문 Write a program that tests whether A is nonincreasing 답변 #include #include int main() {            int num, count = 1;            printf("배열원소의 갯수를 입력하시오 : ");            scanf_s("%d", &num);            printf("배열을 입력하시오 : ");            int *arr = (int*)malloc(sizeof(int)*num);            //동적할당            for (int i = 0; i < num; i++) {                      scanf_s("%d", &arr[i]);                      //반복문을 통한 배열 입력            }            for (int i = 1; i < num; i++) {                      if (arr[i - 1] >= arr[i])                        //증감확인                                 count -= 1;            }            if (count == 1)                      printf("increasing\n");            else                      printf("nonincreasing\n");            free(arr);               }   1.increasing​  2.nonincreasing​ 유형 Q & A 제목 Ch 3 Problem 11 참여자 Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23 질문 Write a program to determine whether one string is a sub-string of another string. 답변 #include #include int main() {            int num, num1, count = 0, i, j;            printf("one string의 갯수를 입력하시오 : ");            scanf_s("%d", &num);            int *arr1 = (int*)malloc(sizeof(int)*num);            printf("one string을 입력하시오 : ");                         //one string 입력            for (i = 0; i < num; i++) {                      scanf_s("%d", &arr1[i]);            }            printf("sub string의 갯수를 입력하시오 : ");            scanf_s("%d", &num1);            int *arr2 = (int*)malloc(sizeof(int)*num1);            printf("sub string을 입력하시오 : ");            for (i = 0; i < num1; i++) {                      scanf_s("%d", &arr2[i]);            }            for (i = 0; i < num1; i++) {                      for (j = 0; j < num; j++) {                                 if (arr1[j] == arr2[i])                                           count += 1;                      }            }            if (count >= num1)                      printf("sub string\n");            else                      printf("non-sub string\n");            free(arr1);            free(arr2); }               1.Sub string​ 2. Non-sub string​ Comment  Sub string​에 대해서 알게 되었고, 코딩과 수학 사이 관계에 대해서 이해도가 한층 깊어졌습니다.

## …  한학기동안학생들의수많은질문에일일이대답해주시느라고생많으셨고감사드립니다!!

(The End of Ch 3)