http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/pennyPile.pdf
1. Understand the problem.
There isn't too many conditions with this problem, the problem itself is not too long.
What I know:
1. Understand the problem.
There isn't too many conditions with this problem, the problem itself is not too long.
What I know:
- There are 2 drawers, let's call them L and R.
- L = 64 (There are 64 pennies inside)
- R = 0
Is it possible to arrange the drawers of pennies so that there is 48 pennies in one drawer considering the following conditions:
- If the left drawer has an even number of pennies, I may transfer half of them to the right drawer.
- If the right drawer has an even number of pennies, I may transfer half of them to the left drawer.
- If L or R have an odd number of pennies, I am not allowed to do either operation.
2. Devise a plan.
In addition to the problem, Prof. Heap has included some nice "hints" to help begin the problem solving:
- Work backwards.
- Use smaller cases.
- Draw a picture.
For me, I will work with the first hint, I am not sure which drawer will be the one containing the final number of 48 pennies, so it is best to consider both cases at the same time. We will call them Case 1 and Case 2.
Case 1: L has 48 pennies, R has 16 pennies.
Case 2: L has 16 pennies, R has 48 pennies.
3. Carry out the plan.
Case 1
Let's begin by working backwards:
L:48 -> L: 64
R:16 -> R: 0
Time to fill in what goes between "->"
L: 48 #I know that I am able to only move pennies when L/R are even.
R:16 #Both L/R are even, so let's move 16 pennies from L to R.
L: 32 #Interesting.. they are still both even, and they are now equal.
R: 32 #Let's move 32 from R to L.
L: 64 #We have completed the task this in 3 steps.
R: 0
Case 2
L: 16 -> L: 0
R: 48 -> R: 64
Time to fill in what goes between "->"
L: 16 #Let's move 16 from R to L.
R: 48
L: 32 #Let's move 32 from L to R.
R: 32
L: 0
R: 64 #We are done.
4. Look back, reconsider the problem. What were some things I have to overcome?
While this problem was not extremely complicated, it could become more difficult had one the numbers become odd, and I were restricted to moving only one drawer. For me, the most difficult part was thinking ahead. This is one of the tough things I encountered when learning proof structure. It can be difficult to think in terms of "one step ahead". Think of a Big-O or Big-Omega proof - you know what you start with, and what you want to end with, but you have to somehow think about how they will meet in the middle - thinking one step ahead.
One of the critical steps in this problem was knowing that if there is 48 in one drawer, there must be 16 in the other. From here, it was not too difficult to decide which way the pennies were meant to move. :)
Case 1: L has 48 pennies, R has 16 pennies.
Case 2: L has 16 pennies, R has 48 pennies.
3. Carry out the plan.
Case 1
Let's begin by working backwards:
L:48 -> L: 64
R:16 -> R: 0
Time to fill in what goes between "->"
L: 48 #I know that I am able to only move pennies when L/R are even.
R:16 #Both L/R are even, so let's move 16 pennies from L to R.
L: 32 #Interesting.. they are still both even, and they are now equal.
R: 32 #Let's move 32 from R to L.
L: 64 #We have completed the task this in 3 steps.
R: 0
Case 2
L: 16 -> L: 0
R: 48 -> R: 64
Time to fill in what goes between "->"
L: 16 #Let's move 16 from R to L.
R: 48
L: 32 #Let's move 32 from L to R.
R: 32
L: 0
R: 64 #We are done.
4. Look back, reconsider the problem. What were some things I have to overcome?
While this problem was not extremely complicated, it could become more difficult had one the numbers become odd, and I were restricted to moving only one drawer. For me, the most difficult part was thinking ahead. This is one of the tough things I encountered when learning proof structure. It can be difficult to think in terms of "one step ahead". Think of a Big-O or Big-Omega proof - you know what you start with, and what you want to end with, but you have to somehow think about how they will meet in the middle - thinking one step ahead.
One of the critical steps in this problem was knowing that if there is 48 in one drawer, there must be 16 in the other. From here, it was not too difficult to decide which way the pennies were meant to move. :)
No comments:
Post a Comment