Problem Solving: Penny Piles

The problem of "penny piles" was presented on March 13th, on account of half the class being brain-dead from taking the CSC148 test.

The Problem: There are two drawers of pennies, and the basic premise involves taking half the pennies in one drawer and putting it in the other (if number of pennies is divisible by two) to make any combination of pennies. The question is if every combination is possible, and what happens when you start with different amount of pennies.

The Plan: Despite not having taken the exam that morning, neither my partner and I were really up for much thinking, so our plan was basically the same as for the other problem solving exercises: do random things until we find a pattern, and then think about why the pattern works.

In class, we tried working backwards and semi-systematically found almost every combination of numbers (we got lazy and did not actually finish the chart containing numbers). What we could have done instead that would have been very similar was draw a tree diagram of the possible results of the original problem of 64 pennies in the left drawer and none in the right drawer, which I have painstakingly recreated here:

(The right half of this tree repeats itself but in different order so I have omitted a large part of it.)

This tree diagram shows that it is possible, if we include the amount in both drawers, to make every number between 0 and 64 if we start with 64 and 0 in the left and right drawers respectively. This is likely the least elegant way to prove such a thing.

Looking back: After having carried out the plan, it worked reasonably well, but our initial thinking should have been more organized and we should have had a tree structure to begin with. 

The end of proofs.

The past few weeks on proofs were not difficult at all. However, I seem to be doing really poorly on the quizzes, partly because I haven't been attending the tutorials (because I can't, really.) and partly because I apparently just have trouble taking assessments in this class because I keep over-thinking things and psyching myself out.

As far as proofs go I'm pretty confident with the material, having done plenty of proofs in MAT240/247, I'm just lacking in assessment-taking skills, which has never been a problem before. I'm not really sure what to do about that.

This week we finished proofs and started to look at running time and big O notation. It makes sense so far, but I wonder if it will get harder.

I asked Prof. Danny if induction would be covered in the course and the answer was negative, but I may take a look at the induction part in the course notes that was not covered as a personal interest. 

Problem Solving: Diagonals

On Friday Feb. 15, we were given the "diagonals" problem in class. It seemed easy enough at first. But, as it turns out, my initial solution was far from perfect.

The problem: Draw a diagonal in a rectangle of m rows and n columns. Find out how many of the grids the line passes through the interior of.

The plan: As with folding, make enough examples to find a pattern.

We drew rectangles from 1x1... 2x1... 2x2 up till 5x5, and from there devised a pattern:
   -for m is odd, the number of shaded squares is m + n - 1 if m != n
   -for m is even, the number of shaded squares is m + 2 [[(n-1)/2]] (where [[]] is the floor function) if m != n
   -for m = n, number of shaded squares is simply m or n.

I showed my solution to Professor Danny who informed me that there were problems with my solution involving multiples. So I made a bunch more examples and compiled that into a new chart.

	n
m		1	2	3	4	5	6	7	8	9	10
	1	1	2	3	4	5	6	7	8	9	10
	2	2	2	4	4	6	6	8	8
	3	3	4	3	6	7	6	9	10
	4	4	4	6	4	8	8	10	8		12
	5	5	6	7	8	5	10	11	12
	6	6	6	6	8	10	6	12	12		14
	7	7	8	9	10	11	12	7	14
	8	8	8	10	8	12	12	14	8		16
	9	9								9
	10	10			12		14		16		10

The 9 and 10 columns are incomplete because I ran out of space and didn't actually draw them. I noticed that the pattern was only broken when m was divisible by n or n was divisible by m. (but sometimes not even then).

It seems, from the exceptions I found in the chart I made (3x6 and 4x8) that the number of shaded squares is then equal to max(m,n), which also works for 2x4. So I think adding this condition, if m%n ∈ℕ then number of squares the diagonal passes through = max(m,n) would fix the pattern. 

Looking back: I didn't really get stuck anywhere, it was a fairly straightforward process, though I stopped working on it for a while after class. I still don't know if I have the complete solution (probably not, this did not take nearly enough time) but so far I didn't really get stuck.

Deltas, Epsilons, and Test 1

The first test happened.

It turns out I managed to completely over-think one question and it would have actually been better if I pretended not to have learned delta-epsilons in "Calculus!".

The good thing is, I completely understand my mistake and it would not happen again. The bad thing is... I still made significant mistakes. Instead of using standard negation I decided to remember what minuscule quantities of formal proof-y calculus I retained from last semester and that simply did not work out well for me. Minor panic and self-deprecating humor ensued in a conversation I had with a friend after the test answers were posted.

Lesson of the day: don't be stupid when taking a test...

Also, I clearly do not understand delta-epsilon as well as I thought I did, which makes me a sad panda.

Problem Solving: Folding

This post covers the "Folding" problem as done in class for one dimension, plus a bit of what I did on my own. If I have time, I will hopefully follow with a post that solves the problem for two dimensions.

The problem asks for the sequence of ups and downs in creases given that one folds a strip of paper in a particular way. Our initial plan was to simply fold it a couple of times and record the pattern. (We had a plan B, which was actually thinking about how/why the folds actually were the way they were mathematically, but it made more sense to start with examples).

This was done with a chart that looked something like this:

fold	pattern
1	∨
2	∧ ∨ ∨
3	∧ ∧ ∨ ∨ ∧ ∨ ∨
4	∧ ∧ ∨ ∧ ∧ ∨ ∨ ∨ ∧ ∧ ∨ ∨ ∧ ∨ ∨

There seemed to be a pattern, but we did not quite grasp it until a light bulb suddenly lit up over my head and I re-recorded the folds so they aligned with folds from previous folds, so something like this:

fold	pattern
1	∨
2	∧∧∧∧∨∧∧∧∨
3	∧∧∧∧∨∧∨∧∧∧∨∧∨
4	∧∧∨∧∧∨∨∨∧∧∨∨∧∨∨

It became apparent that each time we folded the paper, it was inserting an up-down repeating pattern between the old folds. We all understood the pattern pretty well, but we could not figure out a mathematical way to describe it in class.

I later came up with a block of python code that works for the first three folds:

def folding(fold):
    '''(int) -> (list of str)
    return pattern of folds'''
    L = []
    i = 0
    while i <= (2**fold - 2):
        if i % 2 == 0:
            if i % 4 == 0:
                L.append('up')
            elif i % 4 == 2:
                L.append('down')
        elif i % 2 == 1:
            if i % 4 == 1:
                if i % 8 == 1:
                    L.append('up')
                elif i % 8 == 5:
                    L.append('down')
            elif i % 4 == 3:
                L.append('down')
        i += 1
    return L

Unfortunately, this only works up to fold 3. For it to work for more folds, it would be necessary to either write a ridiculous amount of code... or use recursion. Which I simply do not know how to do very well yet. However, at least for the first three folds:

folding(3)

['up', 'up', 'down', 'down', 'up', 'down', 'down']

folding(2)

['up', 'up', 'down']

folding(1)

['up']

If I have time to return to this problem, I will actually write python code that gives an actual solution, as well as tackle the two-dimensional version of this problem in part II. 

And Implies Or

Last week was mostly spent continuing to represent English statements in logical symbols, so, for example, A^B => AvB, as A and B is a subset of A or B.

However, A^B is clearly not the same thing as AvB. So, applying that, when the sign outside MP103 says "NO FOOD AND DRINKS", clearly they meant that I can have a can of coke or a yummy sandwich, just not both together. (Which is probably why some kind individual surreptitiously scratched out the "AND" and replaced it with "OR", which is probably what the original author intended.)

I am under the impression that so far, by covering the differences between 'and' and 'implies', we're secretly being introduced to truth tables (which are more clear about the difference, in my humble opinion) without a lot of the technical mumbo-jumbo that tends to make students' brains go haywire and shut down in panicked self-defense.

However, that did not stop one brave student's outcry at various counter-intuitive but logical claims, which was by far the most entertaining part of that particular lecture. 

Quantifiers: four different representations

The first three classes of CSC165 saw the introduction of two key quantifiers (universal and existential), at first disguised as python code, then in the context of a word problem, illustrated with Venn diagrams and finally in terse mathematical symbols.

It was most fun to figure out on my own how each statement relating to the scenario of employees/salary (a scenario that raised social issues, questioned gender inequality in the workplace, and included a thoroughly mysterious woman with a yearly salary of $500), and I found it interesting to find all the different ways of representing a single English statement. "All employees make over 9000$", for example, can be written as python code, in math with sets/subsets or union/intersections, and illustrated by a Venn diagram.

My biggest problem remains the fact that I am not actually yet enrolled in the class.Thus far, I have found the class very manageable, and the topics well-explained and easy to understand. It also helps that I happen to be extremely fond of Venn diagrams.