Entry #4 - The Penny Piles Problem

The Penny Piles problem proved to be far more complicated than the previous problem. The idea of this problem is to figure out what numbers can be possible to obtain from sorting a pile of pennies from two drawers with operations l and r.

l: if the left drawer has an even amount of pennies, move half of them to the right drawer

r: if the right drawer has an odd amount of pennies, move half of them to the left drawer

First, the question gives us the scenario of 64 pennies in the left side and 0 on the right. I came up with this chart:

The chart is extensive but looking at it closely, one can see that you can get any number from 0 to 64. Pondering, I figured that if any number could be represented as 2 to the power of n, you could get any number within the range of 0 to that number and decided to look into making a few tree charts of that.

Looking at numbers before it, one can see that it is possible to write it as such. But now, I have to consider other sorts of numbers. I excluded the idea of odd numbers and having the right drawers have anything more than 0 for the time being.

(NOTE: 12 is actually 2*2*3)

Here we have a slew of numbers with different prime factorization patterns. I kept trying to find relationships between each scenario of them, eventually stumbling across this idea:

q would be our starting number. If q could be written as 2*2*n, then it is possible that 0, n, q/2, q - n and q could be reached. Where as if we can have q = 2*2*2*n, we get a more complicated result. This then left me to consider a number like 48 which could be written as 2*2*2*2*3, leading to this:

 Eventually, I resulted in getting this diagram:

This proved to be difficult for me to figure out what line r could be since it could be an immense line of numbers. all that was certain is that by always going left, [n, q - n] would be achieved. I figured that I would cut my losses and post my progress but upon looking at the trees for 10, 12, 56, 48 and 100 I noticed something.

numbers I can get from [10, 0]:

(0, 5, 10)

numbers I can get from [12, 0]:

(0, 3, 6, 9, 12)

numbers I can get from [56, 0]:

(0, 7, 14, 21, 28, 35, 49, 56)

numbers I can get from [48, 0]:

(0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 36, 39, 42, 45, 48)

I then realized that if a number is a multiple of n within the range of 0 to q, you can get that number. So now I have one idea. Now I have to consider if one drawer has an odd number of pennies and if both drawers have two even numbers that are different.

Let's consider pair [6, 4] and [12, 10] first. The total amount of each is 10 and 22, but neither the total amount, half of the total amount or 0 is present in the tree. Let's consider what is inside it though:

[6, 4] results in (1, 2, 3, 4, 6, 7, 8, 9)

[12, 10] results in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)

It can be gathered that if a pair is [e, e], then it can get any number in range 0 to q (q being e + e) except 0, q/2 and q. 

Now let's look at the two [o, e] pairs:

[4, 3] results in (1, 2, 3, 4, 5, 6)

[11, 4] results in (1, 2, 4, 7, 8, 11, 13, 14)

The only thing that the two share is that they do not reach their sum nor 0. A difference is that 4 + 3 = 7 which is a prime number and 11 + 4 = 15 which is not. Now then, we can consider more cases of odd + even = prime and odd + even = odd not prime separately.

Based on these examples above, I can conclude that if odd + even = prime, then you can obtain any number from 0 to q except 0 and q

Here I can see that if odd + even = not prime, I obtain a series of different results when I switch their values. I realize that the numbers excluded in [11, 4] are then filled in by [3, 12] and [10, 15]. Both of those are prime factors of q and the results that each of them obtain are their multiples. 15 is not included since it is in the range we cannot reach and there is no overlap of numbers which are multiples of both 3 and 5.

With this, I find that if the prime factorization is one prime times itself again, it will obtain the multiples of that prime. Now one case I have to consider is something along the lines 3 different primes timed together.

I can then infer that multiples of single primes can only reach numbers that are solely their own and not ones that are shared with other prime numbers. Or to put it different, if a multiple of a prime is shared with the multiple of a prime times another prime, it will not appear as a possibility. This also applies for something like 125, which would be weird considering it's 5*5*5. But consider multiples of 25 and 5. 

In conclusion:

Let e mean even and o mean odd
Let n mean a prime number (excluding 1)
Let N mean a product of prime numbers

If you want one number in [a, b] to equal x

• For [q, 0]:
  
  If q = 2^r, x == 0 or x == q or 0 < x < q
  
  If q = (2^r)*n, x == 0 or x == q or x is a multiple of n (n can be N too)
  
  If q = odd number: x == 0 or x == q
• For [e1, e2]: (assume q = e1 + e2)
  
  If e1 == e2, 0 < x < q
  
  If e1 == e2 and e/(2^r) = n, x is a multiple of n
  
  If e1 == e2 and e/(2^r) = N, x is a multiple of N
  
  If e1 != e2 and q = 2^r:
  PENDING
  
  If e1 != e2 and q = (2^r)*n or q = (2^r)*N:
  
  If e1 and e2 share a common n/N, then x != 0, x != q/2 and x != q and x must be a multiple of n/N
  
  If not: 0 < x < q and x != (q/2)
• For [o1, o2]: x == o1 or x == o2
• For [o, e]: (assume q = o + e)
  
  If q = prime, 0 < x < q
  
  If q = not prime:
  Factor q as n*N (*)
  
  If o and e are a multiple of n, x is a multiple of n PROVIDED that it is not a multiple of N and x != q
  
  If o and e are a multiple of N, x is a multiple of N and x != q
  
  If o and e are not a multiple of n or N, 0 < x < q and x is not a multiple of n or N
• (*)
  Keep in mind q can adapt the following scenarios:
  
  q = n1*n2 in which case, o, e and x apply to the unique n
  
  q = n1*n2*n3 which could result in:
  
  q = n1*N(2,3)
  q = n2*N(1,3)
  q = n3*N(1,2)
  
  o, e and x apply to n1 only if it doesn't belong in N(1,2) or N(1,3)
  o, e and x apply to n2 only if it doesn't belong in N(1,2) or N(2,3)
  o, e and x apply to n3 only if it doesn't belong in N(1,3) or N(2,3)
  
  We can have n1 == n2, n2 == n3 or n1 == n3 in this scenario
  
  q = n1*n1*n1 becomes n*N which then applies to the original statment
  
  If we had q = n1*n2*n3*n4:
  
  q = n1*N(2,3,4)
  q = n2*N(1,3,4)
  q = n3*N(1,2,4)
  q = n4*N(1,2,3)
  q = n1*n2*N(3,4)
  q = n1*n3*N(2,4)
  q = n1*n4*N(2,3)
  q = n2*n3*N(1,4)
  q = n2*n4*N(1,3)
  q = n3*n4*N(1,2)
  
  
  o, e and x will only apply to n1 if N(a,b) or N(a,b,c) does not contain 1.
  o, e and x will only apply to N(1,2) if N(a,b,c) does not contain 1 and 2
  etc.

EDIT (10-27-2014):

Updated info in conclusion

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.