Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Compsci 120

Assignment 1

Semester Two, 2022


This assignment covers the material in the first chapter of your coursebook. There are four problems listed below. To get full credit on this assignment, pick any three of them to complete! If you submit more than three problems, markers will grade the first three problems in numerical order that you submit and ignore the others.

All problems are worth the same number of points; complete and accurate answers to any three problems below will grant you full credit on this assignment. If you are stuck or confused by any of the problems, feel free to post on Piazza! While you cannot post questions like

❼ “hey guys what’s the answer to 1(a),” or

“Is my answer to Question 2(b) correct, please check

you can ask questions like

❼ “I don’t think I fully get how to use the % operator, can you give some examples”, or 

❼ “I’m totally stuck on 3(b), where do I even begin?”

Show all working; problems that do not show their work will receive reduced marks. Once you’re done with it, upload your completed assignment as a single PDF to Canvas before the due date (go to Assignments/Assignment 1 and press “Submit Assignment”button).

Please note that late assignments cannot be marked under any circumstances.  (With that said: if you find yourself unable to complete this assignment due to illness, injury, or personal/familial misfortune, please email us as soon as possible. We can come up with solutions to help you succeed in CS120!)

Best of luck, and enjoy the problems!

1.   (a) Recall from Lecture 1, where we talked about tiling. We said that a shape A can be tiled by a shape B if you can cover all of A with (possibly rotated or reflected) copies of B ,

such that none of the copies of B overlap or extend off of A.              Consider the following 5 × 5 board and L-shaped tile as shown below:

 

i. Is it possible to tile the board with L-shaped tiles if an arbitrary black square is removed? Justify your answer


ii. Is it possible to tile the board with L-shaped tiles if an arbitrary white square is removed? Justify your answer

(b) Can you come up with a condition on n and m (where n and m are the rows and columns

of the board) such that n × m board can be tiled with L- shaped tiles? Justify your claim. (Hint: Start with few examples- generalize the values of m and n; don’t give answers like n = 4 and m = 6)

2.   (a) Let n be an even integer. Show that n3 + n + 6 is always even.

(b) In (a), we showed that n3 + n + 6 is even whenever n is even. Can you now extend the proof to include all integers? In other words, can you show that n3 +n+6 is always even for every integer n?

(c) Let x,y be positive integers such that x divides 3y and x divides 4. Show that 2y + 1024 is a multiple of x.  [Hint: find all values of x that satisfy x divides 4 and try to reason out from there]

3.   (a) Suppose that n is an integer.  Show that one of the three values n,n + 5,n + 10 must always be a multiple of 3, regardless of the value of n.

(b) Find 5221110%7 without using a calculator.

(c) Let n be an integer such that (3n + 6)%4 = 0.  Find (n2  + 2n + 1)%4.  Justify your answer.  [ Hint:  You can assume this fact from the lectures that every integer can be written uniquely in the form 4k, 4k + 1, 4k + 2 or 4k + 3 where k ∈ Z]

4.   (a) Let x and y be positive integers such that the prime factorization of x has exactly four 5’s and prime factorization of y  has exactly two 5’s.   How many 5’s does the prime factorization of x + y contain?   (Hint:  the assumption described in the first sentence means that x = 54a and y = 52b where a and b are integers that are not divisible by 5 )

(b) Let x and y be rational numbers such that y  0 and r be an irrational number. Prove

that x + yr is irrational. (Hint: Think what happens if the statement is false)

(c) Let p and q be any two consecutive prime numbers1greater than 2. Prove that p+q  2m, where m is a prime number. (Hint: Think what happens if the statement is false)

Possible marks:  30

Note:  Collaboration  on  assignments  is  encouraged,  but you must write  up  your work individually and in your own words .

Posting questions on chegg/coursehero/stackexchange or copying answers directly from these sources is serious academic misconduct.  If you are found to have  broken these rules, you may be subject to severe academic penalties .

In all assessments, you can cite and use without proof anything proven in lectures and/or the course- book.   If you  want  to  quote  anything  else  (e .g.   results from  other textbooks,  Wikipedia,  etc .)   you must  both  cite  the  source  and re-prove  the  results  in your own words .  Simply  copying solutions  is plagiarism/cheating, and is not allowed in this course .  Academic penalties may apply for attempting to present someone else’s work as your own.