The problem is:
You are sitting in front of two drawers.
The left drawer contains 64 pennies, the right drawer contains nothing.
-
Q1: 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 pennies, transfer half of
them to the left pile. If the right pile has an odd number of pennies,
operation R is disallowed.
-
Q2: Choose another number in
the range [0,64]. Starting from the initial position, can you arrange things
that one of the drawers has that number of pennies?
Are there any numbers in that range that are impossible to
achieve?
-
Q3: What about
starting with a different number of pennies in the left drawer?
Understand the Problem:
Basically
it is about to get a certain number of pennies only by moving a half of pennies
in the piles every time
Let us
define “DL” to be “the number of
pennies in the left drawer” and “DR”
to be “the number of pennies in the right drawer”. And as we already know, “L”
represents operation L, and “R” represents operation R.
[For Q1]
Devising a
Plan:
Since
there are only 64 pennies in the left drawer and nothing in the right one in
the initial status, what we can do is only to apply the L operation. By this we
will get
DL=32 and DR=32.
At this
moment, we have equal amount of pennies in each drawer. There is no difference
for us to apply operation L or R. Let’s try operation L, and then we will get
DL=16 and DR=48.
As we can
see, we already get a drawer with 48 pennies.
Carry Out The Plan:
Look Back:
For these
kinds of small cases, simply trying to apply operations L and R and see what
happens is enough.
[For Q2]
Devising a
Plan:
According
to the hints3, we plan to make a tree diagram by which
we can get all
possibilities of numbers we can get by applying L and R operations. By following the diagram, we can
1) Pick a number in the diagram and track
it (to see how we get it by L and R operations).
2) Find the numbers that are impossible to
achieve.(If the number is not in this diagram, then it can’t be achieved.)
To achieve target 1)
I chose a number 20 pointed by the mouse in the
diagram.
By the diagram we can see that to get
number 20, we need to apply the operation L first, followed by L, R, and end
with L. At that time, we can get 20 pennies in the left drawer.
To achieve target 2)
Since we could find all the numbers in the
range [1, 64] in this diagram, we can conclude that there is no number that
can’t be achieved between the range of 0 and 64.
Look Back:
This way
is kind of troublesome since we have to list the diagram. But it is a easy way
to work out the problem because it has little thing about mathematics.
[For Q3]
Devising a
Plan:
According
to the tree diagram we can conclude that:
①We take 6 operations to get an odd number
②64 = 26
③All the numbers in the range [1, 64] are possible to get
In conclusion, we are guessing that if we start with a different number of pennies in the left drawer, as long
as that number is 2n (n=1,2,3……), every number in
the range of [1, 2n] is impossible to get by L and R operations.
Carry Out The Plan:
We can
start with some smaller cases.
E.g. 1）If we start
with 22 = 4 pennies in the left drawer, we can find that:
As we can see, we take 2 operations to get an odd number, also, all the numbers in the range [1, 4]. The guess is true.
E.g. 2)
If we start with 23=8 pennies in the left drawer, we can find that:
As we can see, we take 3 operations to get an odd number, also, all the numbers in the range [1, 8]. The guess is true.
Look Back:
This way is mainly about guessing instead
of proofing.By referring to the way of solving this problem on
We checked the https://wwwcgi.cdf.toronto.edu/~heap/cgi-bin/Solvent/wiki.pl?Piotr%20Bugaj
which uses the way of programming. Maybe that is a better and reliable way to
solve this problem.
Partner : Jiaxun Zhang
Her slog address is
http://emily88zhang.blogspot.ca/search?updated-min=2013-01-01T00:00:00-08:00&updated-max=2014-01-01T00:00:00-08:00&max-results=9
Partner : Jiaxun Zhang
Her slog address is
http://emily88zhang.blogspot.ca/search?updated-min=2013-01-01T00:00:00-08:00&updated-max=2014-01-01T00:00:00-08:00&max-results=9
