Log Seven

For assignment 3 my partner and I divided up the questions so we could work on them individually, as we didn't have much time to meet up for this week. I found that the first problem that I worked on, which was question 2, seemed unnaturally hard for me to prove. Unfortunately the issue here involved a misunderstanding of the usage of the less than or equal sign. When I first tried working on the question, which was to prove that 5n^3 - 3n^2 + 2n + 3 was in big O of 2n^3 - n^2 + n + 1, after some reductions I ended up with the problem of trying to prove that one expression could be both greater than or equal to another expression. To me it seemed that there was an issue here; even though one side can be greater than the other, there was no way for it be equal. I eventually looked through some of the practice questions and found out that the equivalence doesn't have to be satisfied, as long as the "greater" sign is. Although I should have known this, due to the "or" part, it just seems to be something that slipped my mind. Hopefully I don't repeat this mistake again as its a very fundamental concept. After fixing this misunderstanding, which hopefully is correct in the end, the question became a lot simpler to prove.

As for the problem solving question, I managed to find one on the CEMC website for problems of the weeks. I picked out the most recent one for gr.11/12, which is for week 23. Although by appearance this seems a little bit "under" in terms of grade, I think that the question itself is of reasonable difficulty. I also felt uncomfortable with the questions given on the problem solving website, so I chose this one instead.

http://cemc.uwaterloo.ca/resources/potw/2012-13/POTWE-12-GP-NP-23-P.pdf

Determine the sum of all the three-digit numbers that can be made by choosing three different numbers from the list {1, 2, 3, 4, 5, 6, 7}.

Understanding The Problem

Sum up all distinct three digit numbers using permutations of the numbers from 1-7. This means no repetitions of numbers in a digit.

Devising A Plan

There are only 3 different positions numbers can be on in a 3-digit number, which are the hundreds, tens and ones position. From all of the possible numbers made, each number from 1 to 7 will appear in each of these positions an equal number of times. Summing up all the 3-digit numbers is just equivalent to the sums of all the digits in the hundreds position times 100, plus the sums of the tens digits times 10, plus the sums of the ones digit. By finding the number of times a distinct digit will appear in a distinct position, we can apply this to all of the numbers in the list and all of the possible positions to find the total sum of 3-digit numbers.

Carry Out The Plan

The example digit used here will be 1. "1" appears in the 100's position 6P2(6!/(6-2)!) times. This determines the number of possible combinations for the other two digits from the remaining 6 numbers in the list. Overall this will show the number of 3-digit numbers that start with 1.

6! / (6 - 2)! = 6! / 4!
                   = 6 * 5
                   = 30

This can be applied to all the other numbers, meaning that there will be 30 three digit numbers that have 2-7 as the hundreds digit. Summing up all the numbers from 1-7 and multiplying it by 30 will give the total sum of all the digits in the hundreds position.

30 * (Sum(1, 7)) = 30 * 7 * (7 + 1) / 2
                           = 840

This number will also be the sum of all the tens digits and ones digits, as the previous methods can be applied in the exact same manner for those positions. By multiplying 840 by powers of 10, we can find out the total sum of all 3-digit numbers that can be made by choosing three different numbers from the list.

Sum = 840 * (10^2 + 10^1 + 10^0)
        = 840 * (111)
        = 93240

Looking Back

Extending this, the sum of all "m" digit numbers, where "m" is no greater than "n", that can be created with a list of size "n" containing numbers from 1 to "n" will be,









If the list does not contain digits from 1 to "n" then n(n +1)/2 will simply be replaced with the sum of those digits.