Week 3 is gone already. We had to hand in Problem Set 2 on Thursday. It wasn't hard, the problem was very similar to one of the examples we saw in class last week.
Assignment 1 is due this coming Monday and I am done. Problem 4 on the assignment is now due sometime in October. The assignment in general was a little bit challenging but Problem 4 is giving me some trouble. I have been thinking about it pretty much every day and I still can't figure it out.
For those who are interested, we are asked to find a (recursive) formula for the number of ternary trees with n nodes. I started drawing trees on paper (I always start drawing pictures, it helps me understand the problem and gives me an idea of how to proceed, though in this case the picture did not help me with the latter...
So for n=5 I was getting 300 trees instead of 273 and I until last night, I was unable to see where I was generating the duplicates. Talk about frustration...I was ready to explode until I spotted the duplications...Anyways, I am happy I figured where I was making the mistake but now I need to come up with a way to count them without producing duplicates. I am done with drawing trees for at least a couple of weeks!
In class this week as continued with induction and the Principle of Well Ordering (PWO). We saw that if you believe one of PSI, PCI or PWO then you should accept all three because they are somewhat equivalent you can show that PWO implies the PSI that in turn implies the PCI.
During the last hour of the lecture professor Heap presented three proofs that were all wrong and we had to spot the subtle mistakes. The most interesting for me was the one with the hexagons. The professor told us that it was similar to a famous false proof that all horses are of the same color. If you are like stuff like this, google: proof + "all horses are" and you will find the proof.
Hm, a long post this week. I think it's because I am trying to avoid thinking about ternary trees...
Subscribe to:
Post Comments (Atom)
2 comments:
I'm about a week late giving you this advice, but a good technique is to think about two things: what seemed to be the sticking point that kept you "fooled" about the duplicate trees? Secondly, what was the breakthrough that allowed you to spot the duplication.
The idea is that by looking back on your thought process, you can indirectly speed up your problem-solving in the future.
One small point. "Subtle", not "saddle". I used to have a Prof who called saddle points (in functions of two variables) "subtle points", so you are in an honourable tradition (he was a fantastic prof).
=)
Thanks for the correction, I make mistakes like that all the time.
As for the problem, symmetry is what killed me. Looking at this problem from a combinatorics view makes it much easier.
I am trying to write a rigorous proof now hopefully it will work.
Post a Comment