Week 7: Penny Piles Pose Peculiar Problems

Proof territory continues.

This Friday we had a very fun swing at a difficult problem involving moving penny piles. We worked at trying to move 64 pennies (2 to the power of 6) from one bin to the other, dividing the pile in half when it was even. What we found was that 64 pennies can, with the correct series of divisions, give back a pile of pennies of any size between 1 and 64. For instance:

Operation L: take 1/2 left drawer, put in right (left drawer must be even)
Operation R: take 1/2 right drawer, put in left (right drawer must be even)
(Drawer 1, Drawer 2)

To get the number 37, we must perform:
L(64, 0) -> (32, 32)
R(32, 32) -> (48, 16)

Now we have (2^5, 2^5) becoming (3*2^4, 1*2^4). This point is significant because we no longer have only powers of 2, but we now can use multiples of 3 to produce odd numbers. This will be handy for reaching 37, though it is not a multiple of 2 or 3 (in fact, it's a prime - but it can be multiplied with 2 and 3!)

R(48, 16) -> (56, 8)
L(56, 8) -> (28, 36)
L(28, 36) -> (14, 50)
.
.
.

Okay, this is taking too long.
What essentially occurs is that we must consider two numbers where the sum is 64 and one number is 37. Obviously, the other number in this scenario is 27, so let's think about those two for a minute.

27 is also prime, but its double is 54, which may be a bit more manageable. When one number is 54, the other is 10 - halving 54 here would thus get us our 37. We're working backwards towards the solution...
So now our aim is to get to 54, but let's say 10 because that sounds easier (10 is small and we know its multiples well, while 54 is a bit big and unwieldy). To get 10, we'd need to have (20, 44) before - to get that answer, we'd need to have (40, 24) before.

Let's work from here: (40, 24) is the same as (8*5, 8*3). That sounds fairly manageable, given that our starting number is 8*8. To get the (5, 3) division, let's just work within that area:
L(8*8, 0) -> (8*4, 8*4)
R(8*4, 8*4) -> (8*2, 8*6)
L(8*2, 8*6) -> (8*5, 8*3)

Now we can take the final steps to get 37. We'll have to break the 8s apart, so let's just use powers of 2 from here on to show the factors.
L(5*2^3, 3*2^3) -> (5*2^2, 3*2^3+5*2^2) --matching the factors--> (5*2^2, 11*2^2)
L(5*2^2, 11*2^2) -> (5*2, 11*2^2+5*2) --matching the factors--> (5*2, 27*2)
R(5*2, 27*2) -> (5*2+3^3, 3^3).

And 5*2+3^3 is 37. Hurray! Thus, by working backward, we are able to determine what steps to follow through solving the problem.
I'll add more to this later.

Week 6: Prove it.

Well we're in clear proof territory now. The midterm behind us, it's now become all about proving this or that statement. It's a fairly fun process to be honest: a sort of puzzle that you fill in. We start with the corners - what we start with, and what we have to get to - and gradually connect them. Maybe there's fewer pieces than a puzzle: most proofs we do have around ten steps. We do, however, have more people working on each proof than would be tackling a puzzle.

What is neat about proofs is the step where you have to make the connection: where you're looking at the structure and considering, "What can I change to make this work?" I remember doing a lot of that in math in school, and it was always exhilarating when you came across a connection between the solution and the starting proof.

It's a skill that is really all intuition: you can't memorize it because proofs always vary in form. But there makes the dopamine rush all the better when you do discover the right way to proceed. What I've found, and what Prof. Heap is pushing towards, is that it nonetheless helps to have a few basic ideas to fiddle with the proof:

A. Transform
Transforming, i.e. rearranging the elements, either the end or the beginning can help. Using the contrapositive can often suggest a new way to proceed, or for more mathematical proofs, we can move the elements around.

B. Disprove
If it's not working, try the opposite: disprove it! And, if it's impossible to disprove, then you have a proof by contradiction.

C. Replace
I would often forget to consider this, but replacing elements with their equivalents is probably the best way to find the answer to a proof. If you can get rid of variables (starting to remind myself of optimization), then you are vastly simplifying the task at hand; if you replace a difficult variable with a simpler one, then you are vastly simplifying the task at hand. Be careful when doing this, of course. You don't want to make a mistake and mangle your proof. Use an appropriate replacement. One of which we've used several times has been replacing general even or odd integers n with a 2k or 2k+1, respectively. This can be really useful, and you should always consider it.

There's a few more ways to proceed: we talked about proof by cases and splitting up the proof on Friday, but these main three have been my standbys for a long time, and I recommend them. Share any methods you may have in the comments.

Week 5: Midterm - Feeling Good

Well the midterm went very well... lots of concepts which were familiar from the past midterm and the course as a whole. So I must have listened well in class.

We're moving into more detailed proofs now, which is fun (for now). I'm a problem-solver, so I like looking at the problem and the solution and trying to mash them together. The technique of "work-from-the-end" is one I've often used in the past, and I'm glad to see that going backwards is still useful when confronted with two seemingly different functions to be reconciled.

I enjoy the notion of using contrapositives and negation to work through a problem. In class today we worked towards proving a statement was a contradiction in order to prove its negation. Useful stuff - Euclid apparently thought so at any rate.

I'm curious about how else we can play around with that sort of thing. The converse doesn't seem to have much value at first in my head, aside from the possibility that, if the converse and the statement are true, then the statement is an "iff statement." But that doesn't seem all that helpful in most scenarios. More musing will be necessary.

I'm impressed with the course, overall. I did some logic in high school and found it a bit annoyingly anal after a while, but I guess I'm more comfortable with dealing with incredibly anal systems. Probably thanks to computer science.

Week 4: Assignment 1

Well the week continues to be full of learning!

Working on A1 has been a good test of how well I understand the concepts. I found myself often combining all kinds of tests to find answers - many Venn diagrams were drawn before I wrote answers to questions.

I find that I sometimes get confused about what precisely is meant by conjunctions and disjunctions in a statement. When P(d) /\ Q(d), are we talking about the truth of each statement, or the truth of the intersection of those statements? And is there a fundamental difference between those two distinctions?

But I enjoyed trying to come up with symbols for English and English for symbols, perhaps because I've done a lot of language learning over the years and it felt very much like an activity in translation. Even though the symbolic terms like "for all" or "there exists" are not to be used in English, you can get away with usually the same phrases to represent them, although the best was when a complicated logical statement could simply be wrapped up as "the least of some group." That felt very satisfyingly complete and concise.

This will have to be a short week for the CLOG, but we shall see where things go next!