Piles of Pennies redux

Problem: https://wwwcgi.cdf.toronto.edu/~heap/cgi-bin/Solvent/wiki.pl?Problem_Solving_Home_Page/PennyPiles

Understanding:

We are first asked if it is possible to use the given operations to achieve a result so that one of the drawers has 48 pennies. We are constrained in that the two operations transfer half the pennies from L to R or R to L respectively, but only if there are an even number of pennies in the drawer on which we wish to operate. Since we start with no pennies in the right drawer and 64 in the left, we can do this in two operations:

L -- move half the pennies, that is 64/2 = 32 to the right drawer. Now the left drawer has 32 pennies in it, as does the right drawer.

L -- move half the pennies from the left drawer to the right drawer. That is, move 32/2=16 pennies from the left drawer, adding them to the 32 already in the right drawer, yielding 48 pennies in the right drawer.

The second part of the problem is to try to find a sequence of operations so that one of the drawers has other numbers in the range [0,64].

It is possible to produce one number in the range [0,64]. We just did that with 48 pennies. A second example would be that six left moves leaves one penny in the left drawer and 63 in the other. Along the way to (1,63) we also produce (32,32), (16,48), (8,56), (4,60), and (2,62). So it is indeed possible to produce other numbers in the range [0,64] in one of the drawers.

Though the problem as stated does not ask the question, it is interesting to see if it is possible to produce ALL numbers in the range [0,64] in one of the drawers. That may be possible if we add an additional operation. We just showed how to produce (1,63). Unfortunately, at that point, there is no way to produce any other number of pennies in either drawer, since both drawers now have an odd number of pennies. There needs to be at least one additional operation:

DR - at any point, you can dump all the pennies from the right drawer into the left drawer.

It is also useful to add a fourth rule:

DL - at any point, you can dump all the pennies from the left drawer into the right drawer.

The addition of these two rules will mean that it is possible to produce any number of pennies in the range [0,64] in either the left drawer or the right drawer.

The problem also asks about other starting numbers. Well, first off, an odd number won't do, since you can't make any move (other than 1/2 of 0!). So the starting numbers have to be even. But not just any even numbers. For example, try 30. You can do one move: 15 from one drawer to the other. Then you stop. In fact, this will eventually happen for all even numbers, except powers of 2. In fact, I believe that for any power of two, you can use the operations to produce any number from 0 to 2^k in both drawers (though not at the same time)

Ternary Trees

So...I spent most of the weekend mulling over this problem. So far, I've probably spent 10-12 hours concentrated time and more than a week thinking about it off and on. I've drawn the tree sets for n=3, n=4 and n=5. Still no pattern has emerged that I can spot. At this point, it would be an understatement to say that I'm discouraged. More than that, I need to stop working on this and get on with other things. However, assuming that there is a formula, say f(n) that produces the number of non-equivalent trees (I'd rather say unique -- easier to say and understand), I can produce a proof easily enough. For the moment, I'll assume that I have such a formula. Who knows? Maybe one will show up before I hand it it.

Assignment 1

Just looking at assignment 1. It looks like the first question can be answered without induction using a standard Euclidean argument:

Draw lines from the points on the circle to the center.
That makes n triangles.
The total angles in each triangle is pi.
That gives n*pi angles
But the angles at the center add up to 2*pi since it's a circle
So total angles is (n-2)*pi

I guess I can shoehorn this into an inductive proof somehow.

Question 2 looks like it might best be handled recursively. Make a function that makes up combinations from some set. If the set is empty, return nothing. If set has one element, return that. If set has more than one element, build up subsets consisting of first element and the results of the function called recursively for all other elements. When you're all done, add the empty set as the final element.

Question 3 is harder than I thought at first. It's easy to show that, if n1/n2 = theta as defined in the problem, n1/n2 = n2/(n1-n2). Just some basic algebra. That leads us to n1^2 - n2^2 = n1n2. Something about that seems fishy, so I whipped up a little program to see if it is true. For the first 100,000 numbers, there is no pair that will satisfy the equation. So I think it's false. I just can't prove it. At. All.

Question 4? Looks like if n=0, NE trees = 1, n=1 NET = 1, n=2, NET = 3, n=3, NET=12, n=4,NET=72; n=5, NET=252. Can't see a pattern in that, recursive or otherwise.

Piles of Pennies

After looking at the piles of pennies problem, I think that the initial goal (48 pennies in one drawer) can be easily reached:

1. move 32 pennies (half of 64) from left drawer to right. That gives 32 pennies in each drawer.

2. move 16 pennies (half of 32) from left to right or vice versa. That gives 48 pennies in the right or left drawer respectively.

Voila!

The general problem (any number of pennies between 0 and 64 in either drawer) is not reachable under these rules. As you transfer pennies back and forth, you will eventually reach an odd number of pennies in each drawer, at which point no move is possible. That means (at least) that you can only reach one odd number using the above rules. I suspect that this will also limit the number of even solutions as well.

Problem set 1

I was just thinking about problem set 1. It looks like the first problem (unary digits of powers of 4) is a variation of the similar one for powers of 3 we did in class. Probably a similar approach will work. I think that the unary digits will always be 4 or 6, except for the case of 4^0, so I have to add 1 to the set as well. From there on, not too bad. since 4*4 ends in a 6 and 4*6 ends in a 4.

The second problem can be restated as an application of combinations of n objects taken 2 at a time. that would be (n!/(n-2)!)/2! which is of course n(n-1)/2 -- no proof required that way. Proving it by induction is an interesting problem. For the inductive step, I'll probably take the new element (the one that makes it n+1) and make tuples out of it and all the existing members. That plus the original tuples will probably do it.

First Lecture

My first 236 lecture was last night. The class was much fuller than I had anticipated with more than twice as many students as my 165 class. Once beyond introductory material, we began reviewing proofs by induction. One thing that surprised me was the idea that the carefully-crafted structures of 165 were not necessarily THE model for this course, but just one approach of many. This makes me wonder why 165 is so pedantic about proof structure. If it is not to be the model for other proofs within CS courses, what is it for?

I noticed that some of the examples (unit digits of powers of 3, or 12^n-1 = k*11) could be proven without induction -- maybe even better so. I suppose I would have preferred examples that couldn't be proven (or were very difficult to prove) without using induction. Still, there is value in looking at a problem from a fresh perspective.

First entry

This is my blog for CSC236. Hopefully something useful will turn up