It's my last SLOG. We all knew it was coming. I want to say I enjoyed this class but I can't. I feel neutral on the whole thing. There were both good and bad times. I feel anxious and nervous about the future; did I take enough out of this class? How can I tell? I don't really know the answers to these questions and I wish I did. I just hope I can continue to understand and develop my knowledge of proofs in the future.
Now, less reflection and more about the mathematical proof that I was supposed to do. The reason why this blog post is so late is because for the past day or two, I've been thinking about this one problem and I have yet to figure out the solution. So here's what I have:
Piles of Pennies:
What is the problem?
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 pennies, 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]?
How
to Start: Figuring out Single Cases:
For
any problem that involves working operations, we should walk through the
problem with some default/random values (and then figure out a plan from
there). In fact, it would be best to get 48 pennies in either drawer (the
initial question).
We
start with the values:
[64,0] N/A
[32,32] L
[16,48] L
So it took us 2Ls to get to 48. Let’s try a
harder value: 33.
[64,0] L=> [32,32] L=> [16,48] R=>
[40,24] L=> [20,44] R=> [42,22]…
Clearly, I seem to have no idea.
So after trying to get to 33 for 20 minutes,
I think I have come up with an alternative approach: how would piles look like
before they had gotten to 33.
I think it would be best to have the final
state be called n (it’s just easier to work with variables).
In this scenario, the n state will have to look
like this:
[33,31] (or reversed but we will ignore these
other states since they don’t help us).
Clearly, we could not have gotten to the n
state from the n-1 state from a L move since this would not make sense arithmetically
(33 * 2 > 64 is one reason why), so clearly it came from a right move:
[2, 62]
This too, could have only been possible with
one unique move: an L operation, giving us the n-2 state:
[4, 60] And similarly as above, we move to:
[8, 56] and again…
[16, 48] and suddenly we’re on a move that we’ve
seen in the previous example giving us an answer:
LLLLLR is our final combination of
operations.
Let’s try this backwards method again for 17:
[17,47] <-L [34,30] <-R [4,60] and we’re
back to a familiar track.
We get: LLLLRL
Partial
Solution: Some Understanding
So while, I have no formal proof, I have come
to some form of a conclusion about the patterns that I see. Firstly, the number
we want to get to between the ranges of 0-64, can be any number. Yes, this is a
huge assumption but I tried prime numbers and they seemed to work just as well
(and every non-prime number is divisible by 2 so I would assume they work).
While I have no formal way of proving this, I
did realize that thinking of this problem in a backwards manner is simply the
best way to think of it. If I were writing a program, it would make it far
easier to work with rather than having to think of it like a chess game (and
predicting where my moves would take me and working from there). It very much
is like a binary tree in sense; looking through all the possibilities of
starting from [64,0] would be far too time-consuming but if you start at the
end result [x,64-x], then it seems that you have a clear route to your answer.
Even though I have failed to complete a thorough proof of the situation, I feel as if I did make some headway on to how this works.
Nonetheless, I feel like this has been an interesting experience (the SLOG) but not one I would want to do again.
It's time I go prepare for my exams. Good luck to all!
Cheers!
