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