Instructions:
1. Print out this question paper (two-sided) and write down your full working on the blank area.
2. You can have discussions with your classmates. However, make sure all the solutions you submit are your own work. Any plagirism will be given ZERO mark.
4. Before your submission, please make a softcopy of your work for further discussion in a tutorial.
5. After making your softcopy, submit your assignment to the dropbox located on the 4th floor in Chengdao Building.
Student Number: Name:
1. Given statements p,q,r,s, which of the following arguments are valid?
(Note: you need to give your arguments in order to obtain full mark.)
2. Let a ∈ Z,b ∈ Z+. Use Well Ordering Principle to prove that there exist q,r ∈ Z such that
a = qb + r and 0 ≤ r < b
3.
(a) Translate the following statement into logical formula without predicates.
(b) Use mathematical induction to prove the statement in (a).
(Full mark will be given ONLY if you use mathematical induction.)
4. Prove that
form a partition for the set .
5. Let α,β ∈ R be such that none of them is a root of a nonzero polynomial with integer coefficients (that is, cnxn + cn−1xn−1 + ... + c1x + c0, where ci ∈ Z). Show that there are at least two irrational numbers contained in the following set
S = {α + β,α − β,αβ}
6. (10 points) [bonus question] A kid is playing a game on a 4 × 4 table whose entries are filled with mutually distinct numbers. He needs to make a reshuffle on these numbers so that the numbers on the same line (only consider horizontal, vertical, and two diagonal directions) also appear on the same line after the reshuffle. After trying a few times he conjectures that the ordering of the numbers are always preserved, that is, if b is a number between a,c on a line, then b is also a number between a,c on the new line after the reshuffle. Is this conjecture true? And is this conjecture true for any n × n table?
6
7
8
12
8
7
6
10
11
12
11
10
Initial configuration A fesible reshuffle
