On Aug 16, 11:04 am, Baba <raoul...@gmail.com> wrote: > Hi Chas, Roald, > > These are all complicated formula that i believe are not expected at > this level. If you look at the source (see my first submission) you > will see that this exercise is only the second in a series called > "Introduction to Programming". Therefore i am convinced that there is > a much simpler solution.
The question I was responding to (a different one than your original question) was whether there was a proof of Baba's conjecture that a largest unobtainable quantity was possible if, and only if, the three numbers in question had a gcd of 1. Roald had something like a "gut feeling" that it was true, but such things are generally much more clear cut than "gut feelings" - they can often easily be /proven/ to be true or false, given the right mental tools. In this case, that proof I gave doesn't immediately yield a concrete answer to your /original/ question - assuming that a largest obtainable solution is possible, /how/ do we find the largest unobtainable solution? But it certainly identifies the conditions whereby we can easily and quickly say that there is no such solution, or conversely that such a solution must exist; and that is often extremely helpful to finding an algorithm that /does/ answer your original question. (One thing it does provide is an upper bound to the space of solutions that you should be looking at - and finding upper bounds and lower bounds is a common programming task. Again, this isn't something that you might be "expected" to know about at your level of study, but it doesn't hurt you to be aware of it either :)!) > > Now, i believe that the number of consecutive passes required to make > this work is equal to the smallest number of pack sizes. That is your belief, your intuition; and developing good intuitions is good... BUT... > So if we have > packs of (9,12,21) the number of passes needed would be 9 and... ... and now whatever you might go on to add is simply "going off into the weeds", because I have just proven that there can be /no/ such solution in that case: all three of those numbers are divisible by 3, so you are not "on the trail" when trying to figure out a general solution by considering examples of the type you mention. At your level of study, such things may seem overly complicated (and are certainly /not/ required to simply answer the question as originally stated). But consider the thread in this group called "python interview questions": http://groups.google.com/group/comp.lang.python/browse_frm/thread/bb4d3514e9842f9e# The "FizzBuzz" question involves a similar very basic grasp of the type of mathematical reasoning and thinking that is most valued in programmers in the job market. Of course, your Python class is not the right place to be focusing exclusively on this sort of mathematics, but I would encourage you to simultaneously educate yourself both in the /language/ learning of Python (which is what your class is largely about), along with the more universally applicable skill set that comes from understanding the mathematical justifications of a "good" algorithm That additional knowledge will serve you equally well whether you are programming in Python, Perl, Ruby, Java, C++, D, F, R, and so on (surely someone will claim "Z" as a language soon, if they haven't already...). > ... the > theorem would read > > "If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to > buy any number of nuggets >= 9 given that they come in packs of > 9,12,21" > So I would ask as a simple exercise: how would you go about /proving/ that your assertion is actually a /theorem/, and not just a pretty solid hunch that your statement is true because for small enough numbers you can easily "do it in your head"? Yes, it's "clearly true", but that is not a proof! That is the muscle which is exercised by mathematical reasoning. > However i turn in circles because i don't seem to get any results for > some random pack combinations like (9,12,21) or (10,20,30). > Well, your intuitions are certainly close to the mark. But if you added to your study a course on discrete mathematics, then you would also immediately see why such turning in circles obviously can bear no fruit, and that would give you a great advantage in solving far more difficult and yet common problems of this type. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
