Problem Solving Episode Thing

PROBLEM: Piles of pennies

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]? 

STEP 1 UNDERSTANDING THE PROBLEM:

You have two numbers, x and y. x is 64 and y is 0. The only operation that you can perform on these variables is: If one of the variables is an even number, add half of that variable to the other variable then divide the first variable by two.

Given this, is it possible to make x or y equal to all the numbers from 0 to 64.

It is possible to reach 48 by performing the operation on x twice.

STEP 2 DEVISING A PLAN:

One approach to this problem is to just start by randomly performing the operation and collect the data to see if there’s a pattern. Information obtained here may also help with other plans

Another approach is to try to work backwards. Start with your target x or y value and try to get back to x = 64 and y = 0. This can either be done for every x and y value, or a pattern can be found

A third approach is to look at the problem and try to think if there is a way to mathematically prove that it is possible for certain numbers

A fourth approach is to make a python program that can randomly do these operations until it has obtained every number from 0 to 64. (This is probably cheating).

STEP 3 CARRYING OUT THE PLAN:

Operation L halves x and operation R halves y.

Operation #	x	y	Operation performed
0	64	0
1	32	32	R
2	16	48	R
3	40	24	L
4	52	12	L
5	58	6	L
6	29	35	R

From these trials, it appears that an odd number is only obtained after 6 operations. This could be because 64 = 2⁶ and 2⁶ divided by 2 six times would obtain a 1. Also, we can note that we only need to find out if the numbers <32 or >32 can be obtained. This is because if x < 32, then y would be the counterpart number > 32 such that x + y = 64.

Looking at it another way, the pair 64,0 can be rewritten as 32(2), 0. This can then be operated on to become 16(2), 16(2). From here, it can be seen that the 2 is pretty much negligible. For example:

Operation #	x	y	Operation performed
0	16(2)	16(2)
1	8(2)	24(2)	L
2	20(2)	12(2)	R
3	10(2)	22(2)	L
4	5(2)	27(2)	R

At any step, 2 could simply be divided out by using the operation to get the desired number at that step. Thus, this would be like starting with x = 32 and y = 0 and finding if the numbers from 0 to 32 can be obtained. Similar to what was argued earlier, we would only need to find out if we could obtain numbers < 16.

We could then change it again to have 16(4), 0(4). We need to show that we can obtain the numbers < 8 to get the numbers [0, 16].

Then for 8(8), 0(8) we need to show we can obtain the numbers < 4 to get the numbers [0, 8]

Then for 4(16), 0(16) we need to show we can obtain the numbers less than 2 to get the numbers [0, 4]

Then we get to 2(32), 0(32). From here we see that 0 can be obtained and 1 can be obtained by doing operation L. So this means we can get [0, 4] which then means we can get [0, 8], which means we can get [0, 16], which means we can get [0, 32], which means we can get [0, 64].

STEP 4 LOOKING BACK:

What I did above is just speculation, I’m not sure if it entirely makes sense. I need to look over it more to see if it does. I could also make a tree with all the possibilities to check if the numbers from 0 to 64 are actually obtainable.

SLOG Final Week

Lectures:
There was only one lecture this week on Monday and I didn't bother to show up since it was a review class. Or at least that's what the CDF site says it is.

Assignment 3:
Some of the questions in assignment 3 were pretty simple such as the proof with the big omega since we had done many examples of those in class and in tutorials. However, the questions with l'hopital and halting were a lot more difficult since we didn't really get many examples from lectures or tutorials to help with them.

Overall thoughts on the course:
I thought this course was interesting. Learning how to properly use logical symbols and quantifiers really helped in being able to read some mathematical statements. My favorite part of the course though is the proof section, even though it was the hardest. Doing proofs and learning proof structure really helped teach me how to approach a proof question. Before that part of the course I was always really confused with proofs in calculus since I was not sure what we're allowed to do or how to even start the proofs.

Some issues that I had with this course is that it seemed kind of slow and repetitive at times. Going through all the proof examples during lectures helped remember proof structures a bit but it got really repetitive. Also, some of the content in the course such as quantifiers overlapped with what we learned in calculus.

Slog Week 11

 Lectures:
On the Monday lecture of this week, we talked more about diagonalization and showing what functions are not computable. I may need to look through these slides again because I'm still a bit fuzzy on the details. We also started a bit on induction on Monday. On Wednesday, the rest of induction was taught. I had actually skipped this lecture to prepare for my calculus test that I had later that day, but I'll probably just look through the slides anyways. Also, the induction stuff seemed pretty similar to what we did in calculus. Friday was just another problem solving day.

Tutorial:
The tutorial on Tuesday was pretty much the same as usual. Our TA changed things up by making us do the problem before showing us how to solve it. Unfortunately, our class was pretty quiet so only a few people answered.

Other stuff:
Going back to the halting problem that I had trouble understanding, I looked through the annotated slides this week. After a while of staring at the navel_gaze function I finally understood why inputting navel_gaze and navel_gaze into navel_gaze creates a contradiction. I was surprised at how that worked. I also need to start working on my assignment 3 that's due Monday. It doesn't look too difficult except for the last two questions.

SLOG Week 10

 Lectures:
This week was another shortened week due to fall break so there were no classes on Monday and no tutorials. What we learned this week mainly consisted of the idea that there are some problems that algorithms cannot compute. Such as finding out if a function would loop infinitely or not or finding out if a variable within a function were initialized. This seemed pretty interesting to me because I had previously thought that algorithms could be used to solve or compute any problems.

Difficulties:
I had some difficulties understanding what was happening in the lectures. I didn't really get what was happening during the explanations on why the halting function is not possible to create. Because of this I probably need to spend some time going over the annotated slides.

SLOG Week 9

Lectures:

This week we spent even more time practicing proofs for bounds. The limit stuff got a bit confusing though since I was not really sure what l’hopital’s rule is. The proof for bounds involving two functions was a bit hard to understand at first because of all the c’s, B’s and n’s, but it made more sense after we did a lot of questions relating to them.

Tutorials:

The tutorial this week was very helpful in understanding how to write proofs for bounds and the proper structure. I also forced myself to memorize the definition of bounds so I wouldn’t fail this week’s quiz, which is probably going to be helpful.

SLOG Week 8

Lectures:

This week we had some more practice with counting steps and proving bounds in class, we also had an assignment due and a test on Wednesday, so it was a pretty long week. As for the lectures, I was really confused at what was happening during the proof for the maximum slice function. I had absolutely no idea what was going on. I really need to spend some time to look over the annotated slides. The other bound proofs on the other hand are very straight-forward. 

Assignments/test:

For the assignment and the test, I had a lot of difficulty trying to find out how to apply the definition of floors to my proofs, so I probably did not do so well on those. I definitely need to look at the solutions before writing the exam.

Tutorial:
The tutorial this week was pretty straight-forward, although I kind of panicked on the quiz and forgot what the equation for 1+2+3+...+ n was. 

SLOG Week 7

Lectures:

This week we started talking about counting steps, which was not too hard for me since I’ve taken computer science courses before back in high school. Learning how to prove upper and lower bounds seemed a bit confusing though. It took a while to understand what you are allowed to do in the proof and how you can manipulate inequalities and I probably need some more practice with it before I can confidentially do those proofs. It is also a pain trying to remember the entire definition of upper and lower bounds.

Tutorials:

As for this weeks tutorials, I had actually skipped it because I was too lazy to get up in the morning.