Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tough Diophantine Equation

  1. Jan 2, 2008 #1
    I was reading XKCD and I found this:
    [​IMG]
    I have no idea how to solve it. I know 7 orders of mixed fruit is one solution, but I only got that through trial and error. Does anyone know how to find every solution?
     
  2. jcsd
  3. Jan 2, 2008 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    It's a knapsack problem, programming the most efficient way to solve it is a nice challenge :smile:
     
  4. Jan 2, 2008 #3
    So... there isn't really any semi-efficient way to solve it by hand?
     
  5. Jan 2, 2008 #4

    Vid

    User Avatar

    That's the million dollar question.
     
  6. Jan 2, 2008 #5
    Ah, I see...
     
  7. Jan 6, 2008 #6
    For those who don't want to waste their time, the only other solution for this problem is 5.8+2.15+2*3.55=15.05




    2.15
    2.75
    3.35
    3.55

    4.2
    5.8

    Needs 15.05

    I scrutinized the combinations. It only applies to this problem.

    1st, notice that, because 15.05 has a .05 in the end, we need an odd number of the orders ending in .x5 (the “odds”). So we need 1, 3, or 5 of them (7 is too much for any # but 2.15).

    2nd, we investigate the 4.20 and the 5.80.

    -Obviously, 3*5.8 exceeds the sum, 2*5.8=11.6 leaves us 3.45 to fill, which can’t be done.

    -Then with 5.8, we have 9.25 to fill. Suppose we satisfy this with the “odds” (combination 5.8 and 4.2 will be considered later).
    + We must have an odd combination of the .x5 to make 9.25. Obviously, the 1 and 5 combinations can’t satisfy, so we need 3.
    + As 3*3.35=10.05 > 9.25 and 3*2.75=8.25<9.25, and 2*2.75 +3.55=9.05<9.25
    hence we need two orders from the >3 orders , and 1 from the ones smaller than 3.
    + Try all these combinations (not that many of them), we see that only 2*3.55+2.15=9.25 does the trick!


    -Now, consider 3*4.2=12.6, we need 2.45 not possible again.
    -Then 2*4.2=8.4, we need 6.65, with 1 or 3 or 5 of the odd items. We can quickly drop this possibility.
    -Then 4.2, we need 10.85. Observe that 3*3.55=10.65<10.85 hence no possible 3-combinations and 5*2.15=10.75no possible 5-combinations
    -Now 4.2+5.8=10. We need 5.05 from 1, 3 or 5 of the odds. 3*2.15 is too big, and 1*3.55 is too small. Not possible.

    3rd, we investigate the ones with only the odd prices. We can only have 5 of them.
    5*2.75=13.75<15.05
    5*3.35=16.75>15.05
    We need something of the small side and the big side.

    Suppose we have 3.55 in the combinations. As 5*3.55=17.75 which is 2.70 bigger than 15.05. We want to change some of the 3.55 to other elements to make a -2.70. Because the other elements are -.20, -.80,-1.40 less than 3.55, which can’t form a -2.70 . So no 3.55 in the combination.

    4*3.35=13.4 is also too big for a 5-combination.
    3*3.35=10.05 need 5 for 2 of the 2.15 and 2.75 can’t be done
    2*3.35 + 3*2.75=14.95<15.05 No
    Any other combination is too small
     
    Last edited: Jan 6, 2008
  8. Jan 6, 2008 #7
    Thanks for the solution. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Tough Diophantine Equation
  1. Diophantine Equation (Replies: 2)

  2. A diophantine equation (Replies: 8)

  3. Diophantine equations (Replies: 3)

  4. Diophantine Equation (Replies: 1)

  5. Diophantine equation (Replies: 3)

Loading...