How to Solve the Tough Diophantine Equation?

  • Thread starter Izzhov
  • Start date
In summary, the conversation discusses the solution to a knapsack problem found in XKCD. The solution is 5.8+2.15+2*3.55=15.05 and it was discovered through trial and error. The conversation also explores the different combinations and patterns involved in solving the problem.
  • #1
Izzhov
121
0
I was reading XKCD and I found this:
np_complete.png

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?
 
Physics news on Phys.org
  • #2
It's a knapsack problem, programming the most efficient way to solve it is a nice challenge :smile:
 
  • #3
So... there isn't really any semi-efficient way to solve it by hand?
 
  • #4
That's the million dollar question.
 
  • #5
Ah, I see...
 
  • #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:
  • #7
Thanks for the solution. :)
 

FAQ: How to Solve the Tough Diophantine Equation?

What is a Tough Diophantine Equation?

A Diophantine equation is a polynomial equation in two or more unknowns that involve only integer solutions. A tough Diophantine equation is one that is particularly difficult to solve, often requiring advanced mathematical techniques.

How do you solve a Tough Diophantine Equation?

Solving a tough Diophantine equation often involves using advanced mathematical techniques such as algebraic number theory, modular arithmetic, or quadratic forms. It may also require trial and error methods and a lot of patience.

What are some examples of Tough Diophantine Equations?

Some well-known examples of tough Diophantine equations include Fermat's Last Theorem, the Catalan Conjecture, and the Tijdeman-Zagier Conjecture. These equations have been studied by mathematicians for centuries and have only recently been solved using advanced techniques and computer algorithms.

What is the significance of solving a Tough Diophantine Equation?

Solving a tough Diophantine equation is significant because it often leads to new mathematical discoveries and insights. It also has practical applications in fields such as cryptography and coding theory.

Are there any known methods for solving all Tough Diophantine Equations?

As of now, there is no known method for solving all tough Diophantine equations. Each equation requires its own unique approach and there are still many unsolved equations. However, advancements in mathematics and technology continue to make solving tough Diophantine equations more accessible.

Similar threads

Replies
1
Views
971
Replies
11
Views
638
Replies
1
Views
1K
Replies
1
Views
634
Replies
6
Views
1K
Replies
4
Views
4K
Replies
5
Views
2K
Back
Top