COMP 1805 Discrete Structures I Fall 2022
Problem Set 3
离散结构作业代写 Submit to gradescope early and often so that last-minute technical problems don’t derail you.Only the latest submission is kept.
Purpose & Goals
The fllowing problems are practice relating to Weeks 1- 6, Tutorials 4-6, and Drill 4-6, speifically
- proofs by contrapositive, proofs by construction, proofs by pigeonhole principle, disproofs by counter- example, and proofs by mathematical induction,
- mathematical definitions (functions, sets, etc.), and
- the problem solving process.
Submission Requirements 离散结构作业代写
- Type or clearly hand-write your solutions into a pdf format so that they are legibleand professional. Submit your pdf to gradescope. Photos, illegible, non-pdf, or emailed solutions will not be marked, no exceptions. See piazza for typesetting help.
- Each problem should start on a new page of the document.
- Try to model your formatting off of the proofs from lecture, tutorial, and/or the textbook.
- Submit to gradescope early and often so that last-minute technical problems don’t derail you.Only the latest submission is kept. Lates accepted within 24h at a 10% penalty.
Academic Integrity
- You may work with your peers, but you must construct your solutions in your own words on your own.
- Do not search the web for solutions or hints, post the problem set, or otherwise violate academic integrity.
- Violations (regardless of intent) must be reported to the Dean of Academic Integrity.
Tips
- Answer each problem to the best of your ability. Partial credit is your frend!
- Read the hints for where to find relevant examples for each problem.
- ,Refer to the problem solving tips guide, which also includes homework- specific suggestions.
How to Get Help
When you are stuck and need a little or big push, please ask for help!
- Timebox your effort for each problem so that you don’t spend your life on each problem set(see problem solving tips guide for how to do this effectively.)
- piazza. Read the problem set FAQs or search using the search bar. If that fails, post a public question phrasing your query as generally as possible so that other this is not possible because it reveals your approach, post privately to Instructors. This gives students can benefit. If this is not possible because it reveals your approach, post privately to Instructors. This gives your question the best chance of being answered promptly. Do not direct message or email course staff unless explicitly told this is okay. 离散结构作业代写
- discord. Try piazza first to avoid asking a duplicate questions. Discord is best for informal opinions and comradery; for questions that might be useful to others, please use piazza.Don’t be offended if questions on discord are answered with“look/ask on piazza.”
- student hours. Use for questions that require more back and forth.
Problem 1 (10 pts.) 离散结构作业代写
Let f(x):=
For this problem, we will use the notation cZ to denote the set of multiples of c.For example, 2Z denotes the even integers, and 3Z denotes multiples of 3.
(a) (3pts.) Prove that f :Z→Z is not a function (that is, it is not a function if both its domain and codomain are integers.)
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can. 离散结构作业代写
(3) Correctness. You must prove that f is not a function with a convincing proof modelled on the similar proofs from our lectures.
(b) (7 pts.) Prove that f : 2Z→Z is a function (that is, it is a function if its dormain is even integers and its codomain is all integers.)
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(6) Correctness. Regardless of how you formulate your proof, somewhere you’ll need
(2) to show (not just state) that for eacha∈A, f(a)∈B.
(2) to show (not just state) that for each a∈A, f(a) does not produce two different outputs, and
(2) to show (not just state) that for eacha∈A, f(a)∈B.
(1) Communication. We need to see a mix of notation and intuition. These proofs are short enough that you don’t really need the“column” format, but of course you can always use it. To get these points you must have sufficient detail to convince the reader of the result, and not 80 many words that things get convoluted and confusing. 离散结构作业代写
Note: f is a function from A to B if and only if
- for each a∈A, f(a) is defined.
- for each a∈A, f(a) does not produce two diferent outputs, and
- for each a∈A, f(a)∈B.
Thus to prove f is a function you would show it has these 3 properties. To show that f is not a function you would show it does not have at least one of these 3 properties. See our first lecture on functions for examples and as reference on how to structure your proofs in this problem.
Problem 2 (10 pts.) 离散结构作业代写
Let f(x) :=
.For this problem, we will use the notation cZ to denote the set of multiples of c.For example, 2Z denotes the even integers, and 3Z denotes multiples of 3.
(a) (3 pts,) Prove that f :2Z→Z is not onto.
We discussed how to prove something is not onto in our second lecture on functions; you should look there for reference to structure your proof.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can. 离散结构作业代写
(3) Correctness. You must prove that f is not an onto function with the given domain and codomain, with a convincing proof modelled on the similar proofs from our lectures.
(b) (5 pts.) Prove that f : 2Z→3Z is onto, where 3Z denotes the set of integers that are multiples of 3.
Recall that we usually prove f is onto using a proof by construction. See the second lecture on functions for examples that will help you structure your proof.
Grading Notes. While a detailed rubrie cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(4) Correctness. If your proof is not correct, this is where youll get docked. You’ll need
(1) the definition of onto,
(1) to recognize and use the correct domain and codomain,
(1) for any b in the codomain, to construct an a such that f(a) = b (with proof), and
(1) to show (not just state) that a is in the domain. 离散结构作业代写
(1) Communication. We need to see a mix of notation and intuition. These proofs are short enough that you don’t really need the “column”format, but of course you can always use it. To get these points you must have suficient detail to convince the reader of the result, and not so many words that things get convoluted and confusing. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you’ll get docked.
(c) (2 pts.) Decide whether f : 4Z→3Z is onto and prove your claim.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(2) Correctness. You rmust correctly determine whether f is or is not onto, and then prove your claim (the proof in either case will be similar to one of the previous parts.)
Problem 3 (14 pts.) 离散结构作业代写
Let f(x):=
.For this problem, we will use the notation cZ to denote the set of multiples of c. For example, 2Z denotes the even integers, and 3Z denotes multiples of 3.
(a) (5 pts.) Prove that f :2Z→Z is one-to-one via a direct proof.
Recall that we did an example of such a proof in the second lecture on functions; use that proof to help structure your proof.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(3) Correctness. If your proof is not correct, this is where you’ll get docked. You’ll need
(1) the definition of one-to -one in the“forwards” direction, 离散结构作业代写
(2) other facts to prove f is one-to-one.
(2) Communication. We need to see a mix of notation and intuition, preferably in the “column”format with the notation on the left, and the reasons on the right. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you’ll get docked.
(b) (6 pts.) Prove that f :2Z→Z is one-to-one via a proof by contrapositive.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(4) Correctness. If your proof is not correct, this is where you’ll get docked. You’ll need
(1) a statement that the proof is proceeding by contrapositive,
(1) the definition of one-to-one in its contrapositive form,
(2) other facts to prove f is one- to-one.
(2) Communication. We need to see a mix of notation and intuition, preferably in the “column”format with the notation on the left, and the reasons on the right. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you’ll get docked.
(c) (3 pts.) Decide whether f : 4Z→3Z is one-to-one and prove your claim. 离散结构作业代写
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem.We give partial credit where we can.
(3) Correctness. You must correctly determine whether f is one- to-one, and then prove your claim.
Problem 4 (8 pts.)
Suppose we have a 3×9 grid of 27 squares, where each square is either orange or black. That is, the grid has 9 columns, each with 3 rows.
For example, it’s possible that all 27 squares are orange, that all 21 square are black, or any combination of orange or black.
Use the Pigeonhole Principle to prove that there are two columns that have the same colour pattern(e.g. if one is orange, orange, black, then the other is also orange, orange, black, in the same order.)
Note: We did examples of applying the PHP in lecture, drills, and Tutorial 6. Refer to these to help structure your solutions. 离散结构作业代写
Hint: When using the Pigeonhole Principle, always
- clearly define your set A (of pigeons),
- clearly define your set B (of pigeonholes),
- clearly define the function f : A→B that maps each pigeon a∈A to a single pigeonhole f(a) and that f(a)∈B (ie. f has the 3 properties of a well. defined function), and
- explain how you’re able to apply the Pigeonhole Principle (or its extended version) to obtain the desired result.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can.
(7) Correctness. If your proof is not correct, this is where you’ll get docked. You’ll need to
(1) define the pigeons (or set A),
(1) define the pigeonholes (or set B),
(1) define the function f : A→B between them,
(1) briefly explain why f is well- defined,
(1) explain why |A|> |B|,
(1) correctly apply the PHP,
(1) explain how the result of the PHP achieves the desired result of this problem.
(1) Communication. We need to see a mix of notation and intuition. To get these points you must have sufficient detail to convince the reader of the result, and not so many words that things get convoluted and confusing. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you’ll get docked.
Problem 5 (14 pts.) 离散结构作业代写
Let A, B1, Be….n be sets. Prove by induction that for anyn≥1,
by induction on n.
Hint: Using llipses, this is equivalent to proving that
A∩(B1 U B2U…U Bn)= (A∩B1)∪(A∩B2)∪…U(A∩Bn).
While this is hopefully obvious intuitively (because we’ve tlked about it for n = 2), we are asking you to prove it formally and with an arbitrary number of values with induction. That is, you can use the fact that A∩(B∪C)= (A∩B)U(A∩C), and here we want to prove it more generally.
Hint: For full marks, use the 7-step process from lecture, tutorial, and described on the induction proof paradigm sheet.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea. of how points are distributed for this problem. We give partial credit where we can.
(12) Correctness. If your proof is not correct, this is where you’ll get docked. You’ll need to 离散结构作业代写
(1) define P(n) that is a boolean function,
(1) ensure that P(n) is a function of n,
(1) use the correct n as the base case,
(1) correctly show that the base case is true,
(1) clearly state the induction hypothesis in terms of k (or some variable of your choice),
(6) prove the inductive step
(1) start with LHS of P(k + 1) and manipulate to RHS (or vice versal). Do not start with LHS = RHS
(1) find a way to get the LHS of P(k) in your algebra somewhere, so that you can
(1) correctly apply the induction hypotheses,
(1) clearly label where the IH is used.
(2) find a way to get the RHS of P(ke + 1) in your algebra somewhere. 离散结构作业代写
(1) have a one-sentence conclusion that puts it all together (that we do at the end of every induction proof.)
Note that if you followed the 7 steps then all but the inductive step were hopefully fairly straightforward.
(2) Communication. We need to see a mix of notation and intuition. This proof is complex enough that the“column format” is recommended, but a series of individual algebraic equa-tions separated by explanatory text is fine, too. A paragraph would be impossible to under-stand. To get these points you must have sufficient detail to convince the reader of the result,and not so many words that things get convoluted and confusing. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you’ll get docked.
更多代写：bio网课代上 雅思远程代考 大学Assignment例子 怎么写abstract 英文硕士论文格式 英国论文图片引用
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
