[Tutor] Problem

[Shahan Khan]

I understand your argument. You're saying M(50),M(51)and M(52) is basically a set of 6 9 and 20 packs and we should approach it by using lower values starting from 0 for one or two variables to simply the solution on paper. I think I have some idea now as to how to approach this problem.

Sent from my iPhone

> On 29-Aug-2016, at 5:18 AM, Danny Yoo <dyoo at hashcollision.org> wrote:
> 
>> On Sun, Aug 28, 2016 at 7:46 AM, shahan khan <shahankhan0 at gmail.com> wrote:
>> Hello
>> I'm teching myself Python using MIT opencourse ware. I'm a beginner and
>> have some what knowledge of c and c++. I'm using Python version
> 
> 
> 
>> Here is my code:
> [code cut]
> 
> Before showing code, try to express what you're trying to do in
> English first.  That is, your explanation near the bottom:
> 
>> I'm using for loops to give possible valutes to a,b and c and then using the equation (6*a)+(9*b)+(20*c) to determine possible values for a,b and c for
> satisfying the equation.
> 
> ... this should actually be presented because it's the most important
> part!  The problem with code is that code just executes. Any
> expectations we have about what that code does is a matter of human
> interpretation.
> 
> 
> 
> Anyway, from looking at your original code (modulo indentation), I
> *think* the treatment as a search problem, looking for the values of
> the parameters a, b, c is reasonable, with the way you're doing nested
> for loops,
> 
>> for a in range(1,10):
>>     for b in range(1,5):
>>         for c in range(1,5):
> 
> However, I am not entirely convinced that the search bounds are
> actually sound.  Here's why: I don't know why the numbers 1, 10, 5,
> and 5 were chosen in the loop: they seem arbitrary, and you need to
> say where those numbers came from.  I suspect there's a problem with
> them anyway.
> 
> 
> One concrete reason why I don't think it works: change the problem
> slightly.  Say that we're trying to find a solution for the parameters
> where the Diophantine equation evaluates to 6.  Basically, the really
> simple edge case.
> 
> What change would you make to your code for this simpler case?  I'd
> assume that the simplest thing to do would be to change the target
> value in the test expression, from:
> 
>    if mc==50: ...
> 
> to
> 
>    if mc == 6: ...
> 
> 
> Now, before we even try your program, we *know* there's a trivial
> solution for a, b, and c such that the equation sums to six!
> 
>    a = 1
>    b = 0
>    c = 0
> 
> However, looking back at program structure, we can see, even without
> looking at the rest of the code, that it can't possibly consider such
> parameters, because it's assuming that all three variables have to be
> positive.
> 
> So that's something that we know needs to be fixed in some way.
> 
> 
> 
> My take on the problem: this sounds very much like a question begging
> for a dynamic programming approach, rather than a nested loop
> approach.  The reason I say this is because of the part of the problem
> statement:
> 
> ###############################################################
> Theorem: If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some
> x, then it is possible to buy any number of McNuggets >= x, given that
> McNuggets come in 6, 9 and 20 packs.
> ###############################################################
> 
> would be the beginning of a mathematical induction proof, which is the
> scent of a dynamic programming problem.
> 
> 
> I'd sketch this as follows: let's call M(n) a boolean function on the
> natural numbers that's true if we can buy n McNuggets by *any*
> combination of 6, 9, and 20 packs.
> 
> We know that:
> 
>    * M(6) is true
>    * M(9) is true
>    * M(20) is true
> 
> Why?  Because we can take a single 6-pack, or a single 9-pack, or a
> single 20-pack, and each of these is a way to buy 6, 9, or 20
> McNuggets.
> 
> From that core collection of knowledge, that inductive base, we can
> start investigating what else we can discover by building upon that
> knowledge inductively.
> 
> 
> Example: we know that since M(6) is true, that M(12) is true, because
> we can include another 6-pack to the one that built up M(6).
> Furthermore, we know that M(15) is true, because M(6) is true, and we
> can include another 9-pack to the one that built up M(6).
> 
> 
> What about M(50)?  Well, not quite sure.  However, I do know this: if
> M(50) is true, then *at least one* of the following has to be true:
> 
>   a.  M(44) is true
>   b.  M(41) is true
>   c.  M(30) is true
> 
> How in the world would we know this?
> 
> Because if we were able to make 50 McNuggets out of a collection of 6,
> 9, or 20 packs, then we have to have picked one of those packs.  And
> the remainder, outside of that pack, is where we get 44, 41, or 30.
> 
> We don't have absolute knowledge here: it's *conditional* because we
> don't yet know if M(44), M(41), or M(30) is true.  But it's a start.
> 
> I don't want to say too much more about this.  The reason is because
> if I state the idea just a little bit more formally, it suddenly looks
> a heck of a lot like a direct problem solution.  But I hope that gives
> you some ideas.
> 
> See: https://mail.python.org/pipermail/tutor/2016-July/109391.html for
> some links to dynamic programming material.