Week 7: Penny Piles

On Friday, we have an interesting lecture. The topic is called penny piles, which means, if you have 64 pennies in a drawer, and 0 in another drawer, every time you can move half of the pennies from one drawer to the other if and only if the drawer has an even number of pennies. When a drawer has an odd number of pennies, the game stops. And the final question is, can you get any number (less than 64) of pennies in a drawer?

My first guess is yes, but I can't tell why, so I started to try. I assumed that there are only eight pennies in the first drawer rather than 64 (which is exactly the second hint). For the first try, I move four pennies to the second drawer, so its 4-4. Again, half to the right and get 2-6. Then either moving from left to right or vice versa will cause the game stop, which results 1-7 or 5-3. And therefore I got all number from one to eight during the moving.

In this way, I guess no matter there are eight or 64 or for all 2^n (n is N+), we can get any number of pennies less than the total number. For the case of total of 16 pennies, I found it hard to write all the possibles in a single list, because each time of moving, I have two different ways of moving. Then I thought up a method, I draw all possible moving in a binary tree, which is just what we are learning in CSC148 (and is just hint 3).

The result is, I found that if we have total number of sixteen pennies, we can also get one to sixteen pennies, which verified my assumption. Meanwhile, I found that except the last line of the tree of sixteen pennies, all the number is just twice of the number in the eight-penny tree. And the last line of the sixteen-penny tree have 8 elements, which are all odd number less than 16. So although this is not a formal proof, we can be quite confident to say that for total number of 2^n pennies, we can get any number of pennies less than 2^n.

To formally prove this assumption, I think we can use mathematical induction. We test the case of 1, 2, 4 pennies manually and assume that if we have 2^k pennies, we can get 1 to 2^k pennies, then we prove that if we have 2^(k+1) pennies, we can get 1 to 2^(k+1).

Week 6: Test Result and more Proof

I finally got my score for my first test in U of T, which shocked me a lot. I got full marks on the second and the third questions, but I lost 8 points on the first question. Last week after the test, I checked the sample solution posted on the professor's website, and I didn't think I got so many wrong answers! I even didn't find anything wrong in my test.

Although I haven't got my test back, I still don't know what mistake I made, but maybe I can guess part of the reasons. In the second part of the first question, I might failed to explain my answer properly. Since I have never written an exam in English, I probably don't know the right way to explain my answer. But despite that, I will get my test back next week and figure out what happened. No matter what's the reason, either I failed to learn well or just didn't write properly, I'm sure I will do better in the next text!

For the lecture, we learned some more different kinds of proofing. First thing is to prove some claims about the floor function. I think the point here is to use the definition appropriately.
And when we want to prove something is wrong, we just need to prove the negation of the claim is correct.

And for the final part of the week's lecture, I learned how to prove the claim which we need to discuss is by cases. What we need to be careful is to find all the cases and do not lose any of them. Only in this way can we prove the claim correctly.

I viewed the blog of my friend this week, he mentioned that the indentation is very important, which I totally agree. Once I read someone's proof without indentation, I found it really hard to keep pace with the author because the proof is chaotic. When we finish our assignment on computer, using Tab is a good choice to make the indentation.

Week 5: Test and Proof

For this week, we took a test on Wednesday, which I think is not quite hard. The format of this test is very similar to the one of last year. I don't think there will be big problem on this.

For the lectures, we continued to learn how to prove a theorem in a good format.
First, to prove existence, which I think is the easiest, you just need to find a number of something that fit the theorem and then you have finished the proof.
Then, we learned how to prove a claim about a sequence. If there is an "exist" in the claim, just find a number which fits the claim (maybe you can find it immediately or maybe you have to calculate and get the number), then assume the antecedent is correct and try to get the consequence step by step. After get the result, do not forget to write the last few lines of the proof: add "for all" or "exists" to the claim.

Other than proving a claim directly, we can also prove that the negation of the claim is false.

I didn't know that blogger can use LaTeX before I found this student's slog.
Like this:

This is how to prove n square is odd if n is odd, which is not such difficult to prove.
The point is, I still don't know how to type in this cool way in blogger.

Week 4: Many proves

In this week's lecture, the lecture is mainly about proof.

Although we have all practiced how to prove in high school, this week's lecture is a little bit different. When we get something to prove, the first thing to do is to understand the reason that makes you believe what you are proving is correct. Then is to write down the expression. As we all know, the key point here is to be correct and can convince other people.

I have never learnt about the structure to prove something until this week's lecture. First, write the "for all" or "exist" quantifier sentence (I don't know the term to describe that) on the first few lines. Then in the next line or few lines, write the antecedent. What should we notice here is that, since the assumption is kind of like "contains" in the previous sentence in logic, you should leave some space from the beginning of the line, just like the python language (by pressing Tab). After writing down the assumption, you need to focus on the proving. Maybe you want to prove P(x) => Q(x), but usually you can get there immediately, so prove P(x) => R1(x), then R1(x) => R2(x), ......, finally Rn(x) => Q(x). According to the transitivity, you can conclude that P(x) => Q(x).

There is another topic in this week, which is about whether two quantifiers can be swapped. The professor take the definition of limit as an example which makes me feel a little bit like being in MAT137 class. But the point in this class is not to learn the definition, but to learn that if the universal quantifier and the exist quantifier are exchanged, there will be different meanings, and the definition after the change is incorrect. However, it a proposition contains only universal or only exist quantifier, then they can be exchanged and they express the same meaning.

I found that many of us do not use symbols in slog. For example, here. I believe it is quite easy in word to type "\exists" to get "∃" and type "\in" to get "∈". Using LaTeX is also a good choice. Using words instead of symbols is sometimes confusing, and if you don't want to use symbols, you should state the complete sentence.