Instructions

1.  All solutions must be completed independently, and written up in LATEX  using the template provided.

2.  Show all of your work and explain all solutions. Insufficient justification will result in a loss of marks.

3.  For more details on the collaboration policy and LATEX, see the Assignment Policies document.

4. When completed, submit your compiled PDF to the dropbox posted in onQ before the deadline.

Note:  4 marks (out of 60) in Problem Set 1 are reserved for formatting, which consists of correctly en- tering your name into the LATEX template, removing the sample text/images from it, and formatting your solutions in a way that is readable by the TAs (please be considerate of them), e.g., by inserting line breaks where appropriate, using math mode for equations and text mode for text  (e.g., please make sure that yourtextdoesn\ tlooklikethis and make sure that your equations look like y = x2  instead of y=(1/3)*xˆ2). Formatting grades are assigned at the discretion of the TAs.

Problems

[8 marks]    1.  Count the number of integers from 1 to 999,999 where the sum of their digits equals 9.

[8 marks]   2. How many non-negative integer solutions are there to

x1 + x2 + x3 + x4  = 17

x1  ≥ 5      and      1 ≤ x2  ≤ 4      and     x3  ≤ 4

[8 marks]   3.  Suppose that a website requires you to select a password containing exactly n characters. Each character

may be an upper-case letter, lower-case letter, or numeric digit.  The password requires that any two adjacent characters in the password cannot be the same.

To illustrate, you may consider the following two examples:  If the website requires an  11-character password (i.e., n = 11), the password imperial233 is not allowed (since it contains the sequence 33) but the password stormcloak3 is allowed (even though it contains the character o twice).

How many disallowed n-character passwords are there?  Show all your steps and explain them in a similar level of detail as the examples in the notes, e.g., explain as if you are teaching someone how to solve the problem (marks will be assigned accordingly).

[6 marks]   4.   (a)  Suppose that you are on a Discord server with five channels.  You have created a discrete math

meme (example below), and written a script that sends it to a randomly-chosen channel each time you log in.  Suppose that you have logged in 14 times.  How many possible ways could your meme have been sent across the five channels?

Clarification:  We are not considering the ordering in which the meme was sent to different channels. We are only counting the possibilities for the number of times that the meme could have been sent to each channel.