Problem solving - sum of products

I did this on the last day, way too busy for other courses.

I chose this question, "If n represents a positive whole number, what is the largest product that can be formed by multiplying the elements of a list of positive whole numbers that sum to n?" because it is very interesting, plus I like to play around with numbers a lot. Anyways, onwards to the proof:

1. Understand the problem:

This question basically asks a formula for the largest product made up of numbers that sums up to any number n.

2. Devising a plan:

Many ways to do this:

brute force - trying out a large number of values, find a pattern and test it out with extremely large number to confirm the formula. It's a good way to check your own intuition but not very efficient (especially if your guess is wrong).

equations - there's got to be some ways of relating sum and products as an equation, certainly this way is fast and more efficient as it is already mathematically rigorous and straightforward.

working backward - It may work with other problems, but may not work with this one. Basically use a random number, find the most numbers you can that makes up the two largest multiplier.

I choose a combination of brute force (this problem is relatively small), and equations (to express the formula).

3. Carrying out the plan:

The first few natural numbers are not interesting, the pattern starts to make sense with n >= 6.

number 6

list of possible sums (1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 4), (1, 5), (2, 2, 2), (1, 2, 3), (3, 3)

biggest product 9

number 7

list of possible sums (1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 4), (1, 1, 5), (1, 6), (1, 2, 2, 2), (1, 1, 2, 3), (1, 3, 3), (2, 2, 3)

biggest product 12

number 8

list of possible sums (1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 3), (1, 1, 1, 1, 4), (1, 1, 1, 5), (1, 1, 6), (1, 7), (2, 2, 2, 2), (2, 3, 3), (1, 2, 2, 3), (1, 1, 3, 3)

biggest product 18

... and so on.

Next, onwards to the formula, from the pattern above the biggest product from the list of sums is a combination of 2s, and 3s.

Given a number n, breaks the number into two-halves and find all possibles factor of floor(n/2) and ceil(n/2) (in case n is odd) those two halves represented with 2s and 3s, with 3s the most priority (i.e. a number 8 can be made by 2 X 2 X 2 X 2, but it's value is the biggest for 3 X 3 X 2).

If n is even, let k = n - 3m, where k <= n mod 3, with m \in N. Then either k is 0 or even, thus k can then be represented as powers of 2 (i.e. k = 2^p, for p \in N). Therefore n = 3m or n = 3m + 2^p, for m, p \in N, that will represent the biggest product by multiplying p 2s and m 3s (i.e. 8 = 3 X 2 + 2^1, and product = 2 X 3 X 3 = 18).

Similar case for n = odd. Then it will be of three cases: if it equals 0 after mod 3, then it is a multiples of 3, say, 3m, for m \in N. If it equals 1 after mod 3, then the equation becomes (let t be the odd half) t = 3^(s-1) + 2r, with r, s \in N, where s is the biggest powers of 3 t can obtain). If it equals 2 after mod 3, then t = 3^s + 2r, s, r \in N, since the remainder of mod 3 is a multiples of 2. Then the biggest product can be obtained by multiplying s 3s and r 2s.

So n = 3m or 3m + 2^p or 3^(s-1) + 2r or 3^(s) + 2r, depending on the situation. The biggest product is then the multiples of m or s times of 3s and p or r times of 2s.

4. Looking back:

I'm done the proof, but the mathematical expression can be simplified greatly, I need more knowledge in order to do so.

The combination works greatly because brute force allows me to find a pattern, while using equations allows me to reduce the amount of explanation I need to write/type (it's still a lot to explain the cases).

My solution may not be the neatest, but I think it works perfectly with all n. However I believe there are other equations that are shorter and much more elegant, my skill of proving is not up to that level yet...

Last day and test

This is the first time that the question typo actually messed me up completely.

So, the last day of lecture, the third test is on Chapter 7 (but what exactly?), so I have a hard time focusing on which part to study on, instead I used lots of time just to read through the course notes.

Apparently I haven't prepared myself for the Cartesian product DFSA, plus the minor typos on this question really got me stuck there for a while (yes, I know the typo was already mentioned by Danny, but actually I haven't paid attention to it). I still managed to figure out with the last few minutes I have, the other two questions are very straightforward, so nothing to say about those.

After this intensive thirteen week lecture, obviously I've learned a lot about the theory of computation, all those wonderful proof techniques are very useful for us later on in our undergraduate studies. I personally think Danny is a very good lecturer, I've learned a lot from it (and also from this course), the only think I regret so far is to not spent enough time for this course. I think I lucked out in so many places, and I know that the exam will get me for sure.

Oh well, I enjoyed this course a lot, I certainly need to improve my sleeping habits because I cannot handle morning courses (or exams!), and appeared tired sitting near the front of the class is rather embarrassing.

Back to more studying, I'll write out a proof later.

A rather pointless entry

I'm late for this entry again!

Oh well, this lecture was spent on preparing for the exam next Friday (still can't believe it's that close now), and the TA evaluate form.

There's nothing new here to write, I can spent more productive time studying and finding out a problem to solve for this slog.

Logging off~

Push-down Automata

Date: Monday
Hmm... seems like I forgot, I was busy studying for other courses.

Ah, December, the last week of university, the last week of brain torture, the beginning of a holiday.

The projector is not working again, so back to old fashion chalk-and-blackboard teaching. Today we relate the similarity between context free grammars and finite state automata, then finally show what we couldn't do in FSA (a binary string with the same number of 0s and 1s) by adding memory (a.k.a stacks) onto a similar looking FSA - the PDA! - to make it work.

I was quite relieved to find out that they are extremely similar, guess I don't have to worry about not understand it, because I can study off FSA with a few slight changes and a few more objects added to it. However, I do have to begin preparing for test 3, in the midst of me studying for other courses as well.