Now that there is a lively discussion on the forum, I'm not sure what to post here anymore. Mostly I want to discuss specific issues and the forum provides faster feedback. I don't want to double-post either.
Sigh!
Tuesday, November 18, 2008
Thursday, October 30, 2008
Pennies problem -- proof
The problem:
You stand in front of two drawers in a table, which you open. The left drawer is empty, but the right drawer has 64 pennies in it, according to your count. On the table is a challenge:
Can you rearrange the pennies so that the left drawer has p pennies in it, where 0 <= p < 64? To accomplish this task, there are two moves that you can make:
R - if the number of pennies in the right drawer is even, move half the pennies to the left drawer.
L - if the number of pennies in the left drawer is even, move half the pennies to the right drawer
Note: closing and reopening the drawers will cause the pennies to magically return to their starting state.
So, to start off with, I could move 32 pennies from the right drawer to the left drawer, resulting in 32 pennies in each drawer. Then, I could move 16 pennies from the left drawer back to the right drawer, resulting in 16 pennies in the left drawer and 48 in the right drawer. Or, I could do 6 R moves resulting in 1 penny in the right drawer and 63 in the left one. Or I could do one R move and 5 L moves resulting in 1 penny in the left drawer and 63 in the right one. Of course, once I reach an odd number, I close the drawers and reopen them to reset the puzzle.
Obviously, if I am to make any move at all, there must be an even number of pennies in one of the drawers. In fact, I must start off with an even number of pennies or I can make no move at all! That implies that, if I am to make a move, there must be an even number of pennies in each drawer, since the total number of pennies must be even to begin with. Suppose that I have j pennies in the left drawer and k pennies in the right drawer. I can represent this by an ordered pair:
(j,k), where j and k are natural numbers
Since j and k must be even (otherwise there is no legal move), there must be natural numbers j' and k' such that j = 2j' and k = 2k', respectively, by the definition of even numbers. That means that, after an L move, for example:
L
(j,k) --> (j/2,k+j/2)
which is the same as:
L
(2j',2k') --> (2j'/2, 2k'+2j'/2) = (2(j'/2), 2(k'+j'/2)) (*)
At this point, it's worth observing that that we need to limit ourselves to starting numbers of pennies that are powers of two. If they are not, then there must be some move that will result in an odd number of pennies > 1. For example, say you start with 12 pennies. One L or R move gets you six in each drawer. The next move gets you 3 in one drawer and 9 in the other. That's all you can do. So, we'll restrict ourselves to powers of two. It is interesting to see if this is possible for any power of two. In other words, if I start with 2^k pennies in the right drawer, where k is a natural number, and 0 pennies in the left drawer, can I find a sequence of moves that will produce 1 <= p <= 2^k - 1 pennies in the left drawer?
Let M be the set of all possible move sequences -- that is, all possible combinations of L and R moves. Let P(k) be the predicate:
P(k) for natural numbers k and all natural numbers p such that k > 0, 0 < p < 2^k, there exists a sequence of moves m_0, m_1, ... m_i, for some natural number i, in M such that (0,2^k) --> (p,2^k-p) after i moves.
Claim: For all natural numbers k, P(k)
Basis: k = 1
Then the starting point is (0,2^1) = (0,2)
There is only one valid move: R, which results in (1,1)
Thus (0,2^1) = (0,2^k) --> (p,2^k-p) = (0,2) after 1 move, m_0
Then P(1) is true
Induction step:
Assume k is a natural number > 0. Assume P(k) is true. We need to show that P(k+1) holds. Indeed, our starting point is:
(0,2^(k+1) = (2*0, 2*2^k)
We know, by the induction hypotheses, that that there exists a sequence of moves m in M such that (0,2^k) --> (p,2^k-p) for all natural numbers p such that 0 < p < 2^k after p_i moves. Applying the same sequences to our new starting point will produce the result:
(0,2*2^k) --> (2p, 2*2^k-2p)
since 2*2*k/2 = 2k for all natural numbers k. From here, we can make an additional move:
(2p, 2^k-2p) --> (p, 2*2^k-2p+p) = (0, 2^(k+1)-p)
as wanted. Thus P(k+1) holds and P(k) implies P(k+1).
Conclusion:
Since P(0) holds and P(k) implies P(k+1), for all natural numbers k > 0, I conclude that P(k) holds for all natural numbers k by the principle of simple induction.
Corollary:
Since every combination of even numbered pairs can be reached, every even-numbered pair can be further divided. Let 2a and 2b be the number of pennies in the left and right drawers such that 2a+2b = 2^(k+1) and a, b > 0. Then 2a and 2b are even numbers, by the definition of even numbers. Without loss of generality, applying one left move to this pair results in the transformation:
(2a,2b) --> (2a+b, b), for all natural numbers a, b such that 2a+2b = 2^k
If b is even, we can repeat the same move until we reach a pair where the right-hand
number is odd. At that point, both numbers are odd, since 2n is even by definition and 2n + m where m is odd results in an odd number. Thus all odd numbers can be reached as well.
You stand in front of two drawers in a table, which you open. The left drawer is empty, but the right drawer has 64 pennies in it, according to your count. On the table is a challenge:
Can you rearrange the pennies so that the left drawer has p pennies in it, where 0 <= p < 64? To accomplish this task, there are two moves that you can make:
R - if the number of pennies in the right drawer is even, move half the pennies to the left drawer.
L - if the number of pennies in the left drawer is even, move half the pennies to the right drawer
Note: closing and reopening the drawers will cause the pennies to magically return to their starting state.
So, to start off with, I could move 32 pennies from the right drawer to the left drawer, resulting in 32 pennies in each drawer. Then, I could move 16 pennies from the left drawer back to the right drawer, resulting in 16 pennies in the left drawer and 48 in the right drawer. Or, I could do 6 R moves resulting in 1 penny in the right drawer and 63 in the left one. Or I could do one R move and 5 L moves resulting in 1 penny in the left drawer and 63 in the right one. Of course, once I reach an odd number, I close the drawers and reopen them to reset the puzzle.
Obviously, if I am to make any move at all, there must be an even number of pennies in one of the drawers. In fact, I must start off with an even number of pennies or I can make no move at all! That implies that, if I am to make a move, there must be an even number of pennies in each drawer, since the total number of pennies must be even to begin with. Suppose that I have j pennies in the left drawer and k pennies in the right drawer. I can represent this by an ordered pair:
(j,k), where j and k are natural numbers
Since j and k must be even (otherwise there is no legal move), there must be natural numbers j' and k' such that j = 2j' and k = 2k', respectively, by the definition of even numbers. That means that, after an L move, for example:
L
(j,k) --> (j/2,k+j/2)
which is the same as:
L
(2j',2k') --> (2j'/2, 2k'+2j'/2) = (2(j'/2), 2(k'+j'/2)) (*)
At this point, it's worth observing that that we need to limit ourselves to starting numbers of pennies that are powers of two. If they are not, then there must be some move that will result in an odd number of pennies > 1. For example, say you start with 12 pennies. One L or R move gets you six in each drawer. The next move gets you 3 in one drawer and 9 in the other. That's all you can do. So, we'll restrict ourselves to powers of two. It is interesting to see if this is possible for any power of two. In other words, if I start with 2^k pennies in the right drawer, where k is a natural number, and 0 pennies in the left drawer, can I find a sequence of moves that will produce 1 <= p <= 2^k - 1 pennies in the left drawer?
Let M be the set of all possible move sequences -- that is, all possible combinations of L and R moves. Let P(k) be the predicate:
P(k) for natural numbers k and all natural numbers p such that k > 0, 0 < p < 2^k, there exists a sequence of moves m_0, m_1, ... m_i, for some natural number i, in M such that (0,2^k) --> (p,2^k-p) after i moves.
Claim: For all natural numbers k, P(k)
Basis: k = 1
Then the starting point is (0,2^1) = (0,2)
There is only one valid move: R, which results in (1,1)
Thus (0,2^1) = (0,2^k) --> (p,2^k-p) = (0,2) after 1 move, m_0
Then P(1) is true
Induction step:
Assume k is a natural number > 0. Assume P(k) is true. We need to show that P(k+1) holds. Indeed, our starting point is:
(0,2^(k+1) = (2*0, 2*2^k)
We know, by the induction hypotheses, that that there exists a sequence of moves m in M such that (0,2^k) --> (p,2^k-p) for all natural numbers p such that 0 < p < 2^k after p_i moves. Applying the same sequences to our new starting point will produce the result:
(0,2*2^k) --> (2p, 2*2^k-2p)
since 2*2*k/2 = 2k for all natural numbers k. From here, we can make an additional move:
(2p, 2^k-2p) --> (p, 2*2^k-2p+p) = (0, 2^(k+1)-p)
as wanted. Thus P(k+1) holds and P(k) implies P(k+1).
Conclusion:
Since P(0) holds and P(k) implies P(k+1), for all natural numbers k > 0, I conclude that P(k) holds for all natural numbers k by the principle of simple induction.
Corollary:
Since every combination of even numbered pairs can be reached, every even-numbered pair can be further divided. Let 2a and 2b be the number of pennies in the left and right drawers such that 2a+2b = 2^(k+1) and a, b > 0. Then 2a and 2b are even numbers, by the definition of even numbers. Without loss of generality, applying one left move to this pair results in the transformation:
(2a,2b) --> (2a+b, b), for all natural numbers a, b such that 2a+2b = 2^k
If b is even, we can repeat the same move until we reach a pair where the right-hand
number is odd. At that point, both numbers are odd, since 2n is even by definition and 2n + m where m is odd results in an odd number. Thus all odd numbers can be reached as well.
Proving functions are non-decreasing
I find the concept that recursive functions can be proven to be non-decreasing. Now, I'm wondering: What about non-recursive functions? For example, how would one go about proving that log, or square root, or exponentiation functions are non-decreasing? Do we simply accept that as axiomatic? For example, I know that log(1) is zero in every base and that log(base) is 1 for every base. What about values between 1 and base? I'd like to prove that they are non-decreasing, that is, for any value v between 0 and base, 0 <= log(v) <= log(base). Then I'd like to be able to show that this is true for any v > 0. That is if I have 0 = < v1 <= v2 for any real numbers v1 and v2, how can I prove that:
0 <= log(v1) <= log(v2)
What about other functions, like roots or powers or in general any polynomial with real powers? How could I prove that, for all real numbers r s.t. 0 <=r < 1, the root function on those numbers is non-decreasing for any real root a. (e.g. the square root of 1/4 is 1/2 which is less than the cube root of 1/4 (approx 0.63) or that for reals >= 1, the function is non-increasing?
I'd just like to be able to justify statements like "sqrt function is non-decreasing for values >= 1) or "log function is non-decreasing for values > 0." I suppose that there are tons of other similar functions that fall into the same category as well (though not sine or cosine, of course, except with appropriate bounds).
0 <= log(v1) <= log(v2)
What about other functions, like roots or powers or in general any polynomial with real powers? How could I prove that, for all real numbers r s.t. 0 <=r < 1, the root function on those numbers is non-decreasing for any real root a. (e.g. the square root of 1/4 is 1/2 which is less than the cube root of 1/4 (approx 0.63) or that for reals >= 1, the function is non-increasing?
I'd just like to be able to justify statements like "sqrt function is non-decreasing for values >= 1) or "log function is non-decreasing for values > 0." I suppose that there are tons of other similar functions that fall into the same category as well (though not sine or cosine, of course, except with appropriate bounds).
Tuesday, October 21, 2008
Assignment 2
So, Assignment 2! Finally I get to finish off Ternary Trees. I've got a working formula; hope the proof makes sense.
Question 2 should lead me to something with log(base 7) in it. Of course I can change it to lg since if log7(a) = x then x.lg(7) = lg(a) by simple algebra:
log7(a) = x ==> 7^x = a (what log7) means!
lg(7^x) = lg(a), taking lg (log base 2) of both sides
x.lg(7) = lg(a), by 3rd law of logarithms
so that's not so bad. Still, I guess we need to prove it for non-powers-of-7. Since we did something like it in class for mergesort, that's probably a good example to follow.
Question 3: looks like G(n) = 1, if n <3; G(n) = if n >= 3 will do it (I guess I shouldn't post my formula in public, especially if it's wrong!)
Question 4: Two things occur to me: 1. The method used to divide the problem is not that relevant to the proof, so long as it produces an index between b and e, inclusive. 2. I cannot conceive that this question would be here if there were a counterexample. Sounds too much like a trick to me and wouldn't help me learn proof techniques.
So, I guess I'll prove it, if I can. Probably the approach in the course notes for proving recursive binary search will work. Hope I can use that without it looking too much like copy and paste.
Question 2 should lead me to something with log(base 7) in it. Of course I can change it to lg since if log7(a) = x then x.lg(7) = lg(a) by simple algebra:
log7(a) = x ==> 7^x = a (what log7) means!
lg(7^x) = lg(a), taking lg (log base 2) of both sides
x.lg(7) = lg(a), by 3rd law of logarithms
so that's not so bad. Still, I guess we need to prove it for non-powers-of-7. Since we did something like it in class for mergesort, that's probably a good example to follow.
Question 3: looks like G(n) = 1, if n <3; G(n) =
Question 4: Two things occur to me: 1. The method used to divide the problem is not that relevant to the proof, so long as it produces an index between b and e, inclusive. 2. I cannot conceive that this question would be here if there were a counterexample. Sounds too much like a trick to me and wouldn't help me learn proof techniques.
So, I guess I'll prove it, if I can. Probably the approach in the course notes for proving recursive binary search will work. Hope I can use that without it looking too much like copy and paste.
Friday, October 3, 2008
Ternary Trees
I finally stumbled upon a formula for the Ternary Tree question. Never thought i would take three weeks! Three weeks, thinking about it several hours a day, losing sleep over it, doodling endlessly on napkins, envelopes, toilet paper, bills. Wow is all I can say.
Wednesday, October 1, 2008
Program Proofs
I began reading chapter 3 on program proofs last night. Once again I was struck by the length of the proof for a simple program -- two pages or so for a 10-liner! This is clearly not scalable. The effort (not to mention paper) required to prove a real-world project would dwarf that required to write it in the first place. Small wonder that gcc, Oracle, the Solaris kernel, Adobe CS4, Apache or Asterix (just to name a few large-scale, real-world projects) do not come with proofs, as far as I know. Were anyone to begin to work on proofs for even a small subsystem of these, they'd be up for retirement long before they could finish.
The method given for program proofs also seems to omit critical aspects -- side effects. It is fine to show that a program produces the required output when given proper inputs, but if it leaks memory or stomps on memory it doesn't own or opens holes that can be exploited to break security, or calls routines that require cleanup but doesn't call the cleanup routines, etc., the "proof" is positively pyrrhic.
The author claims that some software organizations require a declaration of loop invariants, if not complete proofs. Maybe I'm from Missouri, but I need names so that I can follow up and confirm it. None of the software organizations I have worked in have ever required anything like that. My experience has shown me that software projects have tight schedules and even tighter budgets. Code needs to be commented, to be sure, and tested (usually by a separate team), but proven? Hardly!
Finally, a rhetorical question: How would you prove a program when the ultimate test of correctness is that the customer is satisfied it does what he wants? For example (a simple one. It's not hard to come up with a gazillion others), say you want to add a red-eye reducer to your photo program. How do you know it works? You only know that if the user is satisfied with the results. Oh, maybe you can prove that your program does the "right" thing in terms of what it does, pixel by pixel, but if the user still thinks it's garbage, your proof is worthless, both to you and your user.
The method given for program proofs also seems to omit critical aspects -- side effects. It is fine to show that a program produces the required output when given proper inputs, but if it leaks memory or stomps on memory it doesn't own or opens holes that can be exploited to break security, or calls routines that require cleanup but doesn't call the cleanup routines, etc., the "proof" is positively pyrrhic.
The author claims that some software organizations require a declaration of loop invariants, if not complete proofs. Maybe I'm from Missouri, but I need names so that I can follow up and confirm it. None of the software organizations I have worked in have ever required anything like that. My experience has shown me that software projects have tight schedules and even tighter budgets. Code needs to be commented, to be sure, and tested (usually by a separate team), but proven? Hardly!
Finally, a rhetorical question: How would you prove a program when the ultimate test of correctness is that the customer is satisfied it does what he wants? For example (a simple one. It's not hard to come up with a gazillion others), say you want to add a red-eye reducer to your photo program. How do you know it works? You only know that if the user is satisfied with the results. Oh, maybe you can prove that your program does the "right" thing in terms of what it does, pixel by pixel, but if the user still thinks it's garbage, your proof is worthless, both to you and your user.
Tuesday, September 23, 2008
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)
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)
Monday, September 22, 2008
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.
Tuesday, September 16, 2008
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.
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.
Monday, September 15, 2008
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.
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.
Saturday, September 13, 2008
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.
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.
Friday, September 12, 2008
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.
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.
Subscribe to:
Comments (Atom)
