Joined: 3/8/2004
Posts: 185
Location: Denmark
http://en.wikipedia.org/wiki/Knapsack_problem
The knapsack problem is often solved using dynamic programming, though no polynomial-time algorithm is known for the general problem.
E.g. no general formulae has yet been found
"We observe the behaviour of simple folk, and derive pleasure from their defects." -Aristotle - Book of Humour
Player (86)
Joined: 3/8/2005
Posts: 973
Location: Newfoundland, Canada
Prove that 1/3 = 0.33333333333333 ok well.. set up a a good pattern. 3 X { 1/10 + 1/100 + 1/1000 + 1/10000 + 1/100000 + .... + 1/10^n } Since the decimal will keep going, n = Infinity. .3333333 = (cant remember rest.. someone help out) I think it has something to do with the eqation Sn = (T1(1-R^n)) / (1 - R)
Emulator Coder, Skilled player (1310)
Joined: 12/21/2004
Posts: 2687
MahaTmA wrote:
The knapsack problem is often solved using dynamic programming, though no polynomial-time algorithm is known for the general problem.
E.g. no general formulae has yet been found
So? Not that a brute-force solution would be mathematically interesting, but Walker Boh didn't say anything about solving it in polynomial time.
Joined: 12/1/2004
Posts: 13
Solve the knapsack problem in polynomial time and win a cool million dollars (US) http://www.claymath.org/millennium/P_vs_NP/
Skilled player (1827)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
MahaTmA wrote:
Prove, that X^n + Y^n = Z^n has no solutions for n>2
You probably knew this, but this problem has actually been solved by an English mathematician named Andrew Wiles. If I were to post the answer here, it would probably take up like 50 pages or so, since he wrote a whole book just anwering that mathematical problem :) Here is another classic math problem which I think no one has solved yet. Statement: All positive integers can be written as the sum of two primenumbers. Example, 20 = 13+7, and since 13 and 7 are primenumbers, this works for 20. Your task is to prove this right or wrong. You may use the same primenumber twice, (like 22=11+11) and you may also use both 1 and zero as primenumbers. Here's from 0 to 10 made like that: 0 = 0+0 1 = 1+0 2 = 1+1 3 = 1+2 4 = 1+3 5 = 2+3 6 = 1+5 7 = 2+5 8 = 1+7 9 = 2+7 10 = 3+7 It would be cool to see how high we can go with this :)
JXQ
Experienced player (761)
Joined: 5/6/2005
Posts: 3132
Just the even numbers > 2 of this problem represent Goldbach's Conjecture, which is still unsolved, except this problem also allows 0 or 1 in the sums, while GC does not.
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
Joined: 4/16/2005
Posts: 251
Randil wrote:
MahaTmA wrote:
Prove, that X^n + Y^n = Z^n has no solutions for n>2
You probably knew this, but this problem has actually been solved by an English mathematician named Andrew Wiles. If I were to post the answer here, it would probably take up like 50 pages or so, since he wrote a whole book just anwering that mathematical problem :)
I was just about to post: "50 pages? You have to be a freaking genius, it took Wiles about 200 to make his point, and even then he lost most of his readers on page 3". But whatever, you should read Uncle Petros and the Goldbach's Conjecture and Fermat's Last Theorem (I hope the latter one is the right one, I read the german translation of it, and there are several english versions by almost the same name). Both are written as novels focussing on the humans searching for mathematical answers, and the math stuff is only mentioned on a side note, blurred enough to get a rough point without being prof in number theory, but also detailed enough so that someone with some background can get an idea of what goes on. May even be something for the "you do that for fun? Weirdos!"-fraction :).
Joined: 3/8/2004
Posts: 185
Location: Denmark
Randil wrote:
It would be cool to see how high we can go with this :)
11= 11 + 0 12 = 11+1 13=11+2 14=13+1 15=13+2 16=11+5 17=17+0 18=17+1 19=17+2 20=13+7=17+3 21=19+2 22=19+3 23=23+0 24=23+1 25=23+2 This is, of course, only accepting that 0 is a prime. this is even though D(0)=NU{0} and not just {0,1} which it should be
"We observe the behaviour of simple folk, and derive pleasure from their defects." -Aristotle - Book of Humour
Skilled player (1827)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Gorash: Thanks for the link, I'll read that later today, I don't have the time right now. And actually, I had no idea how thick Wiles book was, so I just guessed :) EDIT: oh, didn't know that was a link to where to buy the book, I thought it was a link to a site about the problems. Oh, well, I'll think about buying them, I'm a little short on funds right now. Thanks anyway, Gorash :) Anyway, here's another number. 26 = 3+23 Crap, there was no answer to 27. You can try it yourselves if you doubt my über math skills :) Perhaps you are allowed to subtract prime numbers too? In that case 27 = 29-2.
Former player
Joined: 5/22/2004
Posts: 462
Are negative numbers considered prime? If so, then I'd assume subtracting would be okay, since it's just adding negative numbers.
Joined: 5/3/2004
Posts: 1203
MahaTmA wrote:
Post the answer to that in binary code, and I'll set you up for a Nobel prize.
No Nobel prize in math.
Gorash wrote:
I was just about to post: "50 pages? You have to be a freaking genius, it took Wiles about 200 to make his point, and even then he lost most of his readers on page 3"
But he was long winded and his methods unnecessarily obfuscated. As usually happens his ideas have since been generalized and his proof shortened considerably.
Player (206)
Joined: 5/29/2004
Posts: 5712
well, I think there's some kind of prize, 'cause I remember they mentioned it in Good Will Hunting
put yourself in my rocketpack if that poochie is one outrageous dude
Former player
Joined: 3/8/2004
Posts: 706
I believe you mean the Field's Medal?
Skilled player (1827)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Yes, the Field's medal is like the Nobel prize in math. But I think the prizemoney is lower with the Field's medal. Aren't the Norweigan government handing out money once a year to a mathematician who they want to continue his work? I know I've heard of it before, but I don't know if it's true.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Solving math problems is one of my main interests. I sometimes take the Putnam Math Competition, an undergraduate contest in North America for solving math problems. I got 31 last year, which is considered very good (top 300 out of 4000). The problems are very difficult to solve. As for Fermat's Last Theorem, I think Wiles submitted a 200-page proof which was fundamentally flawed. He then fixed the proof and shortened it in the process. Do people still think 0 and 1 are prime numbers? :(
Dan_ wrote:
Are negative numbers considered prime? If so, then I'd assume subtracting would be okay, since it's just adding negative numbers.
As far as I know, the primes are considered only in the set of natural numbers (greater than 0), so the answer is no.
Player (206)
Joined: 5/29/2004
Posts: 5712
I was in MathCounts a few times...
put yourself in my rocketpack if that poochie is one outrageous dude
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Bag of Magic Food wrote:
I was in MathCounts a few times...
If you're talking about the MathCounts contest (Grade 8/9) in British Columbia, Canada, then I took it once. I would have taken it twice if not for illness.
Skilled player (1827)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
82-35-43 wrote:
Do people still think 0 and 1 are prime numbers? :(
Well, not really, but without counting them as primenumbers the mathproblem I posted quicly becomes unsolvable. And I agree with you that primenumbers must be >0. Although I think that you are allowed to subtract primenumbers in my mathproblem, or else it it will quickly be unsolvable. In any case, it makes the problem a little more challenging :)
Editor, Player (69)
Joined: 6/22/2005
Posts: 1050
One is not a prime number. If it were, there would be an infinite way to write the prime factorization of each number. Prime numbers can only be >1 in the real set, iirc.
Current Projects: TAS: Wizards & Warriors III.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Randil wrote:
82-35-43 wrote:
Do people still think 0 and 1 are prime numbers? :(
Well, not really, but without counting them as primenumbers the mathproblem I posted quicly becomes unsolvable. And I agree with you that primenumbers must be >0. Although I think that you are allowed to subtract primenumbers in my mathproblem, or else it it will quickly be unsolvable. In any case, it makes the problem a little more challenging :)
Generally, 0 and 1 are not considered prime numbers. It makes important theorems easier to state. I think the problem you stated was whether every positive number was the sum of two numbers from the set {0,1,prime}. I figured out that if n is odd, then n can be represented if and only if n is prime or n-2 is prime, since the set {0,1,prime} only has two even numbers, 0 and 2. If n is even, then this is equivalent to Goldbach's conjecture. That's why 27 doesn't work. 27 is not prime; 25 is not prime. If you throw in the difference, i.e. whether every positive number is the sum or difference of two numbers in the set {0,1,prime}, you get: If n is odd, then n can be represented if and only if any of n, n-2, n+2 is prime. So it breaks down at 93.
Skilled player (1827)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Hmm, very interesting... I thought that this went much higher for the odd integers. Well, what do you know. I really do agree with you guys that neither 0 or 1 is prime, buy you have to bend the rules a little to make this problem possible. :) A better way of putting the rules would be "You may use all primenumbers as well as the numbers 0 and 1." So, wanna see out how far we can go with the even integers? Although 82-35-43 proved that it breaks down at 93 for odd integers, I don't know how far we can go with the even ones. It would be interesting to find out.
Editor, Reviewer, Experienced player (979)
Joined: 4/17/2004
Posts: 3109
Location: Sweden
>So, wanna see out how far we can go with the even integers? Although 82-35-43 proved that it breaks down at 93 for odd integers, I don't know how far we can go with the even ones. It would be interesting to find out. Even integers have been tested by computer up to 2*10^17. And there is mathematical proof that every odd integer larger than e^e^11.503 (about 3.3^3*10^43000) can be written by three primes. But the numbers between those two are up for grabs. :) Get working.
Joined: 3/8/2004
Posts: 185
Location: Denmark
*bump* I'm still awaiting a response to the problem I posted on the first page, as Randil has given up :)
"We observe the behaviour of simple folk, and derive pleasure from their defects." -Aristotle - Book of Humour
Joined: 4/16/2005
Posts: 251
f'(c) > 0 (2) Define the function g as: g(x)=(f(x)-f(c))^(1/3) , a=<x=<b Ergo: g(c) = 0 (3)
Nope, not ergo. Non sequitur. f'(c) != f(c) in most cases. The problem itself is not hard. The hardest part is to read and follow that weird thoughts, paired with the serialized description... Next one please. :)
Joined: 3/8/2004
Posts: 185
Location: Denmark
Not sure you are reading it correctly: g(x)=(f(x)-f(c))^(1/3) , a=<x=<b g(c)=(f(c)-f(c))^(1/3)=(0)^(1/3)=0 Nowhere has it been stated that f(c)=f'(c)
"We observe the behaviour of simple folk, and derive pleasure from their defects." -Aristotle - Book of Humour