Piles of Pennies

Continuing on from proving or disproving whether functions are upper or lower bounded by other functions, the lectures from the past week have been adding on to such proofs by the introduction of additional implications. Now statements such as those claiming that a function upper bounded by another function implies that a function squared is also upper bounded by the other function squared.

This concept brought back many previously used techniques both from CSC165 and Calculus in order to proceed with proving or disproving the statements. Overall, due to not being completely new material, my understanding of this material is not too bad. It is very similar to proofs done in the past where there are some steps acting as hurdles but everything works, as said by Professor Heap, after one special step due to the inward falling domino structure of the proofs. Assignment #3 should provide sufficient practice on the concept of proofs relating to bounds.

I have also been working on the Penny Pile problem brought up during a lecture. As of now I have not been able to formulate a solution which can easily determine whether a certain result is possible however I have put together a simple Python program to run tests to determine whether a result is possible. The algorithm used may contain some errors at this point, but they will be ironed out as progress on this problem continues.

First of all, let's go over the algorithm I had in mind when constructing this program. Writing down your ideas is always a good way to find mistakes.

1. While the goal has not been reached:
1. Check if either the left or right pile are even numbers. If not, break simulation.
2. If the goal can be reached by moving half of the left pile to the right pile, do so.
3. Else if the goal can be reached by moving half of the right pile to the left pile, do so.
4. Else if the left pile is even, move half of it to the right pile.
5. Else if the right pile is even, move half of it to the left pile.

In the coming week, this algorithm will be tested slowly using smaller sets and comparing its results to ones found by hand. The above algorithm translated into Python, in a very rough stage, is the following:



def penny_piles(goal, left=64, right=0):

    n = 0

    failed = False

    print('Left: ' + str(left) + " Right: " + str(right))

    while not(left == goal or right == goal):

        time.sleep(1)                    

        if not(left % 2 == 0 or right % 2 == 0):

            print("Failed.")

            failed = True

            break

        print('Left: ' + str(left) + " Right: " + str(right))

        if right + left // 2 == goal or left // 2 == goal:            

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif left + right // 2 == goal or right // 2 == goal:            

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        elif left % 2 == 0:

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif right % 2 == 0:

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        n += 1

    print('Left: ' + str(left) + " Right: " + str(right))

    if not failed:

        print('Goal reached after ' + str(n) + ' swaps.')

This is a very interesting problem, looking forward to working through, and hopefully solving, it.