Instructions:
1. Print out this question paper (two-sided) and write down your full working on the blank area.
2. You can have discussions with your classmates. However, make sure all the solutions you submit are your own work. Any plagirism will be given ZERO mark.
4. Before your submission, please make a softcopy of your work for further discussion in a tutorial.
5. After making your softcopy, submit your assignment to the dropbox located on the 4th floor in Chengdao Building.
Student Number: Name:
1. (20 points) In order to find an outstanding undergraduate teaching fellow for CSC3001, Grant gave 81 challenging questions to the candidate who eventually scored 90. Assume that the candidate scored integral points and at least 1 point on each question. Prove that the candidate scored exactly 18 points on some consecutive questions.
2. Let a,b,c,r,s,t,n be non-negative integers such that
n ≥ r + s, n ≥ r + t, n ≥ s + t.
Count the number of solutions for the following inequality:
a + b + c = n
where a < r,b < s,c < t. (Note: You do not need to simplify the expression.)
3.
(i) Given r ∈ Z+ and n ∈ Z. Define
Show that for any n ∈ Z+ we have
(ii) For n ≥ 2, establish the following by combinatorial argument
4. The following data were given in a study of a group of 1000 subscribers
to a certain magazine. In reference to job, marital status, and education, there were
312 professionals,
470 married persons,
86 married professionals,
(ii) Explain why the numbers reported in the study must be incorrect.
5. In an election, candidate A receives n votes and candidate B receives m votes, where n > m. Assuming that all of the (n+m)!/n!m! orderings of the votes are equally likely, let Pn,m denote the probability that A is always ahead in the counting of the votes.
(a) Find Pn,1, Pn,2
(b) Based on (a), conjecture the value of Pn,m.
(c) Derive a recursion for Pn,m in terms of Pn−1,m and Pn,m−1 by conditioning on who receives the last vote.
(d) Use part (c) to verify your conjecture in part (b) by an inductive proof on n + m.
6. 10 points [Bonus question] For k ∈ Z+, set Sk := {x2 (mod k)|x ∈ Z}. Prove that given m,n ∈ Z+, if gcd(m,n) = 1, then |Sm| · |Sn| = |Smn|.
