# [Notes](#fn1): Problem Class, 20 Oct 2020 > Group 11 -- Problem Class, MATH40001/40009 IUM > Stergios M. Antonakoudis (stergios@imperial.ac.uk) </br> Welcome to IUM Problem Class Group 11. \ Today's class: <u>**Problem Sheet 2 of Part II.**</u> [^1]: <small> *These notes[^1] are typed up and created during and for the purposes of the discussion in the online session of Problem Class Group 11 for IUM on MS Teams, similarly to the use of a 'whiteboard' in an actual class.* </small> --- ## Questions --- ## Problems to discuss: ==1, 2, 3, 4, 5== --- ### ==Problem 3.a)== Every amount of postage, that is more than one cent, can be formed using 2 cent and 3 cent stamps. ### ==Solution 3.a)== Check that 2,3 are obviously good! Let's assume that there are amounts of postage that one cannot form using 2 cent and 3 cent stamps. Choose N to be the least such amount! (by the well-ordering principle of natural numbers). Clearly $N>2$ and $N>3$. Hence, $N \geq 4$. Consider $N-2$; we know that $N-2 \geq 2$. Hence, $N-2 = 2\cdot A + 3 \cdot B$, for some $A,B \in \mathbb{N}$ (because $N > N-2$). Therefore, $N = 2 \cdot (A+1) + 3 \cdot B$. A contradiction. Hence, every $N > 1$ can be formed using 2 cent and 3 cent stamps. **QED** Alternatively, we can argue as follow: If $N=2k$, for some $k \in \mathbb{N}$, we're done! If $N=2k+1$, for some $k \in \mathbb{N}$, then either $N=3$ (i.e. $k=1$) and we're done, or $N>3$ (i.e. $k>1$) and $N=2k+1= 2(k-1) +3$ and we're done again, since $k>1$. ### ==Problem 5== Let $n \in \mathbb{N}$ and $a,b,c,d \in \mathbb{Z}$ with $[a]_n=[b]_n$ and $[c]_n=[d]_n$. (a) $[a+c]_n= [b+d]_n$ (b) $[a\cdot c]_n = [b \cdot d]_n$ ### ==Solution 5== $[a]_n=[b]_n$ means that $b-a = n\cdot p$ for some $p \in \mathbb{Z}$ and likewise, $[c]_n=[d]_n$ means $d-c = n\cdot q$ for some $q \in \mathbb{Z}$. (a) Adding them up, we get $(b+d)-(a+c)= n\cdot (p+q)$; hence $[a+c]_n=[b+d]_n$. (b) Multiplying them up, we get $bd = (a +np)(c+nq)= ac + npc + nqa + n^2pq$; hence $bd= ac + n(pc+qa+npq)$. In other words $[ac]_n=[bd]_n$. **QED**