CSCI 250 Spring 2012Discrete Structures Archived Class

# All Homework

• Exercises taken from Discrete Mathematics and its Applications, Seventh Edition unless otherwise noted.
• You must show all of your work for each problem!
• Points will be deducted if you do not show all of your work.
• Each problem is generally worth 10 points. Problems with multiple parts may be assigned more points if there are enough parts or each part is significant enough.
• The Review Questions are always related to the section that will be discussed on the assignment due date.

# Homework 1

SectionProblem
1.110ceg
1.114cef
N/AThe questions below

This question is worth double. Answer the following questions based on the course website. For each one, give an answer and specify which link on the left you clicked to get the information. For instance, your answer for one might be:

```      45. Certainly (Gradebook)
```
Each question is worth 1 point, right or wrong.
1. How many assignments can you turn in late?
2. If you turn in an assignment 2 minutes into the class, is it late?
3. What percentage of your grade are exams? What percent is each exam?
4. If you want to see me in my office, what should you do?
5. If you want to submit anonymous feedback, can you? How?
6. Does neatness/organization of homework matter at all?
7. Do I have to show all of my work on homework problems, whether or not the problem says so?
8. Can you tell exactly what grade you got on any assignment in the course at any time? Can you get an idea of how your grade compares with the grade of others?
9. If you have a disability of any kind, what should you do?
10. Will I give extra credit assignments to students who are not performing well in the course?
11. What is the reading assignment for Monday?
12. At exactly what time are homework assignments due (be precise)?
13. How many problems are on Homework 4?
14. Is there class on Friday? Is it required?
15. What dates are the exams? Do you plan on being in class on those days?
16. Is reading the textbook optional?
17. Is attending department colloquiums required? How many? What day/time are they usually?
18. Are there any solutions available for the exercises in the book? If so, where?
19. What should you do after every homework assignment is handed back?
20. What is the earliest possible date and time you can leave Hope College at the end of the semester?

# Homework 2

SectionProblemsNotes
1.118
1.132ae
1.28
1.210
Review Questions4abOn page 111

# Homework 3

SectionProblem notes
1.120
28Phrases these using the same language that is in the original.
36fShow intermediate columns and list the variable columns and rows in the same order as the examples in the textbook.
1.310dSee previous comment. Also, explain why the truth table justifies your answer.
16Read the paragraph before the problem.
Review Questions6On page 111

# Homework 4

1.142Remember to say something to justify your answers. It doesn't have to be much.
1.44 Briefly explain each.
8 One of these is tricky. Think carefully.
50 Define a universe of discourse and choose statements P and Q on that universe such that the given statements have different truth values. Notice that 49 is similar...

# Homework 5

SectionProblemNotes
1.322Read the paragraph before the problem and do the problem according to the directions given there.
1.414Justify your answers by providing an example, counter example, and/or brief explanation.
1.68 Express the statements using predicates, quantifiers, and logical connectives (e.g. negation, and, or). Then identify the rules used.
16Clearly state whether or not the argument is correct and give the specific rule(s) of inference or fallacy used.
Review Question10aOn page 111.

# Homework 6

SectionProblemsNotes
1.240Look at #41 to see what sort of answer it is looking for.
1.432See the solution to #33 for an example of what it is asking for. In particular, for each one you need to:
1. Specify the domain and define appropriate predicate(s).
2. Express the statement using your predicate(s) and the appropriate quantifier(s).
3. Negate the expression and then move the negation as far to the right as you can.
4. Express the negation in English, phrasing it "nicely".
(This one is worth 20 points)
1.72Be very precise, using the definition of even (In particular, you cannot not say, for instance, that 10x+14y-6z+12 is even. You must use algebra to make it look like 2k for some integer k. Similarly for future problems with either odd or even.). A common mistake on this kind of proof is to write it in such a way that you are essentially assuming the two numbers are the same number without realizing it.
16As with the previous problem, make sure you don't construct a proof that only ends up proving it for m=n.
Review Question12On page 111

# Homework 7

SectionProblemNotes
1.122
1.330Begin by realizing that it can only be false if the premise is true but the conclusion is false. Then argue that if the conclusion is false, the premise is, too.
1.456
1.718Take the assumption that n is an integer as a given, and read the problem as "If 3n+2 is even, then n is even."
1.86Make sure to use the official definitions of odd and even throughout the proof. Also, the phrase about opposite parity simply means that one is odd and the other is even.

# Homework 8

SectionProblemNotes
1.328Read the paragraph before the problem.
1.444
1.732Three keys to this problem: First, you need each to be equivalent to the others. This will require 3 or 4 mini-proofs, depending on how you go about it. Second, you do not start all of the mini-proofs by assuming x is rational. Finally, you must use the formal definition of rational throughout your proof.
1.830Make sure you consider every possibility.
36There is in some sense an obvious number to try. That is, given two distinct numbers, there is one number that you can be certain is between them. The trick is then to prove that this number is irrational. If it isn't clear how to do that, what sort of proof comes to mind?
Review Question1On page 186
3On page 186

# Homework 9

SectionProblemNotes
1.242
1.344Read the paragraph before problem 43. Use the result of Problem 43. In other words, you just need to show that you can implement ∨ using ¬ and ∧.
1.724
2.116In case it isn't clear, give a single diagram showing the relationship between A, B, and C.
28
36
2.24If the answer to any of these is A or B, say so.

# Homework 10

SectionProblemNotes
1.144Show intermediate results
1.620Explain why or why not, specifying rules of inference/fallacies.
1.88+additionRead carefully. It says "not exceeding it", so the number itself should be included. The addition is to answer the same problem, but with the phrase "not exceeding it" replaced with "less than it".
2.212Use a "set containment proof". See Examples 10 and 12. Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
16aSee note for the previous problem.
2.38abcd
12+additionAlso specify whether each is onto. For both one-to-one and onto, justify.

# Homework 11

SectionProblemNotes
1.436
1.738Clearly show why your counterexample works. Also, read the problem carefully so you do not come up with a false counterexample.
2.216eUse a "set containment proof". Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
2.320N is the set of natural numbers ({0, 1, 2, ...}). Also, when part c says "different than the identity", it means it cannot always map a number to itself, regardless of what the function looks like. So functions like f(x)=⌊x⌋ or f(x)=2*(x/2) don't count.
36Make sure you clearly indicate which answer is which.
16b
26bhDo not give a recursive formula. I should be able to determine a100 by just plugging in 100, for instance. Assume the first term is a1.
32cMake sure to show your work.
34bMake sure to show your work.
40Make sure to show your work.

# Homework 12

SectionProblemNotes
2.226c
2.356
58
2.426a
Review Question1abOn page 378

# Homework 13

SectionProblemNotes
2.224You may use any of the valid techniques from the book.
2.426eDo not give a recursive formula. I should be able to determine a100 by just plugging in 100, for instance. Assume the first term is a1. If you are having a hard time with this, try adding or subtracting 1 from the term and seeing if the numbers look more familiar. Then you should be able to determine a formula.
32d
34d
5.14This problem is much easier if you assume P(k-1) and show P(k).
50

# Homework 14

SectionProblemNotes
1.624
2.416e
5.16Look at the solutions to similar problems (e.g. #5, #7)
18Look at the solution to problem #19
5.24Look at problem #3 and the solution in the back of the book.

# Homework 15

SectionProblemNotes
1.410
2.338Your answer should be one or more equations that relate the constants (e.g. ab=c+d). An answer that gives an example of specific values of constants that work is not enough.
5.110It should be a very simple formula.
5.28Your answer should be something of the form "For \$5n, where n≥a" for some integer a (which you need to find). Then you will need strong induction to prove it. This is probably one of the more confusing problems, but look for the solutions of the similar ones in the book for some help.
10I will give you the answer to the first part: It is always n-1 breaks. For the inductive step, don't over think it. When you break the chocolate the first time, just make up sizes it breaks into (e.g. one piece will be size i (where i is at least 1), and the other then has to be what?). Strong induction makes this pretty straightforward.
30
32

# Homework 16

SectionProblemNotes
5.120Don't make this one harder than it is. It is fairly straightforward.
5.38abFor b: recursive definitions do not always have to be based on the immediately preceding term.
12Recall that f0=0 and f1=1. This one should not be too difficult if you use the correct proof technique.
24aThe empty string (λ) is a palindrome.
38
Review Question1On page 439

# Homework 17

SectionProblemNotes
1.136eFor old time's sake.
5.112This one involves some tricky algebra.
5.38cd
24b
6.110
12
40You do not have to write out the equivalent decimal expression for this one (Josh).
Review Question6On page 440

# Homework 18

SectionProblemNotes
5.318An is A multiplied by itself n times. If you need a refresher on how to multiply matrices, ask me or look at section 2.6.
6.132Do not make these ones harder than they are. Also, do not simplify your answers. For examples, 263 or 26*25*24 are acceptable.
8.58
20
Review Question10On page 440

# Homework 19

1.318Read the paragraph before this group of problems.
6.114
60
6.212x mod 5 is the remainder when x is divided by 5. So, for instance, 13 mod 5 = 8 mod 5.
26The easiest way to show this is to give a graph where the vertices are people and edges indicates friendship. Then you need to argue why your example suffices.
34
6.38
22

# Homework 20

1.710
5.340This one can be tricky. Make sure you don't miss any possibilities.
6.324
30
6.44

# Homework 21

SectionProblemNotes
1.814This one is really easy if you try some examples. You will quickly discover whether or not it is true.
2.416fRecall that sometimes you are better off not multiplying everything out as you go. Also, this one might be more clear if you work downward.
6.338
Review Question2On page 634

SectionProblem
2.214
6.146
8.514
6.48
9.14
12
28
34aceg

SectionProblem
1.816
5.156
6.316
9.34c
8c
14ab

# Homework 24

SectionProblemNotes
2.216c
6.174Read the problem very carefully. Also, if you are able to write the decimal representation of the answer to d on less than 100 sheets of paper, you don't have the correct answer.
6.236
9.318c
32
9.512
36c
Review Question1On page 844

# Homework 25

SectionProblemNotes
2.320
5.314
6.46
9.322
9.516You need to prove that the relation has the three required properties. The complicated thing about this problem is the notation--the relation is ordered pairs of ordered pairs. This might help you think about it correctly: One thing you need to show is that if ((a,b), (c,d)) is in R, then ((c,d), (a,b)) is in R.
46
12.14a
6c
12

# Homework 26

SectionProblemNotes
6.240Don't use induction. There is a much easier way to think about it. (Hint: What section if this in?)
6.428
9.134b
36b
9.544
12.12
12.22b
6