SLog #12 – Penny Piles (Problem Solving)

How to Solve Problems (George Polya):

1. Understand the Problem
2. Plan a Solution
3. Carry Out Your Plan
4. Review Your Solution

Understand the Problem

The first step into problem solving is to understand what the problem is and all the information that they provide you with. The question states that there are 2 drawers, a left and right one. The left one initially starts off with 64 pennies whereas the right drawer starts off with 0. This is the setup for the question.

Now there are roles associated with transferring pennies:

I: If the left drawer has an even number of pennies, you may transfer half of them to the right drawer. If the left drawer has an odd number of pennies, operation I is disallowed.

r: If the right drawer has an even number of pennies, you may transfer half of them to the left drawer. If the right drawer has an odd number of pennies, operation r is disallowed.

In short, while a drawer has an even number of pennies, you may transfer half of them to the other drawer.

Plan a Solution

Because of the constraint that only when an “even number” of pennies exists in the left (right) drawer, you may transfer half to the right (left) drawer. Therefore once one of the drawers has an odd number, then both the operations are disallowed and therefore the remaining pennies are left alone. As a result, when trying to get to a odd number in one of the drawers, you must do so in such a way so that it is the last shift. This is crucial to the understanding of the question.

Because of the property mentioned above, we can think of the question as “if we have an odd number, can we reach it by dividing a number in two?”. When working backwards, we are able to do the reverse of the operation which is multiply one side by two, and subtract the amount from the other.

[Original Operation: L = x/2, R = y + (x/2)]

[Backwards Operation: L = x*2, R = y – (x*2)]

One way of determining whether or not a desired number can be reached is to create a full tree diagram illustrating every possible path and checking if every number from 0-64 appears in at least one branch (though this is very tedious).

Carry Out Your Plan

Using the backwards operation is very useful since we just have to check if the multiplication of two results in a number x between 0 < x < 64. If not, perform the operation on the other end. This seems like a solid technique for finding numbers.

Example: Say we wish to find the number 15. Lets start from the bottom. Assume we have L = 15, R = 49. Since multiplying the right results in a number x > 64, multiply the L*2 and subtract it from the right. Now we have L = 30, R = 49 – 15 = 34. Since multiplying the right once again gives us a number greater than 64, perform I again. L = 60, R = 4. Now L*2 > 64, therefore perform r. L = 56, R = 8. Again perform r again and again. L = 48, R = 16 -> L = 32, R = 32, -> L = 64, R = 0. We found the chain! Therefore we can write a function that checks if the result of one side is greater than 64, and if so, perform the other operation. If we wish to return the actions (assuming the original operations), place the operations in backwards order.

If we make a tree diagram for all the possible values, we can see that it does indeed contain all the values from 0 – 64 combinations. Therefore it is possible to get any number of pennies from 0 – 64 in one of the drawers.

Review Your Solution

I think this is a very solid way of approaching the problem since the original direction was difficult to perform. By working backwards, a chain was able to form. This is all speculation and may not be entirely incorrect, but I have found no problems using it so far.

If you have any questions or flaws that you have found in the approach/hypothesis, leave a comment underneath!

[Nov 28 2014] End of the Journey (SLog #11)

Finally, the end of the course is reached and it feels fantastic! Not that I didn’t enjoy the course (it was actually quite interesting) but the Christmas break is coming up and I can’t wait to spend it with my friends and family!

This will probably be the second last post of this SLog. I will be uploading one more in the week that deals with the problem solving section of the SLog assignment so be expecting that to be posted in the near future.

Anyways this week lecture consists of the last little bit of computability as well as things we should consider to review for the final exam. As the majority of the class was describing how the exam will turn out, there isn’t much to talk about.

As for the tutorial, we were given Big O’s/Omegas/Theta proofs that we were suppose to prove and they seem to be hitting on the theory more so than the problem, since the problems seemed quite easy in itself. I think I really need to practice proofs as well as their structures since I didn’t exactly do well on the assignment (-sigh-). Assignment 3’s deadline is coming up very shortly and I may use a bit of my time to message the professor or my TA to get some help if I get stuck with any of the problems or just want to clarify some things (I need all the help I can get at this point).

So once again, I will be posting up the problem solving section later on, and I guess this is the end of this SLog! It’s been a very intriguing journey and I definitely feel as though my time in this course has been used wisely. I learned a lot of logic and problem solving skills over the duration of the course that will greatly help me in future courses (especially those associated with math). Anyways thanks for reading and I hope this SLog is somewhat interesting!

[Nov 21 2014] Homestretch (SLog #10)

I’m not entirely sure that this post is necessary, but better safe than sorry!

So this week’s lecture and tutorial were cancelled due to the fall break (finally), and its been a relaxing week. Though now the pile of stress is starting to build up since the final exam period is coming soon as well as the due dates for any remaining assignments and work.

This week’s post is going to be kept really short due to the lack of content to talk about, but next week is definitely gonna fill in for this one so stay tuned for that!

[Nov 14 2014] Big O’s! (SLog #9)

Another week, another post! This week we extended our understanding of proofs into Big O’s and omegas, which deal with growth rate of functions. Although typically the same structure as all the other proofs we had done so far, the Big O proofs need a specific approach when trying to find the “connection” between the two functions in which we are given. For example, we use a chaining method in which the function of higher order is under-estimated, until there is only one term, and the lower order function is over-estimated, also until there is only one term. Then the rest of the proof is to show that for a specific c and B, the “larger” order will upper bound the “lower” order function. The concept seems very straight forward, but sometimes finding the connection may not come right away.

The tutorial sessions that we have are a great help! I’m glad that this course has a period where students can ask questions, get aid, and see examples on how to do it if you don’t already understand the concept. The quizzes mainly encourage participation rather than critical thinking, and it’s a much more relaxing environment which actually makes me learn better (I’m the type of person who gets confused when stress…).

I am very excited that we also get a 2 day break right after the weekend! Not only will I be able to catch up in work, but the lack of classes on those days will keep my workload constant and I can focus on assignments I’m currently behind in.

Anyways those are my thoughts on the week, and I hope you guys have a great long weekend!

[Nov 7 2014] Nearing the End (SLog #8)

Finally we  are in the first week of November, and it’s hard to believe that there’s only one month left of first semester! I’m pretty excited for the Christmas Break but there’s still plenty of work to do in the mean time. This week we focused more on the definition of Big O, and took up examples on how to prove them (taking information from the previous topic). The coding in the algorithms shown in the lecture and tutorial still seem difficult for me since I just barely learned how to read/write code in my computer science course (CSC108 since I’m a beginner) so I’m doing the best I can to experiment with coding in Python. I understand the general approach/concept so I will feel a lot more confident once I get the coding down.

Additionally, we had just done and performed an assignment and test on proofs (yay…) and I’m unsure about my results. The way to approach proofs seem very abstract to me (as people have different ways to prove the same statement) and I’m not sure whether or not I’ve done a good job proving it (though to me it seems like it was shown). After doing similar things on the MAT137 test, it’s frightening since I only got a 50% on the proof section for that. We’ll see how things turn out!

[Oct 31 2014] Spooooooky (SLog #7)

Happy Halloween everyone!

This semester seems to be soaring by really quickly (over halfway done some of my courses already!) and work is starting to escalate once more! I guess that’s something to be scared of! This week we took a deeper look into the concept of algorithms as well as reviewing a couple of notes on proofs (mainly for the upcoming assignment and test). Though they seem relatively doable, I feel like the proofs are very abstract in the sense that they can be made in several different ways and there is no absolute to how proofs are done. Having a solution to one question may not work (as in the same concept) with another relatively similar question. As a result, I’m not 100% sure whether or not my proof/structure is correct but hopefully it will all work out!

In tutorial this week, I got some extremely valuable insight on how to approach these assignment problems from my TA and I’m so glad I went (not only for the quiz mark!). My TA explained the meaning and approach we need to tackle some difficult proofs and at the end of the tutorial, I feel as though I have gotten a strong sense on solving them.

Well that’s enough for this post, time to go and enjoy some candy!

[Oct 24 2014] Done with the Madness (SLog #6)

All my midterms are completed and boy does that feel good! Although I feel as though I could have better prepared myself for them through more effective time management, I believe in my circumstances I did pretty well. This weeks lecture focused on the conclusion of proofs as well as an introduction to algorithms (which I am not familiar with). The conclusion ended with a brief summary of all the different approaches one can take when solving proofs as well as a couple of examples that were solved step by step to solidify our understanding of the unit. Afterwards, the concept of algorithms was introduced and it seems like this is the first relative computer type unit in the course so far (though there were some things introduced earlier in the year that also dealt with coding and such). I think it will be confusing at first until I get used to the language so hopefully the professor does not speed past everything and assumes we understand.

In our tutorial, we were given fairly simple proofs to solve as practice to what we have learned in the unit and I think I got the hang of proofs. The only uncertainty is around the proof structure, as I more or less understand the logic already. Anyways, I will be trying my best to boost up my grade after that midterm, doing well on one quiz at a time!

[Oct 18 2014] Collection of Midterms (SLog #5)

This week felt like a nightmare! Well maybe that was an exaggeration but the amount of studying and practicing this week was ridiculous! Over the course of the week, I’ve finished 3 out of my 4 midterms and there is still one I have to practice for (most likely the hardest one by far). I find that the questions are fairly straightforward though but the time constraint really messes with my results.

This week we centered our lecture around proofs. Although they seem very intuitive when we are performing the proof in class, when I try and attempt a similar proof (that is looks the same with a different concept), I find it really difficult to start off on the right track. It feels like proofs are something you must fiddle around with until you have a good starting point and then use things like algebra to fill in the gap. On the other hand, if you do not find a starting point, it becomes painstakingly difficult.

This weeks SLog is going to be short since there was no tutorial for this week and because of thanksgiving, our lecture was also shortened.

[Oct 3 2014] First Test (SLog #4)

Recently we have just finished our first Term Test for the course and it wasn’t as brutal as a thought. They were very similar to that of the previous test questions (in terms of context) and the wording was also the same so it was easy to understand what they were asking for.

We are beginning to introduce proofs within our class and it has me confused just as much as in my MAT137 class. I’m hoping that after being taught two different ways, the concept of proofs will start to solidify. Either way, I am currently working on previous problems that I have received in my math class to practice proofs while looking at both class notes to see how they derive/use them.

Quantifiers and the concepts of converse, contra-positive, and negations are really interesting to me now, as I can look at a statement relatively easily and find out what it is saying (usually the ones in tutorials where the questions involve some sort of quantified statement) and I think its a real indicator of my learning in the course. Still I am relatively afraid of my first assignment (after reviewing a found a couple of small mistakes that led to the whole question being wrong) and will be trying my best to improve it through the tests, mid-term, and quizzes!

[Oct 3 2014] The Stress (SLog #3)

This week we began to learn about bi-implication, proofs and laws associated with quantifiers and it is all very new and confusing to me. Despite getting the gist of what they are, proofs seem complicated and I didn’t grasp them yet, though I am rereading the lecture slides and trying to solve how he moved between each step.

We just finished our first assignment as a class and I have to say it was a fairly large assignment. Working on it for more than 6 hours straight each day is not how I saw my time off from school! But through struggling with the problems, I began to develop a stronger understanding of the topics we talked about in class and I think I am fairly knowledgeable with universal/existential quantifiers, negations, and how math symbols can be transferred into the English language.

One of the questions that gave me trouble (that I was glad to solve) is:

Initially, I did not know how to solve it. But as I went to this weeks tutorial, we were talking about equivalences and how to use the laws to prove things are equal. It was then that I realized I could do the same to answer the question and slowly but surely, the answer began to develop.