Monday 13 October 2014

The Paper Folding Challenge

The Challenge: 

Take a strip of paper, hold it lengthwise, such that the longer side is horizontal, then fold it in half from left to right. Repeat this several times, each time folding from left to right, and halving the strip. You will reach a point where you can no longer physically fold the paper in half any more... 7 is the popular theoretical paper folding limit. Now, unfold the paper and you will realize that the creases sometimes point up and sometimes point down. Wouldn't it be nice if you were able to come up with a solution to predict the result of each fold without actually folding it? This will allow us to fold past the theoretical paper folding limit with our mind!

Understand the problem:

Okay, first, I immediately realized that this is a pattern recognition problem. Essentially, if I can figure out the pattern for which the paper's creases come to be as result of each fold,  I should be able to use that pattern to predict the next fold... Right?

Devise a Plan:

My plan was to first just take a piece of paper, fold it in half, observe, record the results, and repeat. Hold on, maybe there are some obvious facts we can take in account first before we dive into this problem. First, we know in our head that by making a fold, the paper is divided into two equal halves, and a second fold would in turn divide each of those halves into two equal halves.

Carry out the Plan:

After some folding, I realized the following:
  • for 2 folds and up, the first crease is always up, while the last crease is always down
  • starting from both ends and moving inwards, the each set of creases are alternates to each other
  • each fold  does not affect the creases created by the previous fold
  • each fold adds alternative up/down creases to the pre-existing creases, such that the first crease is always fronted by an up crease, and followed by a down crease, then each subsequent crease is followed by alternating ups and downs

Look back:

Here is the pattern for folds 1 to 6:
d
udd
uuddudd
uuduuddduuddudd
uuduudduuudduddduuduuddduuddudd
uuduudduuuddudduuuduuddduudduddduuduudduuudduddduuduuddduuddudd

How to do this in Python:

Add code below:

Implication VS Conjunction, Truth Tables, and More!

This post covers both week 3 and week 4's materials.

The Difference between Conjunction and Implication

This took some thinking, and I had some trouble understanding the implicit difference between the two. First, lets see how they are similar. Both implication and conjunction express elements with two properties. In implication for example, if P then Q, means P must be Q. In conjunction, P and Q means that an element is both P and Q. However, the difference is that while implication is one sentence, conjunction deals with two. Another difference is in how their negations are expressed. First, remember that negation simply inverts the truth value of a sentence; that is, for the negation to be True, the sentence has to be False. Now, since the implication can only be false when the assumption is True and the conclusion is False, the negation of the implication is exactly that. On the other hand, the conjunction is False, if one of the sentences is false, or both are false, so it can be written as not P or not Q.

All You Need to Know About Implications

An implication contains statements and conditions; it says that assuming if something is true, then consequently something else is true. An interesting thing about implications is that the only way to falsify it is to show that the assumption is true while the consequence is false. All other configurations of truth/false can verify the implication. So even when the assumption is false, and the consequence is true, the implication as a whole is still true. Actually, as I have stated before, even if the BOTH the assumption and the consequence are false, the implication is STILL true.

Another interesting thing is that knowing the implication means you automatically know its contrapositive. Huh? What's that? The contrapositive is simply the negation of the consequence implying the negation of the assumption. In other words, reverse the implication and apply negation to both sides. A Venn diagram should suffice as a visual explanation. What's more is that the contrapositive of the contrapositive is the original implication. That means the implication and the contrapositive are equivalent!!

Truth Tables

Now that we know about implication and conjunction... and how to verify/falsify them, we can try to verify more complex claims. I think truth tables are the most efficient tools for these kinds of exercises. To set up a truth table, simply count how many predicates you have, then calculate the base 2 to the power of that number, which becomes how many difference truth configurations for your predicates. For example, if you have 3 predicates, then the number of truth configurations is 2^3, which is 8.

DeMorgan's Law

Knowing how truth tables work helped me understand how DeMorgan's Law works. First, a quick summary of DeMorgan's Law:


  • negation (S1 and S2) is equivalent to (negation of S1 or negation of S2)
  • negation (S1 or S2) is equivalent to (negation of S1 and negation of S2)
Another way to understand these two laws is through Venn diagrams.
Finally, notice that DeMorgan's Law are named as such because they are universally True. In the truth table, this is represented as a column containing all True's. This means that every instance of universal truths can be represented by a truth table where every truth configuration leads to the final evaluation of the claim to be True.