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)
Subscribe to:
Posts (Atom)
