Problem solving session penny piles

This problem solving session is based on the lecture in 10.28 which the problem of penny piles is discussed.

A problem solving session contains four parts:

1. Understand the problem

2. Devise a plan

3. Carry out the plan

4, Look back,figure out when and how you are stuck

Each part would be discussed carefully.

1. Understand the problem

To rephrase the question: You have two number 64 and 0. You can do an operation to change the number. The operation could be done if the number is in even, you divide that number by 2, and add the divided number to the other.

For example, now one have two number 48 and 16. If you do this to 48, then it becomes 48/2 = 24 and the other number becomes 12+24 = 40. Or, you do this to 12, then it becomes 12/2 = 6 and 48+6 = 54.

We want to prove that any number in the range [0,64] are able to achieve.

2. Devise a plan

Initially we have number 64 and 0, and the only operation we can do is to divide 64 by 2 and add 32 to 0, so it becomes 32, 32. Here since the numbers are the same, the next step would change it to 48 and 16.Then we have two choices which are 24, 40 or 56, 8. Then four 12, 52; 44, 20; 28, 36; 60, 4. So far the question has already become very complicate and would be even more complicate as there are more and more possibilities. Anyway, from the sample we have seen so far, we can see the pattern that they are all even number. That is quite reasonable as an odd number means we can no longer do operation to it. For example, 17, 47 seems hard to get. If we think it in a reverse way, the answer is quiet obvious. 47*2>64, so the only possible choice is 17*2=34 and the previous numbers are 34, 30.Again, 34*2>64. Thus, the previous one is 4,60. Then 8, 56. Then 16, 48. Then 32, 32. Then 64, 0 which is the beginning.

Now it is easy to see the pattern, we do it reversely. Sdince we have the last step and we could assume the previous step until we get 64, 0.

3. Carry a plan

We have an input (A1, A2)

Let

While  (A1,A2) != (64, 0) or (0, 64):

    If A1>32:

        A2 = A2/2, A1 = A1+A2/2

    else:

        A1 = A1/2, A2 = A2+A1/2

4. Figure out when and how you stuck

In this problem solving session, I stuck for a long time when facing to the data I collected as it is hard to find the pattern. Then at one point, I got the idea to think reversely and solve the problem quiet easily. I think this is the key for the question.  

Reflection of CSC165 Lec. 12 Nov. 25th

Reflection of CSC165 Lec. 12   Nov. 25th

I forget a lot after one week's rest. Assignment 3's Q5 and Q6 really test my understanding to the content of week 10 and definitely I need to work more on it.

12.1 Countability

There are three types of countability in this course.

 1-1 means each x would correspond to each y (implies each x may correspond to more than one y and some y may not correspond to x.)

Well-defined means each x maps to a unique y.

onto means every y has some x that maps to it. (but x could correspond to more than one y or no y)

In conclusion, we can say a well-defined function is 1-1 and onto

Now, try to prove:

X =  {natural numbers}

Y =  {even natural numbers}

Intuition : X > Y as every two natural numbers generate one even number

Intuition 2: However, there are infinite X, so there will also be infinite Y and infinite = infinite

Work  with the countability:

We can find every X correspond to Y, which means they are well defined, every x has a unique y mapping to it. Thus |X| = |Y|.

Also there is a concept called "countable". In convention, any set A that satisfies |A|≤|N| is computable. 

Actually, there are countably  infinitely many python functions as all python functions could be transfer to natural number series which belongs to N. Thus it is countable  

Reflection of CSC165 Lec. 10 Nov. 11th

Reflection of CSC165 Lec. 10   Nov. 11th

10.1 Big -omega proof

After the big oh proof we did last week, omega proof is taught today. The principle of big-oh proof and omega proof is the same since big-oh means the upper bound and big-omega means the lower bound, they are almost in opposite position.

In definition, Big- omega means:

A function f(n) is in Ω(g(n)) iff:

∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≥ cg(n)

Keep in mind Big-oh means:

A function f(n) is in O(g(n)) iff:

∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≤ cg(n)

The proof of big-omega means you need to underestimate f(n) and overestimate g(n) in order to make the overestimated cg(n) equals to underestimated f(n)

10.2 Big-Oh proof for general cases

After proofing a lot of specific cases of Big-oh proof, it is time to find some general pattern or do some proof without any actual functions and numbers.

Proof:  ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

Assume f,g,h∈F, f∈O(g) ∧ g∈O(h)

    Then ∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≤ cg(n)    # def of f(n) is in O(g(n))

    Then ∃c'∈R+, ∃B'∈N, such that ∀n∈N, n ≥B' →f(n) ≤ c'h(n) # def of f(n) is in O(g(n))

    Pick c'' = c*c', then c''∈R+

    Pick B'' = max(B,B'), then B''∈N

        Assume n∈N, n≥B''

        Then f(n) ≤ cg(n)

        Also g(n) ≤ c'h(n)

        Then f(n) ≤ cg(n) ≤ cc'h(n) = c''h(n)

        Then ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

    Then ∃c∈R+, ∃B∈N, ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

Then ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

In this case, the tricky choose of c is the core of answering the question. The answer substitute cg(n) to cc'h(n).

In fact, the choice of c plays an important role in this type of general question. It is used to link the condition together to form what we want to prove.

                                                                                

10.3 introduction to computability

After studying this section, I think it is the most difficult part so far I have learnt in this course. It is so abstract that I cannot get it from the example showed in the slide. Also the last question of Assignment 3 talks about the halt problem. I think I do not do it very well. Even though, I will try to explain this part in my words and comment on the question of Assignment 3.

Computer computes things by using algorithm, it is so powerful that it can solve a lot of complicate questions and returns the answer. However it is not always the case, sometimes the an easy program may lead to problem like infinity loop, which the computer would work forever inside the loop and cannot return the answer.

A typical infinity loop program may be this:

def blah(x):

    if x % 2 == 0:

        while True: pass

    else

        return x

The function would return x when x is an odd number, but when x is even, it will go into if x % 2 == 0. The while statement is true, so it will loop in the while line forever.

In order to judge this kind of functions, we use halt(f, i) to do so. I spend a lot of time to understand halt because the definition of it given on the slide is too vogue. I think it can be improved like this:

def halt(f, i):

    '''(function, input) -> Bool       

    

    Return true if the function halts (return sth. As result). Return False if it does not return                        anything. (Does not halt)   

    '''

    How to write halt in this case???

     return True

It is said that nobody can write halt(f, n) and it could be proved by contradiction.

So we suppose we can write halt(f,n)

Also I do not recommend to return sth. Like 42 as it is really confused for those who have  not seen or do not know the story and context of it.

 

There are three levels of function in terms of computability.

1. Computable

F is well defined in and we can tell how to compute f(x) for every x in the domain.

2. Well defined

We can tell the meaning of f(x) (what f(x) is for every x in some domain)

3. Non-computable

We cannot tell what f(x) is for some x in all domain.

Halt(f, n)  is well-defined but not computable because we cannot compute the f(x), but know the meaning of it.

After knowing the function for halt is not computable, we can decide any function is computable by using reduction.

We say f reduces g, if

Def f(n):

    return g(n)

This simple relation between f(n) and g(n) means their computability is the same.

G computable implied f computable

In contrapositive, f non-computable implied g not-computable

There are still some problems remain  unsolved and I will get the answer as soon as possible during upcoming office hour.

Reflection of CSC165 Lec.9 Nov. 5th

9.1  Big O proof

Def of O(n2)

A function f(n) is in O(n2) iff:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

In English, it means beyond the breakpoint B, f(n) is upper-bounded by cn2, where c is some wisely chosen constant multiplier.

Now let's try to prove 3n2 + 2n ∈ O(n2)

Which means it should fits:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

f(n) =  3n2 + 2n, in order to let  f(n) ≤ cn2, c should be larger than 3

Moreover, 3n2 + 2n < 3n2 + 2n2 = 5n2

So, c could be 5 and b could be 1 as it satisfies the condition.

Proof: 3n2 + 2n ∈o(n2) 

3n2 + 2n: N→R>0

Pick c = 5, then c ∈R+

Pick B = 1, then B ∈ N

    assume n ∈N

        assume n ≥ 1

            then 3n2 + 2n ≤ 3n2 +3n2 + 2n * n

                                   = 5n2 = cn2

            then 3n2 + 2n ≤ cn2

        then n ≥ B → 3n2 + 2n ≤ cn2

     then ∀ n ∈N, n ≥ B → 3n2 + 2n ≤ cn2

Then  ∃ ∈R+, ∃B ∈N, ∀n ∈N, n ≥B → 3n2 + 2n ≤ cn2

Then   3n2 + 2n ∈ O(n2)

Then we may face to some cases that are much more complicate. Like to prove:

7n6-5n4+2n3 ∈O(6n8-4n5+n2)

The general step is to assume n  ≥ 1 # As it is applicable in most cases

Then we overestimate the upper bound and  underestimate the lower bound.

So if A < B, and the relation is not really clear, we prove it by using

(A<C<D<E<F<G<B) which the relation of every two of these are obvious

In this case: 6n8 - 4n5 + n2 > 6n8 - 4n5  > 6n8 - 4n8 > 2n8 * 9/2 > 9n6 = 7n6 +2n6 >7n6 + 2n3 > 7n6 - 5n4 +2n3

Disprove of O(n) follows the same pattern. We first negate the initial definition of O(n) and prove the negation is true

Let's think about the case of：

9.2 Big O proof with limits

      

     

   

              

   

           

  

      

       

  

  

    

   

      

        

                    

About The Site

I tried to change my slog site to wordpress, but the UI of wordpress is not so good as well. The word is too thin for people to read. And it is not good at reading special mathematics symbol.

On the other hand, I cannot login to Blogger sometimes (in fact it happens quiet often but not all the time). Anyway, I still decide to update the blog here as long as I can still login.

Reflection of CSC165 Lec. 7 Oct. 21st

Reflection of CSC165 Lec. 6 Oct. 21st

7.1 Proof by cases

Proof by cases is one kind of intuitional way in life. We think every different possibility of one case and prove all these possibilities are true. In class, we face to the following problem:

∀n∈N,n^2+n  is even
n2  + n = n (n+1)

To solve this case, we think all possibilities of n, which means n may be either even or odd.
If n is even, then n(n+1) is also even.
If n is odd, the n+1 must be even, n(n+1) is even.

The thinking above is just a rough one, we need to write the proof process academically:

Assume n ∈N
    then (∃k∈N, n=2k+1)  ∨ （∃k∈N, n=2k）
    Case1: assume ∃k∈N, n=2k+1:
        then n2  + n = n (n+1) = (2k+1)(2k+2)
                           =2 [(2k+1)(k+1)]
                           =2j                         let j be  [(2k+1)(k+1)]
    Case2: assume  ∃k∈N, n=2k:
        then n2 + n = n(n+1) =2k(2k+1)
                          =2[k(2k+1)]
                          =2k                         let k be [k(2k+1)]
Then n2+n is even

7.2 Review of proof patterns

This section aims to conclude all the ways of proof and find the pattern of them.

Generally there are two patterns of inference rules(from what we know to what we can infer):

Introduction rules start from a small statement and finally infer a bigger statement.
Elimination rules start from a big statement and finally infer a smaller statement.

7.3 Algorithm Analysis and Asymptotic Notation

This section seems very computer science related, but I do not think the professor explain the idea of algorithm very well as algorithm means. I think algorithm is a kind of sovereign goal that every computer scientist may pursue. In a lot of real life situations, there might be a lot of ways to solve a problem. Normal people may simply find one way and solve it. However, a computer scientist may find all possible ways and compare them, choose the best one in the end. The wordload is much higher than simply find one way while the final result is the same----The problem is solved. But this perfectionism makes the progress of the whole subject.

In the class we compare two sorting algorithms which are bubble sort and merge sort. These two can both achieve the goal of sorting certain codes, but the running time is totally different.

Running time does not mean the actual seconds of time the program run, because the actual time may vary depend on how powerful the hardware is. So even the program is not so efficient, one can still get the result faster than those who run a better program but on a poor hardware. Thus, if all programs are run on the same hardware, the number of steps is the real determinants.

By seeing the process of working, we find as the size of codes become larger, the more number of steps bubble would take rather than merge. In conclusion, the general pattern that bubble would take is 0.5n2 (though we do not study why is it.) and merge would take n log n.

Another important idea in algorithm is the significance of highest degree variables. That is to say x2 is no difference than 100000x2 because their variable's highest degree is the same.

Also, we may use the symbol O(f(n)) to presents the idea that a set of functions run no faster than f(n). (e.g.: 5x2 + 3x +1 is in O(3x2))

Reflection of CSC165 Lec. 6 Oct. 14th

Reflection of CSC165 Lec. 6 Oct. 14th

Today's lecture lasted two hours, so the content would be a little bit shorter, again.

6.1  proof about non-boolean functions

Non-boolean functions are another type of function. Compare to Boolean, the result is not simply True or False. Thus, we cannot make a judge (of True of False) by looking at a non-boolean function. 

The most important non-boolean function introduced in class is called "floor". ⌊X⌋  means the largest integer ≤ x.

Although ⌊X⌋  and x looks quiet similar, but they have different property. X is just a variable,  ⌊X⌋  is a function, which in the same as f(x). Thus, we cannot apply ∀⌊X⌋∈R (a quantifier) to a function.

6.2 prove something false disprove something

To prove a statement S equals to proving ¬S.

6.3 proof about limits

Let's try to solve a typical question of proof about limits which mentioned in class.

∀ϵ>0, ∃δ>0, ∀x∈R, |x−2|<δ→|x^2−4|<ϵ

Here the thinking is, since ϵ could be every value > 0, we must change δ according to ϵ in order to satisfy the requirment. Thus, we need to find a constant relationship between ϵ and δ so that no matter what the value of ϵ is, we  can always find a valid value of δ follows the pattern of such relationship.

Since we know that |x^2−4|<ϵ and  |x−2|<δ and we need to build a relation between ϵ and δ, we can try to find the relation between  |x^2−4|  and |x−2|.

We find out |x^2−4|= |x+2|×|x−2|

Since |x−2|<δ 

 |x^2−4|<δ ×|x+2|

Let x + 2 be (x - 2) + 4 = δ + 4 

 |x^2−4|<δ ×(δ+4) 

Now comes to the tricky part:

 make δ≤1,δ ×(δ+4)<5δ<ϵ  so, δ≤ϵ/5  

We also now  δ≤1(as we assume):

δ=min⁡(1,ϵ/5)

However, all the works above is just rough thought and cannot be used as to prove, but the conclusion would be used in the prove.

Prove:

Assume ϵ>0                  # Assume the prerequisite

    pick δ=min⁡(1,ϵ/5)      # from the conclusion of the rough thought above

    then δ>0                   #we can conclude this from the line above.

    assume x ∈R               #Assume prerequisite

         assume |x−2|<δ  #Assume the antecedent, antecedent must be true if we want to prove the implication is true

             then  |x^2−4|= |x+2|×|x−2|<δ ×(δ+4)<5δ<ϵ  #The same process as the rough thought

Then |x−2|<δ→ |x^2−4|<ϵ 

Change site officially.

I can no longer bear this site. It is so unstable that I cannot login most of the time. It really negatively affects my slog uploading. I will move all my slogs to the new wordpress blog site. The new address is csc165rioli.wordpress.com

Supplement for week 5 —— Recommendation of others' slog

After viewing some others SLOG, I found I may forget to mention important point of proof.

Basically it is about the general structure of the proof. For the statement of A implies B, we use "Assume" to stipulate all the assumptions are true and in implication the assumption should be true, otherwise we cannot falsify it. Then we use "Let" to illustrate the relation between A and B, by this way we get the A implies B. We use "Then" to indicate the assumption of statement is correspond with the implication.

Here I want to recommend the slog:

http://165timeslogically.blogspot.ca/

The slog has a good format of writing the structure of proof:

  "Assume .........
           Assume.......
              Let (here you define your variables)
              Prove! (here you do the proof!)
           Then... (you show that you assumption is valid)
   Then ... (here, you have proven the whole statement)"

The indentation here is very important as it implies the logic of each sentence just like Python does.

We are not required to complete the whole proof these days, but it is still important to know about the structure as it is the basis.   

Reflection of CSC165 Lec 5 Oct. 7

Reflection of CSC165 Lec 5 Oct. 7

This week the content is less than before as the first period is used as term test. The professor introduced some different ways of proving.

5.1 Contrapositive and contradiction

5.1.1 Proof using Contrapositive

Sometimes it is hard to prove P => Q directly. However, as we have learnt before, P => Q <=> ¬Q => ¬P. By using thie property, we can say if ¬Q => ¬P is true, then P => Q is true. We may still apply the chain method as introduced in 4.2 to prove that ¬Q => ¬P is true.

A typical example is to prove  ∀n∈N, n2 is odd =>n is odd.

If we try to prove it in a direct way, that is, get rid of the square, we would probably get n = and it hard to get through. (k could be everything ∈N)

However, by proving if n is not odd => n2 is odd, we get:

n is even => n2 is even

n = 2k + 1 and n2 = 4k2 + 4k + 1 = 2(2k2 + 2) + 1

Let k be 2k2 + 2

n2 is even.

5.1.2 Proof using Contradiction

In some cases, the P in P => Q is not explicit. For example: There are infinitely many even natural numbers.

Here we see the result Q "there are infinitely many even natural numbers", but the P is abstract. In this case, we would use the way of contradiction.

Proof:

assume there are a finite number of even numbers

# assuming ¬Q

  then there exists a largest even number, m

  then let m’ = 2m

  then m’ is an even number, and larger than m

  # contradiction, since m is the largest even number

then there are infinitely many even numbers

# assuming ¬Q leads to contradiction, so Q.

The # here is important as others may not quite understand what the content is about, the comments after hashtag would help others understanding.

5.2 existential, sequence

5.2.1 direct proof of existential

  As mentioned in the beginning of the course as this figure shows

one example could verify existential

5.2.2 prove a claim about a sequence

  The proof may consist several different structures and multiple quantifiers. One example introduced in class is:

∀n∈N, an = n2

Now prove:

∃i∈N, ∀j∈N, aj <= i => j < i

The professor still use the way of contrapositive, but I think it is also okay to prove it directly.

an = aj = (j2 ≤ i) => j ≤ i

since j ∈N and j2∈N, they are either positive or zero,so j2≥j. Thus,   j ≤j2 and j2≤i, j ≤i

Reflection of CSC165 Lec. 4 Sep. 30th.

Reflection of CSC165 Lec. 4 Sep. 30th.

Just something I want to write at first. I regard SLOG as another way to review the whole course,  so my goal is to repeat all the contents the professor taught as completely as possible. This is also a process of self-check if I am good at everything from this lecture. However, it is not a simple copy of the professor's powerpoint. I will rewrite all content in my own words, just like I am the teacher and I will teach students by this slog. The slog will contain some of my personal views or comments of the lecture. To make it clearer, I will use Italic font to mark it, and as some of you may find, I use bold font  to emphasize the concepts or sentences which I think is crucial.

Also, I plan to write a slog about recommending others' slog as I really see some interesting thing that I may neglect. This will be done later and separately.

4.1 Bi-implication, transitivity, mixed quantifiers

4.1.1 Bi-implication

Bi-implication is a bilateral implication. That is to say, P implies Q and Q implies P. (P => Q ) ∧ (Q => P), also we give a new sign P <=> Q to indicate bi-implication.

To more comprehensively understand bi-implication, we may try to modify it in the form (X ∧ X ) ∨ ( X ∧ X ).

By doing this we need to be familiar with the law mentioned in 3.3.2. In fact, I do not really pay attention to this part last time doing the slog as I do not quite get the reason why are we using it. I found it becomes extremely important in this lecture, so I want to do a review about laws first.

Laws:

1. De morgan's laws:

¬(P ∨ Q) <=> ¬P ∧ ¬Q

¬(P ∧ Q) <=> ¬P ∨ ¬Q

De morgan's law could be easily deduced by negating P ∧/∨ Q. Remembering the result would be efficient to solve the problem when it is comlicate.

2. Commutative laws:

P ∧ Q <=> Q ∧ P

P ∨ Q <=> Q ∨ P

We can change the order of Q and P as in and, or  relation they are lateral, but the change could not be made if P => Q as they have causality.

3. Associative laws:

4. Distributive laws:

I want to put associative law and distributive law together as they both talk about the situation when we have three predicates.

The associative law claims:

(P ∧ Q) ∧ R <=> P ∧ (Q ∧ R)

(P ∨ Q) ∨ R <=> P ∨ (Q ∨ R)

Associative law means if all three predicates are in the same condition, the parenthesis will not the affect the result.  

The distributive law claims:

(P ∨ Q) ∧ R <=> (P ∧ R) ∨ (Q ∧ R)

(P ∧ Q) ∨ R <=> (P ∨ R) ∧ (Q ∨ R)

Distributive law works quite the same as (P + Q) * R as P and Q are respectively distributed to R.

5. Identity laws:

P ∧ (Q ∨ ¬Q) <=> P

P ∨ (Q ∧ ¬Q) <=> P

The (Q ∨ ¬Q) is an empty set as one thing cannot be itself and not itself at the same time. A predicate and an empty set would lead to the predicate itself.

The (Q ∧ ¬Q) is always "all" set as it claims something would either be Q or not Q, which include all the possibilities, so it will also not affect the result.

6. Idempotent laws

P ∧ P <=> P

P ∨ P <=> P

P and P , P or P will not change the result of P, so it is the same as P itself. I still do not know the meaning of this one in fact.

Now we know  (P => Q ) ∧ (Q => P) is P <=> Q and (P => Q)  ¬P ∨ Q. P <=> Q ¬P ∨ Q) ∧ (¬Q ∨ P)

The negation of P <=> Q is ¬(P <=> Q), which could be written like (P ∧ ¬Q )∨(¬P ∧ Q).

This means either P or Q is true, but not both is true. In daily speak either or could mean one of them (but not both) is true, but in logic either or contains both and. To specifically present either or but not both, we can also use symbol exclusive or, ⊕.

4.1.2 Transitivity

Transitivity basically means the passing property of implication. For example:

P=> Q  and Q=> R, we can conclude with P =>R

The figure of transitivity would be like this: Since P => Q, Q must be true when P is true, R must be true when Q is true. So R contains a larger region than Q and R.

A classic type of transitivity could be Syllogism. A syllogism is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two or more propositions that are asserted or assumed to be true. For example:

"All men are mortal.

Socrates is a man.

Therefore, Socrates is mortal."

The example here is not really elaborate as it does not fit the form of predicate, but let's just regard Socrates as P, man as Q, mortal as R. This clearly fits the figure above. Also keep in mind in computer science these P, Q, R may not have any logic relation. They could be anything irrelevant with implication.

4.2 Proofs

"A proof is an argument that convinces someone who is logical, careful and precise"

What we have learnt so far about proof are mostly concepts which is not worthy to conclude, but it shows us a general pattern of proof something. Let's say we want to find P(x) => Q(x), but P and Q seems irrelevant. We can firstly find P(x) => R(x) which R(x) is directly led by P(x). R(x) => R1(x) which R1(x) is directly led by R(x), we follow the pattern until we find Rn(x) => Q(x). The proofs is broken into several steps and each step is easy to follow.

The unexpected hanging paradox is also introduced in class, I found this topic extremely interesting and did a lot of research on it. To save the time and space, I do not want to repeat the paradox itself and the proof about it in class. I think one argument in the proof sounds weak: "It cannot be on Friday, since after Thursday noon it would not be a surprise anymore." This statement is only true when he survives the first four days, but he may still be hanged up in the four days before. Thus, from the prespective of prisoner, the only thing he know is that he is 50% likely to be hanged up in the coming weekdays in the first four days, and this uncertainty becomes a surprise.

4.3 Problem solving session.

In CS or mathematics, we need a series of process to solve one problem. This series of work is called "Polya’s problem solving scheme". This is extremely useful in real life cases as not that much variables or quantifiers are difined. It suggests the following steps:

◆ understand the problem

◆ devise a plan

◆ carry out the plan

◆ look back

◆ acknowledge when, and how, you’re stuck

The case being given in class is called Folding, I am going to solve this problem following the Polya’s problem solving scheme.

1. Understand the problem

The process is written on the paper handout clearly. The aim is to find the pattern of crease's direction(face up or face down).

2. Devise a plan

I want to fold the strip 1 to 4 times and record the data of crease's direction. Then I try to observe the pattern and conclude the general law of it.

3. Carry out the plan

When fold 1 time:	↓	1
When fold 2 times:	↓↓↑	3
When fold 3 times:	↓↓↑↓↓↑↑	7
When fold 4 times:	↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑	15

I observe the following pattern through the data I collected:

1. the first one is always ↓.

2. the beginning is the same.

3. There are always odd number of creases, and the rear part is the reverse of the from part from the middle to the beginning.

4. Look back

I see the phenomenon and I also need to know why it happens.

1. the first one is always  ↓ because we "keep holding the right end and unfold the entire strip." and "Fold the strip so that the left end is on top of the right end. " Thus, no matter how many times I fold, the first one will always be ↓.

2. 2 happens because the N+1th fold is one the basis of Nth fold, so the initial pattern would  always be the same.

3. 3 happens because we always unfold the strip from the middle and do it again and again.

After understanding these patterns, we could conclude something more general and abstract.

Let's see this:

When fold 4 times:

↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑

In fact ,we could separate the creases into three parts:

When fold 4 times:

↓↓↑↓↓↑↑

↓

↓↓↑↑↓↑↑

The first part equals to "when fold 3 times".

The second part could be called "new", it is always the middle and always face down as explained in 1.

The second part is the reverse of the first part from the end to the beginning.

By this way, we could predict the pattern when we fold the fifth times:

When fold 5 times:

↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑

↓

↓↓↑↓↓↑↑↑↓↓↑↑↓↑↑

5. Acknowledge when, and how, you're stuck

The most difficult part is to observe the phenomenon through the data collected. Sometimes the pattern hides in the data and it hard to find. I need to try a lot of different possibilities.