Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CISC 203 - Assignment 2
Due: Thursday October 10 by 2:30 PM
(in the locked CISC 203 drop-off box on Goodwin 2nd floor)
One bonus mark for neatly written student information: Papers that have your name, student number and other information written exactly as requested in the regulations (found at the end), will receive one bonus mark.
Note: In questions dealing with counting/combinatorics it is always required that you explain how you arrive at the answer, (i.e., just giving some value like “562376” or “ 36 23 ” is not sufficient). On the other hand, it is not expected that you should compute very large numerical values: it is fine to give the final answer in a form like “ 56! 29!” or “ 40 21 ” as long as you clearly explain how you arrived at the answer.
1. (2 marks) How many 5-permutations does the set {1, 2, 3, 4, 5, 6, 7, 8, 9} have ? Justify your answer!
2. (2 marks)
(a) In how many ways can a group of 40 people be divided into two hockey teams each consisting of 20 people?
(b) In how many ways can we divide a group of 40 people to give 20 players for Kingston Frontenacs and 20 players for London Knights ?
Explain how you arrived at your answers!
Hints. Note that the answers to (a) and (b) should not be the same. It may be easier to begin with (b) and then for (a) figure out what is different.
3. (3 marks) Consider permutations of the sequence of seven letters ABCDEFG.
How many of the permutations contain
(a) the string ABC ?
(b) the string DEBC ?
(c) the strings AB and DC ?
(d) the strings AB and BC ?
(e) the strings AC and DC ?
(f) the strings CBA and EFG ?
Justify your answers!
4. (2 marks) Show that for n, m ≥ 1,
n + 1 m ! = n + 1 m n m − 1 ! .
5. (4 marks) How many bit strings of length 12 contain
(a) exactly three 1s?
(b) at most three 1s?
(c) at least three 1s?
(d) an equal number of 0s and 1s?
Justify your answers!
6. (4 marks) The Tim Horton’s at John Deutch center has 8 varieties of donuts. When choosing a number of donuts only the type of the donut matters. Also the order in which the choices are made does not matter.
How many ways there are to choose
(a) six donuts?
(b) 12 donuts?
(c) 24 donuts?
(d) 12 donuts with at least one of each kind?
Justify your answers!
7. (3 marks) Show that among any n + 1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.
Hint: Use the pigeon-hole principle. However, one needs to do something else – it may not be possible to apply the pigeon-hole principle directly.
Regulations on assignments
• The assignment must be based on individual work. Copying solutions from other students is a violation of academic integrity. See the course web site for more information http://research.cs.queensu.ca/home/cisc203/index.html
• At the top of the first page of the assignment, type or write in clear capital letters the following information on four different lines and in the order listed below:
– CISC-203 ASSIGNMENT X (where X ∈ {1, 2, 3, 4} is the number of the current assignment)
– LAST-NAME, FIRST-NAME (your name as it appears on solus, e.g., “SMITH, NANCY”)
– your student number (e.g., “1234 4321”)
– your signature (the signature need not be easily readable)
• Bonus mark: Papers that have the above information written exactly correctly and perfectly clearly and legibly will receive one bonus mark. An additional requirement is that it is not permitted to submit more than one copy of the same assignment. The assignment is worth 20 marks. Papers that receive the bonus mark, may get more than 20 marks. For the bonus mark there is no partial credit for incomplete information or unclear handwriting.
• The assignment should be put into the locked CISC 203 drop-off box on the 2nd floor of Goodwin hall by the due date. The assignments must be submitted in hardcopy. Assignments sent by email are not accepted.
• If the submission consists of more than one page, the pages must be stapled together.
• Note: You are asked to write your solutions using non-erasable pen (or to type the solutions). Solutions written in pencil or erasable ink will be marked, but they will not be considered for remarking after the assignments are returned.