Problem Solving :))))

problem solving:

Products of sums

Understand the problem:  To find the positive integers that have the biggest product and sum is n.

Devise a plan: start from the small numbers and try to find what kind of numbers will give the maximum product.

Carry out:

n             integers sum to n                                                                             max product 

1                1                                                                                                              1(1)

2                (1,1)                                                                                                        1(1,1) 

                             

3                (1,1,1), (1,2),(3)                                                                                       3(3)  

                      

4                (1,1,1,1),(1,1,2),(2,2)(3,1),(4)                                                              4(2,2)   

                               

5                (1,1,1,1,1),(1,1,1,2)(1,1,3),(2,2,1),(2,3)(5)                                            6(2,3)     

                         

6                (1,1,1,1,1,1),(1,1,1,1,2),(1,1,2,2),(1,1,1,3),                                            9(3.3)

                  (1,1,4),(1,2,3),(2,2,2),(2,4),(3,3),(6)   

7                …                                                                                                   12(3,2,2)

8                …                                                                                                    18(3,3,2)

9                …                                                                                                       27(3,3,3)

.

.

.

n

All the products have the factor 2 and 3 except the first 2. Actually there are more factor 3 than factor 2. After I did some work on the paper, i found when we want the max product, the most number of factor 2 is 2 and the other factor are all 3.

Also all the sums that include 1 cannot be the max product. Because n > 1(n-1)

So in my opinion, the positive integer n the maximum product will contain the factor 2 and 3

but I found there are many cases in this problem.

The first one: n is a perfect square number(such as 16, 25…)

                        in this case the max product is n^(sqrt(n))

The second one: n % 3 = 0 (such as 6,9,12):

                                in this case the max product is 3^(n/3)

The third one: n % 3 = 1 (such as 10, 13…)

                          in this case first spilt n to two positive integer, the first one can be        

                          divided by 3, the  second

                          one can be divided by 2. Let the first one as larger as possible.

                          in order to do this. 

                          let s = n // 3 then max product is (3^(s-1))*(2 * 2)

                          because when n % 3 has the remainder 1, that shows when we want  

                          the most number of factor 3, there is a factor 1 

                          remain, in order to make the product max, let one factor 3 be 2 and  

                          let this 1 be 2   #(1*3<2*2)

The fourth one n % 3 = 2 (such as 14, 17,20…)

                         in this case is very similar to the third one.

                         still let s = n // 3 then the max product is (3^s)*2

                          because in this time we don't have 1 left when we want the most    

                          number of 3 as the factor. 

I do not think there has other case, because when a positive integer divided by 3 the only possible remainders are 0,1,2. 

That was all of my proof. Maybe there had some problem. Because I didn't actually calculator after n > 15, that is a huge work. But I compared the product that I got by using my formula with the number different from I got. The formula actually gave the numbers that have the maximum product.

Big O

I hate big O so much!!!!! It's sooooo head to determine the worse case. And in the other csc class we need to find the worse case running time for our code. It's so hard to see. Also for the O(m + n) and O(m(log(n))), it's not very easy which one is better. 

Also I am confused about big O and big Omega. Is the one is the worst case and the other one is the best case. Those two things made me carzy.

For the last assignment, can a function is both in Big O and big omega of other function? 

Three weeks left

After I saw my quiz 6, I just thought I forgot to ask a question about counting steps.  When we count steps for a line and after that count the total steps for the function, in the tutorial problem set we count every steps for a line, but in the lecture I think professor just counted a line as one step. What's the difference between those two? 

Also I am so happy it's end of the term, I really want a very long break. This term csc148 and csc 165 made me and my group super busy. Every time when we finished the homework for one of the course, the other course gave us new work. And we even made every Thursday as a library day. But I enjoyed those time to shared ideas with other people. It was fun to listen other people's idea, because it can bring me some new idea. 

Btw I really want to say something about our test room. The lecture hall  is not a good place for term test. It's soooooooo crowed and hard to concentrate in that room. Plz changing a test room for the future student...

a little interesting story about proof

After first mid-term, we started proof. Proof is soooooo hard. It’s hard to find the way to prove an implication. Also structure of proof is hard to write. When I see a proof question, I always do not know what to write to start a proof and what should I proof. Also there was an interesting things happened when I went to Montreal during the reading week. One night, I was in the hotel with my roommate and we both doing our homework. When she saw my assignment two, she said:” is this your homework? Why you guys need to prove those questions? They are obviously to see the answer. Look, when x < y and they both are real number, of course there is a real number that greater than x and less than y. You do not need to prove.” LoL

Assignment one

During the last two weeks, I was working on assignment one with my group. There are three questions that we found are challenging for us.

The first question is Question 4 part (c): the only prime number that divides element of S is 2. When we did Question 4, we thought about which one is the subset. But for this question, we could not find the subset. My opinion is this statement and S is equivalence to each other. But due to the question, I thought we must choose imply or implied by. So my question is for the questions like Question 4 can we answer equivalence?

The second question is about Question 1. I am not sure when should use implication and when should just use “and” and “or”? In Question 1 part (d), I am not sure about which to use. After we discussed, we chose not to use implication. But I still feel confused about that.

The last question is about Question 3. We found this question is the most challenging one in this assignment. When we translate from symbolic form to English sentence, we cannot find an efficiency to read the symbols. Also, how to translate those symbols to the right English words is another problem for us. 

Question about P ⇒ Q and (¬P ∨ Q)

This week is all about negation. I have one question about this week’s stuff. Why P ⇒ Q as same as (¬P ∨ Q)? I try to analyze this problem. Firstly P implies Q shows all the elements in P must in Q. P is the subset of Q. But I cannot understand why (¬P ∨ Q) means the same thing. Also I am not very sure about the symbol “∨”. Does (¬P ∨ Q) means the union of not P and Q? I cannot see the equivalence between (¬P ∨ Q) and P ⇒ Q.

p.s. I am sorry about posting this blog so late. I wrote the draft copy on last week but I forgot to post it .

a little bit suffering

This weeks classes are about quantifiers, sentences, symbols and implications. All of those things come into my mind in a week which makes me feel a little bit confused. I think I need to organize them in this weekend. Quantifiers and sentences do not mess me up, but implication does.

Symbols are the easiest one for me, thanks for MAT223!!!  In this semester Mat224 also include symbols. But there is a new one the symbol of negation, if I understand correct this symbol means non or not.

I want to say something about implication. In English, the definition of implication is "if...then".  In other words, implication means giving a qualification and then geting a result. The following sentence is an example: " if today is raining, then you will need to bring an umbrella.  But I am not very clear about the contrapositive and converse.The original implication is "if x, then y". In my opinion, the contrapositive for that is " if non-y, then non-x".  Also I think in contrapositive, if the original implication is True, then the contrapositive of that implication is True.The definition of converse in logic is the same as its English meaning . Also in my opinion, the original implication is 'if x, then y' and this is True. The converse of that implication is 'if y, then x' but we cannot figure out whether this is True or False. For example, in calculus, my high school teacher said if a function is differentiable on it domain, then it is continuous on its domain, but if a function is continuous on its domain, we don't know that is differentiable on its domain and the counter example is y = abs (x). I hope my understanding is right. 

Finally, I want to thanks for the tutorial problem set, because that helps me understanding the Venn diagram. It's really helpful.