Post # 5-Problem Set # 1

Well, to begin with, problem set # 1 was easy... I thought that I would need to use one of two famous techniques: wishful thinking or thoughtful wishing. However, it turned out that eaxmples we did in class were in many ways similar to problems included in the problem set. Anyway, since deadline passed long time ago I want to publish my solutions in case if you want to go through.

Q#1

No need to go into details. After going through several cases for n=1, 2, 3, 4 I found that there is a pattern. Each time when we multiply a number by 4, we multiply each digit of that number. For example, if we multiply 45 by 4 we know that the last digit of resulting number must be 0, since 5*4=20. Next step is to write out a proof based on simple induction. So, piece of cake, I would say.

Q#2

Again, I did some scratch work, so see for yourselves:

case1: n=1, {1}, there are 0 pairs

case2: n=2, {1, 2}, there is one pair, 2*(2-1)/2=1

case3: n=3, {1, 2, 3}, possible pairs {1, 2}, {2, 3}, {3, 1}, 3*(3-1)/2=3 pairs

And again, pattern! The great news, sounds like music to my ears, meaning that scratch work had not been done vainly! Any set {1, 2, ..., n-1, n} contains all pairs of different numbers from set {1, 2, ..., n-1}. The rest of the pairs of different numbers are formed just by taking each element of {1, 2, ..., n-1} and adding to it the last element of {1, 2, ..., n-1, n}. So each time when n increases by one, the number of pairs of different numbers increases by n.

n*(n-1)/2+n=n((n-1)/n+1)=n(n+1)/2, simple algebra and simple induction.