MATH 340 Discrete Mathematics Winter 2021
Assignment 1
Due date: Friday, February 5, 2021 at 11:59 PM.
You can work out the problems with some friends, but every student must submit their own solutions, written in their own words: otherwise it may be considered as plagiarism. Direct copying of a solution from somewhere on the internet is also, obviously, forbidden. Late submissions will be penalized by 10% o per day after the deadline.
Question 1 (20 marks)
A website asks you to login in order to be able to write on its guestbook. But of course, it won’t let you choose just any string as a password: that would be too simple! Instead, the requirements are the following:
1. The password must contain between 8 and 10 characters.
2. Each character must be of one of the following types: lowercase letters without accents (az), uppercase letters without accents (AZ), digits (09) or special char- acters from the following list: !?#&@%*~$_
3. The password contains at least one character of at least three of the four types mentioned above.
In how many ways can a password be chosen in order to meet all those requirements? Note: That way of thinking about internet security is completely obsolete, but somehow
still common. XKCD has a comic strip about that… See https://xkcd.com/936/
Question 2 (20 marks)
Let (a1, . . . an) be any nite sequence of n integers. Show that there exist two indices s and t, with 1 ≤ s ≤ t ≤ n, such that
t
ai≡0 modn
i=s
Hint: You should use the Pigeonhole principle….
Question 3 (20 marks)
Let p ≥ 3 be a prime number, and mark p points at equal distance on the circumference of a circle like in the pictures below (where p = 7). We can trace polygons by choosing a certain amount of those points as vertices, and connecting them with non-intersecting straight lines. How many dierent polygons can we form:
(a) if we consider that a dierent choice of vertices leads to a dierent polygon?
(b) if we count all dierent rotations of the same polygon as a single polygon?
=
(c) if we count all isometric polygons (all rotations and reections of the same polygon) as the same ?
==
Question 4 (20 marks)
A wedding organizer needs to sit 4 couples and 4 single persons around a round table. In how many ways can she sit those 12 people so that:
(a) All couples sit together (the two members of each couple sit side-by-side)? (b) No couple sit together? Hint: Inclusion-Exclusion…
Note: Since the table is round, dierent rotations of the same arrangement are indistin- guishable, but a clockwise arrangement is distinguishable from its counterclockwise version.
ADD
D B=C A̸=A C CBB
Question 5 (20 marks)
Use the generating functions method to nd a short formula for the sum of cubes.
n
cn =k3
k=0