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

MATC44 - Winter 2024

Assignment 1

Due: January 25th, 2024

Instructions: You may collaborate with your peers (and professor) on homework problems related to the course, however, you must write up your own solutions independently.  It is considered an academic offense to copy someone else’s solution or to allow someone to copy yours.

Provide justification for every problem (a proof, logical argument or counter-example).  Full credit is given only for solutions that are fully justified and correct.

Q1 (6 marks)

Prove that if 303 integers are selected from among {1, 2, . . . , 904}, then the selection includes two integers whose difference is either 2, 3 or 6. What if 302 integers are selected instead?

Q2 (3 marks)

Of all the statements that can be proven using mathematical induction, which one is your favourite? Write out the statement and give a brief outline of its proof.

Q3 (6 marks)

A tetromino is a polygon in the plane made up of four equal-sized squares connected edge-to-edge. Depicted below are the square-tetromino, the skew-tetromino and a reflection of the skew-tetromino:

Determine all possible values of positive integers m ≥ 2 and n ≥ 2 such that an m × n grid of squares can be tiled by using a collection of square and skew-tetrominoes (each tetromino may be rotated and reflected freely). Fully justify your answer (i.e., for pairs (m,n) where it is impossible, give a proof, and for pairs (m,n) where it is possible, give an example/construction showing this).

Q4 (5 marks)

For each n ≥ 5, determine the number of n-digit positive integers (as a function of n) that satisfy all of the following properties simultaneously:

❼ The sum of the digits is divisible by 10.

❼ The product of the second and third digits is 3.

❼ The integer is even.

Q5 (5 marks)

Let n ≥ 2 be a positive integer.  Give a combinatorial proof (i.e., double counting) of the identity