Description
Question 1
Using the Well-Ordering Property (see the Appendix 1, A-5, of the textbook) of the positive integers show that 1 is the smallest positive integer.
(Hint: You can use (k ∈ Z+ ∧ n ∈ Z+) → kn ∈ Z+ without giving a proof for it.)
Question 2
Use induction to prove the statement S(m, n) : “The number of possible (ordered) solutions to x1 + x2 + . . . + xm = n is f(m, n) = (n+m−1)! where n and m are positive integers and xi ∈ {0} ∪ Z+”.
n! (m−1)!
(Hint: First use induction to prove S(m, 1) and S(1, n). Proceed, again with induction, to prove S(m + 1, n + 1) using S(m + 1, n) and S(m, n + 1) as your basis steps.)
Question 3
-
A set of equally-spaced dots are given in the figure to the right. How many triangles congruent to the one drawn in the figure, with the same size and of any orientation, can be constructed by con-necting the dots in the given grid?
-
How many onto functions are there from a set with 6 elements to a set with 4 elements?
Question 4
A string over an alphabet Σ is an ordered tuple of elements of Σ. The length of such a string is the number of elements it has. For example, the string 001101 is a string over {0, 1} and its length is 6.
-
Find the recurrence relation for the number of strings over the alphabet Σ = {0, 1, 2} of length n that contain two consecutive symbols that are the same.
-
State the initial conditions of the recurrence relation.
-
Solve the recurrence relation by finding both the homogeneous and particular solutions.
-
Your submission should be a single vector-based PDF document with the name the3.pdf.
-
Late Submission: Not allowed.
-
Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
-
Updates & Announces: You must follow the odtuclass for discussions and possible updates. You can ask your questions in the Student Forum on the course page in odtuclass.
-
Evaluation: Your .pdf file will be checked for plagiarism automatically using “black-box” tech-nique and manually by assistants, so make sure to obey the specifications.
Submission
Submission will be done via odtuclass. For those who prefer to use LATEX to generate the vector-based PDF file, a template answer filethe3.tex will be provided in odtuclass. You need to compile the filled template yourselves and submit the generated .pdf file only.
2
