Problem Solving Blog/11th (final) blog :3

So I've finally decided on the problem that I'm going to try to solve.
I choose you, penny piles!
I liked this problem because it reminded me of binary code. Since there are only two actions that can be done the procedure can be modeled by a Tree structure :)

There are some general trends I've noticed.

1. It is symmetrical, as in the numbers are paired up, so if you have x, y you get two possible combinations out all the range [0, 64] since x + y = 64. Since y, x and x, y yield you the same two combinations you only really need to make one of these equal to all numbers from [0, 64].

2. From this point above, I conclude that if you can find all the combination for [0, 32], then you
can prove the same thing for every even numbers in range of [0, 64].

Let's say you play around 64 pennies and breaks it in 32, 32
Half of that is 16, 16.
This can be obtained simply by splitting 0, 32.

Let's look at another example.
Let's say you get 32, 32 -> 16, 48 - > 40, 24
Half of that would be 20, 12
An equivalent of that in 32 penny pile would be 16, 16 -> 24, 8 -> 12, 20


3. But since you can get odd numbers from dividing even numbers in half, this takes care of the lower half of the odd numbers.

Here's an example. If you find the value of 22, 42 in the 64-pile hen you can conclude that
11, 21 is in the 32-pile.
 But if the 32-pile has all the numbers from [0, 32] then 22, 42 will definitely be a valid combination for 64-pile because of rule 2.

I'm going to list combinations by brute force, but knowing the patterns from above, I can just do the 32-pile by brute force, and that will prove that any x, y combination is valid for the 64 pile for all x and y that is an even number.

0, 32
16, 16
8, 24
4, 28
2, 30
1, 31
------
You can do it backwards, in this case I want 3
(Any '->' is meant to be an alternative path, that might help find other numbers)
3, 29
6, 26 -> 19, 13
12, 20 -> 22, 10 -> 27, 5 or  11, 21
24, 8 -> This is in the first list of numbers, so this is valid.
------
Want 7
7, 25
14, 18 -> 23, 9
28, 4 -> This is in the first list of numbers, so this is valid.
------
want 15
15, 17
30, 2 -> This is in the first list of numbers, so this is valid.

I proved all the numbers from [0, 16], but if you look at their partner, they are numbers from[16, 32]

This proves all the numbers from [0, 32] and all the even numbers from [32, 64] for 64-pile
So we're missing
33, 31
35, 29
37, 27
39, 25
41, 23....
Notice how their partners are numbers from [0, 32]?
That's right, they're just in the form of y, x instead of x, y
Therefore it is possible to get any number from range[0, 64] in the 64-pile case.