The problem I decided to look at for this post is the following:
https://wwwcgi.cdf.toronto.edu/~heap/cgi-bin/Solvent/wiki.pl?Problem_Solving_Home_Page/TryThisProblem
Note: I avoided looking at any solutions proposed for this problem, in order to fully show my problem-solving thought process, which I don't want entailing " Looked at a solution which worked and made me realize what I should be doing :P"
Following Polya's approach to how to solve problems (explained in this link), I will be divided this post into 4 parts, each part highlighting a step in my problem solving process and what that entitled for the above particular problem.
Problem:
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.
Note: I avoided choosing a problem that we might've been given in class/in an assignment or in a tutorial. That is because I felt like solving a problem from scratch, and had I done a problem from any of the previously mentioned pools of problems, I would already kind of have an idea of the type of thing I'm supposed to do and where to start, depending on the time that problem was presented and what we were doing in lecture at the time.
STEP 1: Understanding the problem:
Personally, this step entitled defining two piece-wise functions, F(m,n) and F(n), and re-writing the statement I'm trying to prove in a different way to ensure that I fully understand the statement.
Piece-wise functions:
F(n) = {n/2 if n is even
{ 3n+1 if n is odd
F(m,n) = {F(n) m=0
{F(m-1, F(n)) m > 0
Statement
for any natural number, if we compose f(n) of itself enough times (m times), we get 1 out of applying F(m,n).
STEP 2: Devising a plan:
For this part of my problem-solving process, I found myself thinking of different approaches to solving the given problem. Thoughts included complete induction and mathematical induction. In order to decide which flavour of induction to use, I decided to set my definitions hoping that would give me a hint as to the type of induction I should use.
Definitions:
The definitions of the functions were given above.
(Side note: since n is said to be a positive number, my predicate will be dealing with a positive n, not any natural number (i.e. not zero))
Let P(n) be the predicate such that:
P(n) : For all positive natural numbers n, there exists a natural number m such that F(m,n) = 1.
While writing the above definition out, I could partially see how to approach the problem through complete induction, so i decided to follow through and see if complete induction works.
I would have to have a base case of n=1. Propose m=0 and show P(n).
For the induction step, I would assume P(i) for all natural numbers greater than 0 and less than n (0<i<n), and look at 2 cases; 1. If n is an even number, then I would use the induction hypothesis to state that there's a natural number m, such that P(n/2) holds and show that by adding 1 to the previous m, we get P(n)
and here is where the problem arises 2. If n is an odd number, then F(m,n) = F(m-1,3n+1), since 3n+1 is greater than n, I can't use the induction hypothesis in any way.
I then tried looking at what P(n) would look like,F(m,n) = F(m-1,3n+1) = F(m-1, 3(2k+1) + 1) for some natural number k (since n is odd) = F(m-1, 2(3k+1))
= F(m-2, 3k+1) = F(m-2, n+k). since n+k is still bigger than n, I can't use the induction hypothesis anywhere here either. I then tried dividing case 2 into 2 more cases, if k is even (n+k odd) and if k is odd (n+k even), but that only seemed to make the problem bigger.
I then went on to think of how the problem would look like had I used mathematical induction, but that approach didn't get me much further.
After the extensive amount of proof trials, I re-read the problem and thought, maybe the statement is false, and a counterexample is what I need.
I then looked at the number 9 and saw a contradiction.
STEP 3: Carry out plan:
Let n = 9. Assume m is a natural finite number.
Then F(m,9) = F(m-1, F(9))
= F(m-1, 3(9)+1)
= F(m-1, 28)
= F(m-2, 14)
= F(m-3, 7)
= F(m-4, 22)
= F(m-5, 11)
= F(m-6, 34)
= F(m-7,18)
= F(m-8, 9)
# contradiction, since there's a loop when setting n to be 9, m would be an infinite number. Therefore there won't be an m such that F(m, 9) = 1. Therefore the statement is false.
STEP 4: Look back:
From solving this particular problem, I learned to read questions more carefully. If the question isn't asking me to see if the statement's true or false before proving it, I should definitely start by trying many examples and trying to find a counterexample, before attempting to prove the statement.
In addition, through trying to solve the problem, I realized that the statement would be true if n was a power of 2, since that way, we would never need to look at n being odd, therefore never have to use F(n) = 3n+1
ENTERTAINMENT:
I know this section only showed up once or a couple of times before, but here it is again :)
This is something I thought was super cool in google:
if you search recursion in google, you'll see one of google's coolest hidden easter eggs. Look at it! It might take a couple of seconds to notice what it is, it sure did for me. Ok fine I'll tell you. Typing recursion in google gets you to a page that says "Did you mean recursion" which if pressed over and over again takes you to an infinite recursive loop! :D
For 17 other cool google easter eggs, check out this website:
http://www.searchenginepeople.com/blog/ongoing-list-google-search-easter-eggs.html
No comments:
Post a Comment