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.
What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?
****************************************
Step 1: Understand the problem.
This question need us to figure out the way to rearrange the pennies in the two sets by only apply two operations namely, L and R. The operation of L and R are identically the same, only difference is they only implement the operation in each specific set.
Some observation as follow:
(0). The initial states requires the left basket only can contain even number of pennies, otherwise there will be no operation for the problem.
(1). We can only use the L or R operation if any set contains even number of pennies. Otherwise the L or R and be implemented.
(2). If one of the set contains odd number of pennies, we can't have further operation until we move odd number of pennies into this set from the other one.
(3). Following the last step, if odd number of pennies moved in, then other set moved from will end up with odd pennies. This means we can't have any further operation for moving from set .
Step 2: Devising a plan.
(1). Observe the first few cases to see if any pattern can be concluded for this problem.
(2). Try to give a formula to instruction about the operation rules.
(3). Try to generalize the case with different start case.
Step 3: Carry out the plan.
Q1: left drawer contains 64 pennies, end with one of the drawers has 48 pennies
(0). 64|0 # initial case
(1). 32|32 # move half(32) from left to right
(2). 48|16 # move half(16) from right to left
Then at the end of the two operations we end up with 48 pennies in one of the drawers as required.
Q2: one of the piles has other numbers in the range [0,64]
(0). We can easily see that we can't generate a none penny pile in our system. Since zero times two is still zero, that's means we can't divided a pile by half inorder to generate a zero.
(1). Since we can't generate zero, how about 1? The answer is yes, since in this algorithm 64 is a power of 2 number, the only thing we need to do is to divided the same pile by many times. then we can easy to get a 2, and then once again, we can get 1.
(2). Actually we can generate any number by provide the initial value of 64 or any powered 2 natural numbers. The proof can be done by using recursive loop.
Q3: What about starting with a different number of pennies in the left drawer?
(0). As mentioned above the left drawer can't start at a odd number, otherwise there will be no more operation.
(1). Any number that powered by 2 is a good starting number, this means we can generate any number other then 0.
Step 4: Looking back.
This question is an open question, there can be a lot of questions related to this question, by simply change the starting value in the left drawer or by give an different operation rules.
This question need us to figure out the way to rearrange the pennies in the two sets by only apply two operations namely, L and R. The operation of L and R are identically the same, only difference is they only implement the operation in each specific set.
Some observation as follow:
(0). The initial states requires the left basket only can contain even number of pennies, otherwise there will be no operation for the problem.
(1). We can only use the L or R operation if any set contains even number of pennies. Otherwise the L or R and be implemented.
(2). If one of the set contains odd number of pennies, we can't have further operation until we move odd number of pennies into this set from the other one.
(3). Following the last step, if odd number of pennies moved in, then other set moved from will end up with odd pennies. This means we can't have any further operation for moving from set .
Step 2: Devising a plan.
(1). Observe the first few cases to see if any pattern can be concluded for this problem.
(2). Try to give a formula to instruction about the operation rules.
(3). Try to generalize the case with different start case.
Step 3: Carry out the plan.
Q1: left drawer contains 64 pennies, end with one of the drawers has 48 pennies
(0). 64|0 # initial case
(1). 32|32 # move half(32) from left to right
(2). 48|16 # move half(16) from right to left
Then at the end of the two operations we end up with 48 pennies in one of the drawers as required.
Q2: one of the piles has other numbers in the range [0,64]
(0). We can easily see that we can't generate a none penny pile in our system. Since zero times two is still zero, that's means we can't divided a pile by half inorder to generate a zero.
(1). Since we can't generate zero, how about 1? The answer is yes, since in this algorithm 64 is a power of 2 number, the only thing we need to do is to divided the same pile by many times. then we can easy to get a 2, and then once again, we can get 1.
(2). Actually we can generate any number by provide the initial value of 64 or any powered 2 natural numbers. The proof can be done by using recursive loop.
Q3: What about starting with a different number of pennies in the left drawer?
(0). As mentioned above the left drawer can't start at a odd number, otherwise there will be no more operation.
(1). Any number that powered by 2 is a good starting number, this means we can generate any number other then 0.
Step 4: Looking back.
This question is an open question, there can be a lot of questions related to this question, by simply change the starting value in the left drawer or by give an different operation rules.
No comments:
Post a Comment