Wednesday 3 December 2014

Math Problem Solving Entry: Penny Piles

Well guys, it's a little late but here I am bringing you the problem solving part of my blog, involving the problem that we addressed during the last lecture of week 7. You guys know it by the name Penny Piles. Let me give you the breakdown of How I solved this problem.

Summary
You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:
L
If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.
R
If the right pile has an even number of pannies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

Choose another number in the range [0, 64]. Starting from the same initial position, can can you arrange things such that one of the drawers has that number of pennies? Are there any numbers in that range that are impossible to achieve?

Understanding the Problem

  • What is given: that the left drawer contains 64 pennies and the right drawer contains no pennies. Also we are given two methods of transfer from left to right (L) and right to left (R). These methods also contain rules that one must abide by.
  • What is needed: We need to find the correct combination of Ls and Rs in order to successfully ensure that one drawer has 48 pennies.
Devising a Plan
  • Plan 1: keep track of the potential penny transfers in a list/tree, starting with the ordered pair (64,0) representing (pennies in left drawer, pennies in right drawer) and start implementing Ls and Rs and keep track of the result. Record the process of reaching the point where one drawer contains 48 pennies
  • Plan 2: Look at the hint page and proceed from there
Carrying out the plan
After carrying out plan one I discovered that there are two ways to achieve having 48 pennies in one drawer. These methods are implementing method L 2 times in order to have the right drawer contain 48 pennies, and implementing the method L and then the method R in order to have the left drawer contain 48 pennies.

Looking Back
Looking back the main problem did not take too long to solve seeing as only 2 steps needed to be taken to achieve the desired result. So one could say you could technically solve this problem just by eyeballing the situation and coming up with the solution in your head rather than writing things down. The result can be checked as we can implement the methods in reverse in order to achieve the original result.

Additional Problem
In terms of the additional problem of attempting to find any number in the range [1, 64] that is impossible to achieve in terms of pennies by using the two methods listed, I find that to be impossible. The methods L and R can be used to achieve any one of those numbers in terms of pennies in a drawer. All even numbers can be achieved because the combination [62, 2] can be reached by using L and R, This means that if 2 can be achieved, then any multiple of 2 can be achieved by using these methods. In terms of odd numbers, since all even numbers can be achieved, the even numbers that can be halved into the same odd number times 2 can be used to both achieve these odd numbers as well as create other odd numbers in the range [1, 64] by using L or R. For example, 34 can be used to achieve 17. 54 can be used achieve 27, etc. [23, 41] can be achieved by going from [64, 0], [32, 32], [48, 16], [56, 8], [28, 36], [46, 18], and finally [23, 41].

No comments:

Post a Comment