Discrete and Foundational Mathematics I
Discrete and Foundational Mathematics I MATH 187
Popular in Course
Popular in Mathematics (M)
This 9 page Study Guide was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Study Guide belongs to MATH 187 at Boise State University taught by Melvin Holmes in Fall. Since its upload, it has received 30 views. For similar materials see /class/217990/math-187-boise-state-university in Mathematics (M) at Boise State University.
Reviews for Discrete and Foundational Mathematics I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/03/15
Study Problems for Test III with Solutions Dr Holmes April 1 2004 This document is certainly much longer than the test Nor is there any guarantee that the coverage is exactly the same that on the test Some of the individual problems are harder than any individual test question is likely to be but they should help you to think about the right things This document does not give complete coverage for chapter 10 though it does have some chapter 10 questions for full chapter 10 coverage also look at assignment XII The test starts with the construction of the integers in chapter 7 and continues through section 105 Solutions will be posted on the web on Wednesday afternoon or Thursday 1 Prove using the representation of the integers in chapter 7 that the square of any integer is either zero or positive By a is positive I mean a gt 0 Your proof should reduce entirely to calculations with natural numbers only plus applications of the de nitions of gt and multiplication on the represented integers Solution An integer is written an equivalence class m 71 for some natural numbers m and 71 Using the de nition of multiplication we nd that m 71 m 71 lm2 712 2mm 11 is the integer 0 lm2 712 2mm 2 1 1 means m2 712 1 2 27mm 1 or equivalently m2 n2 gt 2mm This uses the de nition of order for represented integers Suppose m gt 72 D S Then we have m 712 m2 27mm 712 a natural number so m2 712 must be greater than 27mm Suppose 72 gt m Then we have 72 m2 722 2mm m2 a natural number and once again m2 722 gt 2mm If m 71 it follows that mn is the integer zero and its square is zero This is actually quite tricky it is hard to see what you are allowed to do Don t expect anything this hard Ionvert 153w to base 8 Solution 153 divided by 8 is 19 remainder 1 19 divided by 8 is 2 remainder 3 2 divided by 8 is 0 remainder 3 The answer is 2318 Convert 2348 to base 10 Solution 282384156 Give the complete addition and multiplication tables for mod 4 arith metic Give the complete addition and multiplication tables for base 4 Notice that these are not the same thing Convert 27 and 45 to base 4 Carry out the calculations 2745 and 2745 in base 4 Convert your results back to base 10 and check that you have the right answers 27 1683 1234 45 32121 2314 adding 1 1 12 3 2 31 10 2 0 and you can check that 244572 10204 and 1023334 1215 123 231 123 112021 31112 102333 27mm 45ten 4 C Compute gcd6105 21390 21390 divided by 6105 is 3 remainder 3075 6105 divided by 3075 is 1 remainder 3030 3075 divided by 3030 is 1 remainder 45 3030 divided by 45 is 67 remainder 15 45 divided by 15 is 3 remainder 0 So the gcd is 15 Determine integers m and 71 such that 6105m21390n gcd6105 21390 21390 36105 3075 3030 6105 3075 6105 21390 36105 46105 21390 45 3075 3030 21390 36105 46105 21390 221390 76105 15 3030 6745 46105 21390 67221390 76105 4 6776105 1 67221390 4736105 13521390 So gcd213906105 15 4736105 13521390 Find integers m and 71 such that 6105M 2139071 20 if possible If it is not possible explain Why not It can t be done since 15 doesn t go evenly into 20 Find integers m and 71 such that 6105M 2139071 30 if possible If it is not possible explain Why not 30 2 215 2 24736105 213521390 9466105 27021390 There is a theorem which that ifp is a prime and p bc then either p a p b or p c Show that this is not necessarily true ifp is not a prime choose values of p a b c such that pain and none of the statements p a p b and p c are true For example consider 30 which goes evenly into 925 900 but doesn t go evenly into either 4 9 or 25 the idea is that the prime factors of 30 2 3 5 each go evenly into different factors in the product 6 1 9 Give an argument based on prime factorizations to show that no frac tion with a and 6 positive integers can be a square root of 3 Hint a2 and 62 must each have an even number of factors of 3 in their prime factorizations why Now think about cancelling factors of 3 in Since the number of factors of 3 in the numerator a2 and the number of factors of three in the denominator b2 are both even twice the number of factors in a and twice the number of factors in b the number of factors of 3 in the numerator of the simpli ed fraction 2 must also be even which is not possible if the quotient is to be equal to 3 So there can be no a and b in the natural numbers such that 2 3 If c ab and a 2 V E then b 3 must be true Use this fact to show that if c has no prime factor 3 V E then it must be a prime number itself Carefully explain why this is true it does take a little bit of care The argument proving the contrapositive should begin suppose that c is not a prime number Then 0 ab with neither a not 6 equal to c or 1 Solution If 0 is not a prime then 0 ab for some a and b neither of which is equal to 1 Suppose a is the smaller of the two numbers it cannot be greater than or our fact would make 6 lt and so a would not be the smaller of the two a may not be a prime itself but because it is not equal to 1 it has a prime factor and this prime factor is g a and so less than or equal to IfI want to check whether 1000001 is a prime what is an upper limit on how large the smallest prime factor of 1000001 could be The smallest prime factor can be no greater than x1000001 lt 1001 Show that the de nition of multiplication for our representation of the rationals is independent of representatives You should know what this means I m not providing any hints here but you can look at the similar problem in assignment XI if you want to see the hints I gave there I will tell you that your calculations should reduce to calculations with integers alone C O 9 Suppose and 5 34 what we need to show is that is equal to 6 d 2 and 5 54 this is the same assuming 16 1 6 So assume and cd c d What we need to prove is 6 d which is equivalent to by the de nition of multiplication of fractions which is in turn equivalent to ac6 d a c 6d so 106 d a c 6d is what we need to show ac6 d a6 cd a 6c d a c 6d the rst equation follows from regrouping properties of multiplication of integers the second equation follows from the hypotheses 16 1 6 and cd dd and the third follows from regrouping again What I write can also be written a 6 of course but we did de ne a 6 which gives us a chance to use familiar notation lt ud2bc lt E c Show that if lt S then e If I draw and 3 on a number line where is 32 This is trickier than any test question is likely to be so don t spend too much time on it if you don t see how to do it but it is a good question for thinking about density Solution Don t worry about this one Show that for any rational numbers a and 6 0 you might want to write them fractions 1 6 is irrational Hint if you set this equal to a fraction you can solve for If a 6 c where c is a rational number then 16 which will be rational because a 6 c are rational which is impossible Show that for any a lt 6 a 6 a is greater than a and less than Since 0 lt g lt 1 we have a a06 a lt a 6 a lt 1 16 a 6 this follows by adding a to each side of the inequalities then multiplying them by the positive quantity 6 1 Now use these results to show that for any rational numbers a and 6 there is an irrational number 7quot such that a lt 7quot lt 6 H D S The number a 82 a a is irrational by the rst fact and lies between a and b by the second fact This is too complex again to be a test question but there are ingredients in it that might go into a test question lompute the repeating decimal representation of in base 10 This will be 272727 What are the two distinct decimal representations of in base 10 There really are two 125 and 1249999 Present the repeating decimal 02313131 a fraction Show a cal culation justifying your conclusion admittedly this will be somewhat informal 992313131 1002313131 2313131 23131313 2313131 231 2 229 so 02313131 Explain why the in nite decimal 0101001000100001 represents an irrational number It neither terminates nor ends in an in nitely repeating block of digits lompute the repeating decimal representation of in base 7 This will be 02222222 What is the value of the repeating base 3 decimal 01111 Write it a fraction Its value is Give a clear description diagram is acceptable of a bijection between the set of natural numbers and the set of ordered pairs of natural numbers Show the ordered pairs associated with the numbers from one to ten explicitly list them and make it clear using a diagram or verbal description how the process would continue Look at the picture in the book illustrating the theorem that the set of rationals is countable 1 14 Give a counterexample showing that it is not always true that 0ab where 0 is the Euler phi function de ned in section 103 This is straightforward compute several values of d and you should nd a counterexample 952 1 954 2 and 958 4 1X2 Harder certainly not a test question look for a special condition on a and b which makes the equation 0ab a b true This is just something to think about if you like math H C 39 A license plate contains three letters and four digits How many possible license plates are there satisfying each of the fol lowing sets of conditions no extra conditions all possible plates 263 104 b no letter or digit appears more than once no repetitions at all 26252410987 A O V no letter or digit is immediately followed by itself 26252510999 A O V some letter is repeated andmquot some digit is repeated if you did one of the earlier parts 263 104 26 25 24 10 9 8 7 take all license plates and subtract the ones with no repetitions e some letter is repeated and some digit is repeated be careful 263 26 25 24 104 10 9 8 7 the idea is to compute how many sequences of three letters with at least one repetition there are then how many sequences of four numbers with at least one repetition then multiply these two quantities H V some letter is immediately followed by itself and some digit is immediately followed by itself 263 262525104 1099 g There is at least one A and at least one 1 Repetitions are allowed 263 253 104 94 will do it 8 h There is exactly one A and exactly one 1 There is no other restriction on repetitions 3 252 4 93 three to choose the place Where the A is then two choices of a nonA letter then four to choose the place Where the 1 is and three choices of a non1 digit
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'