Entry #3 - Proofs And The Test

In Week 5, I learned a new way to format a proof as well as how one can create a proof by contradiction with a statement that requires you to look at a long list of factors. I'll admit that it still is a tough subject for me to understand completely how to go about a proof. Certainly a frustrating factor is trying to find something that can allow you to show to someone that you understand that the statement is true or false. Another bit that confuses me is when one should comment and when one should assume that the reader would already know it. I should look into finding some problems and making proofs to them so I get more practice. 

Equally as important this week was the test. On the one hand, I feel as if I had studied properly for this test and had all the information that I needed to get a very high mark on it. On the other hand, I know I made substantial/idiotic errors that will cost me dearly. The last question was probably the biggest example of this as I finally had the proper sets and made the right statements true and false but before I could rewrite my answer so it would align properly to my statement, time was up. It may have to do with perhaps worrying that I wouldn't get enough marks if I didn't explain well for the first question which ate up time to do the other questions.

PROBLEM:

This is taken straight from the problem-solving wiki:

Suppose n stands for some positive whole number. Define a function f(n) that associates n with another positive whole number, as follows:
If n is even, then f(n) is n/2
If n is odd, then f(n) is 3n+1

Since f(n) takes any positive whole number as input, and produces a positive whole number as output, it makes sense to talk about f(f(n)) or f(f(f(n))) --- composing f with itself several times. Let's define F(m,n) as f(f(...f(n)...), where f is composed with itself m times. Is the following statement true or false?

For each natural number n there exists a natural number m such that F(m,n) = 1.

EXPLAINING WHY IT'S TRUE:

It is important to note that this is referring to the Collatz conjecture. If we write the statement symbolically we get:

∀ n ∊ ℕ, ∃ m ∊ ℕ, F(m, n) = 1.

Writing out the negation would be:

∃ n ∊ ℕ, ∀ m ∊ ℕ, F(m, n) =/= 1.

If I wanted to make the negation true, I would have to find a natural number that would never reach to 2, since 2/2 = 1. Which would also mean that this natural number would never be converted to a number that equivalent to a power of 2. It's evident that I can't find one that satisfies the negation because there is no number that can't avoid being pulled into being equal to a power of 2. One way to look at it is by an example:

14 = 7 * 2
(3*7 + 1) * (2/2)
(22/2) * 1
(3*11 + 1) # disregard 1 since it's already reached its final point
(34/2)
(3*17 + 1)
(52/2)
(26/2)
(3*13 + 1)
(40/2) # multiple of 10 and power of 2
(20/2)
(10/2)
(3*5 + 1) # by only one step, 5 reaches a power of 2
(16) # we have reached a power of 2

Splitting up any number into its prime factors we could have each number go through the Collatz conjecture separately and they'd reach a power of 2 at any moment. It's important to note that 5 is a prime odd number and it immediately reaches a power with one step and before it got to 5 it was gravitating to a multiple of 10 and a power of 2. Basically speaking, there are little "traps" that occur which snare numbers into sliding down to one which are impossible to avoid.