This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Should we not rename the article Frobenius problem? Also, what is the opinion on a proposed merge of Chicken McNuggets problem with this article? JocK 18:30, 3 November 2007 (UTC)
I have no opinion on the rename of this article, but let's talk McNuggets - is that not exactly the same as the coin problem? It says "special case" but it's really nothing special. That's like saying "4 is a special case of n2" or something else completely stupid. I'm tempted to say it's advertising form McDonalds. It introduces no new content and speaks nothing to the notability of this "special case" (ie plug and chug) of the coin/Frobenius problem. Additional comment: I would be happy to see an article that discusses this as a "famous problem" or "often used example" but that is far different from it being some problem in mathematics pioneered by the brightest of research mathematicians. Or whatever. -- Cheeser1 02:00, 4 November 2007 (UTC)
I happened upon this article via the McNugget problem hook at the |DYK page and I was pleased to learn something interesting and new from this page. I am about as far from a mathematician as you can get and would normally not bother with something so.....well (please don't take offense!) boring. But there was something approachable and quirky about the McNugget problem and once I grasp the basic premise of it, I was able to look at the rest of the article in a more inquisitive light. To that extent I think its a worthwhile inclusion in the article. As for the rename/merge question, I'll just leave that to the folks who know what they are talking about. :) Agne Cheese/ Wine 14:54, 4 November 2007 (UTC)
What about Postage stamp problem? Probably that page should be merged into this one too. Sean Eberhard ( talk) 06:27, 9 January 2019 (UTC)
You've got to be kidding. The proof sketch might appear under the "n = 2" tab, but it's NOT EVER known as the McNugget Theorem. — Arthur Rubin (talk) 02:34, 14 June 2008 (UTC)
The first formula fails to match the correct value where it's equivalent to n=2 above, and the second formula is not apparently symmetric in m and n. — Arthur Rubin (talk) 14:16, 15 August 2008 (UTC)
For those of you who are impartial in your judgement of article material, I make the case that my edit should stand as follows:
This is an encyclopaedia article - not a mathematical paper - and edits to it should be judged on a different basis to a peer-review of a mathematical paper prior to publication. The change-making section should stand. New Thought ( talk) 11:58, 31 December 2008 (UTC)
I am not a mathematician, but stated in the McNugget is that 6,9 and 20 are relatively prime, which, according to definition given in article relatively prime, they are not: 6 and 9 share 3, 6 and 20 share 2 as a common factor. —Preceding unsigned comment added by 78.54.122.170 ( talk) 10:59, 5 April 2009 (UTC)
The concept of being relatively prime can also be extended any finite set of integers S = {a1, a2, .... an} to mean that the greatest common divisor of the elements of the set is 1. If every pair of integers in the set is relatively prime, then the set is called pairwise relatively prime.
Every pairwise relatively prime set is relatively prime; however, the converse is not true: {6, 10, 15} is relatively prime, but not pairwise relative prime. (In fact, each pair of integers in the set has a non-trivial common factor.)
The section coin problem#Frobenius numbers for small n states that "A closed-form solution exists for the coin problem only where n = 1, 2 or 3." However, the subsection for "n = 3" says only that "Fast algorithms are known for three numbers, though the calculations can be very tedious if done by hand." And then goes on to give approximate bounds. I would not consider "a fast algorithm" to be the same thing as "a closed-form solution". That is why I had excluded n = 3 in the lead paragraph. Whether the "fast algorithm" is a closed-form formula or not, the article is inconsistent and needs to be fixed. All the best, -- Jorge Stolfi ( talk) 18:15, 31 December 2009 (UTC)
The lead now states that "If the number of coin types is between three and ten, no explicit formula is known, but there are algorithms that will compute the Frobenius number in polynomial time." Is that the right way to put it? When I skimmed through the references, I came back with the impression that there is a polynomial algorithm for all fixed n, but that it "probably" had never been implemented beyond n = 10. Also that "fairly fast" algorithms existed for small n, where "fast" of course does not mean "polynomial". And, to my tastes, fast algorithms are at least as interesting as polynomial ones. All the best, -- Jorge Stolfi ( talk) 18:25, 31 December 2009 (UTC)
[unindent] Gandalf61, sorry for undoing your edit, but the abstract of Kannan's paper does not say "magnitude". As far as I can tell, it is exponential in the *logarithm* of the magnitude. (Otherwise I believe that the solution would be trivial and would not need any of the heavy machinery used by Kannan; a " sieve of Eratosthenes" style algorithm should do it.) Until this is clarified, it is better to say just "polynomial time" and let the interested reader look for the paper himself. All the best, -- Jorge Stolfi ( talk) 00:49, 4 January 2010 (UTC)
As you see, the expression for g is symmetrical on m and n, so it has a symmetrical form:
k + 1 k + 1 m ·(n - 1) - n ·(m - 1)
—————————————————————————————————
m - n
aleksisto 109.227.78.115 ( talk) 17:36, 8 October 2010 (UTC) —
At present, this page states the problem as follows:
For n=1, the solution is stated as follows:
Now, obviously this is incorrect. For example, suppose n=1, and a1=4. Then there are obviously an infinite number of integers that cannot be expressed as linear combinations of the set { a1}. Similar errors appear in the solutions for n=2 and n=3 -- each of these assumes that the GCD is 1, and yet this is not stated in the problem itself. Indeed, the text in the Coin problem#Statement section following the problem itself explicitly allows for the possibility that the GCD is not 1.
The simplest fix would be to insert the GCD restriction into the problem itself, as follows:
Alternatively, the error could be fixed by beginning each of the solution sections (n=1, n=2, n=3) with the statement that if the GCD is not one, the inaccessible integers are boundless, but if the GCD is one, then the solution is so-and-so.
Aesthetically, I prefer the first choice. But I don't know if there is actually an "official" statement of the coin problem in mathematical literature; if there is, we of course must follow that. Does anyone know if there is? If not, I will make the change I have suggested here. — Lawrence King ( talk) 00:41, 30 March 2011 (UTC)
Okay, I changed the wording. The old wording was unclear, because the paragraph following the problem appeared to further analyze the problem rather than adding new conditions to it. —
Lawrence King (
talk)
15:16, 30 March 2011 (UTC)
The closed form for n= 3 where 3!<= p< q< (r> 2p and r> 2q) is g(p,q,r)= (p-2)(q-2)(r-2) -2[(p-1)(q-1)-1 +(p-1)(r-1)-1 +(q-1)(r-1)-1] +3[p +q +r +1] -1. It took me about 45 minutes to see it. You might want to add it to the wikipedia page as a possible answer, even though it would be hard to prove it!
For example, the McNugget problem is p= 6, q= 9, r= 20, g(6,9,20)= 4*7*18 -2[(5*8 -1 +(5*19 -1) +(8*19 -1)] +3[6 +9 +20 +1] -1 = 504 -2(284) +3(36) -1 = 43. Nice!
Try it... for 6, 8, 27; you'll get 37, and it's right! Nobody has seen it since about the year 1880. Mighty fine,... huh?? William Bouris I saved it onto a YouTube video. 108.242.169.13 ( talk) 18:48, 20 November 2015 (UTC)
I have a few suggestions.
1, Several citations occur twice, I don't know how to fix it.
2, The paper proving NP-hardness is not cited: Jorge L Ramirez Alfonsin. Complexity of the Frobenius problem. Combinatorica, 16(1):143–147, 1996.
3, I don't understand what the person had in mind who wrote "No known algorithm is polynomial time in the number of coin denominations" - how could an algorithm run without taking into account the denominations' sizes? I think that this only confuses the reader and should be removed.
4, A claimed proof of Sigma2-completeness has appeared recently: https://arxiv.org/abs/1602.05657
Domotorp 12:21, 14 February 2017 (UTC)
I flagged the current section on the case n=3, since there is no citation given and googling the author's name only produces a YouTube video by the editor. However, it appears that there is an actual recent paper on the general formula. The section should be updated to reflect this, preferably by someone with more maths expertise. Petrilaarne ( talk) 16:09, 1 October 2017 (UTC)
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Should we not rename the article Frobenius problem? Also, what is the opinion on a proposed merge of Chicken McNuggets problem with this article? JocK 18:30, 3 November 2007 (UTC)
I have no opinion on the rename of this article, but let's talk McNuggets - is that not exactly the same as the coin problem? It says "special case" but it's really nothing special. That's like saying "4 is a special case of n2" or something else completely stupid. I'm tempted to say it's advertising form McDonalds. It introduces no new content and speaks nothing to the notability of this "special case" (ie plug and chug) of the coin/Frobenius problem. Additional comment: I would be happy to see an article that discusses this as a "famous problem" or "often used example" but that is far different from it being some problem in mathematics pioneered by the brightest of research mathematicians. Or whatever. -- Cheeser1 02:00, 4 November 2007 (UTC)
I happened upon this article via the McNugget problem hook at the |DYK page and I was pleased to learn something interesting and new from this page. I am about as far from a mathematician as you can get and would normally not bother with something so.....well (please don't take offense!) boring. But there was something approachable and quirky about the McNugget problem and once I grasp the basic premise of it, I was able to look at the rest of the article in a more inquisitive light. To that extent I think its a worthwhile inclusion in the article. As for the rename/merge question, I'll just leave that to the folks who know what they are talking about. :) Agne Cheese/ Wine 14:54, 4 November 2007 (UTC)
What about Postage stamp problem? Probably that page should be merged into this one too. Sean Eberhard ( talk) 06:27, 9 January 2019 (UTC)
You've got to be kidding. The proof sketch might appear under the "n = 2" tab, but it's NOT EVER known as the McNugget Theorem. — Arthur Rubin (talk) 02:34, 14 June 2008 (UTC)
The first formula fails to match the correct value where it's equivalent to n=2 above, and the second formula is not apparently symmetric in m and n. — Arthur Rubin (talk) 14:16, 15 August 2008 (UTC)
For those of you who are impartial in your judgement of article material, I make the case that my edit should stand as follows:
This is an encyclopaedia article - not a mathematical paper - and edits to it should be judged on a different basis to a peer-review of a mathematical paper prior to publication. The change-making section should stand. New Thought ( talk) 11:58, 31 December 2008 (UTC)
I am not a mathematician, but stated in the McNugget is that 6,9 and 20 are relatively prime, which, according to definition given in article relatively prime, they are not: 6 and 9 share 3, 6 and 20 share 2 as a common factor. —Preceding unsigned comment added by 78.54.122.170 ( talk) 10:59, 5 April 2009 (UTC)
The concept of being relatively prime can also be extended any finite set of integers S = {a1, a2, .... an} to mean that the greatest common divisor of the elements of the set is 1. If every pair of integers in the set is relatively prime, then the set is called pairwise relatively prime.
Every pairwise relatively prime set is relatively prime; however, the converse is not true: {6, 10, 15} is relatively prime, but not pairwise relative prime. (In fact, each pair of integers in the set has a non-trivial common factor.)
The section coin problem#Frobenius numbers for small n states that "A closed-form solution exists for the coin problem only where n = 1, 2 or 3." However, the subsection for "n = 3" says only that "Fast algorithms are known for three numbers, though the calculations can be very tedious if done by hand." And then goes on to give approximate bounds. I would not consider "a fast algorithm" to be the same thing as "a closed-form solution". That is why I had excluded n = 3 in the lead paragraph. Whether the "fast algorithm" is a closed-form formula or not, the article is inconsistent and needs to be fixed. All the best, -- Jorge Stolfi ( talk) 18:15, 31 December 2009 (UTC)
The lead now states that "If the number of coin types is between three and ten, no explicit formula is known, but there are algorithms that will compute the Frobenius number in polynomial time." Is that the right way to put it? When I skimmed through the references, I came back with the impression that there is a polynomial algorithm for all fixed n, but that it "probably" had never been implemented beyond n = 10. Also that "fairly fast" algorithms existed for small n, where "fast" of course does not mean "polynomial". And, to my tastes, fast algorithms are at least as interesting as polynomial ones. All the best, -- Jorge Stolfi ( talk) 18:25, 31 December 2009 (UTC)
[unindent] Gandalf61, sorry for undoing your edit, but the abstract of Kannan's paper does not say "magnitude". As far as I can tell, it is exponential in the *logarithm* of the magnitude. (Otherwise I believe that the solution would be trivial and would not need any of the heavy machinery used by Kannan; a " sieve of Eratosthenes" style algorithm should do it.) Until this is clarified, it is better to say just "polynomial time" and let the interested reader look for the paper himself. All the best, -- Jorge Stolfi ( talk) 00:49, 4 January 2010 (UTC)
As you see, the expression for g is symmetrical on m and n, so it has a symmetrical form:
k + 1 k + 1 m ·(n - 1) - n ·(m - 1)
—————————————————————————————————
m - n
aleksisto 109.227.78.115 ( talk) 17:36, 8 October 2010 (UTC) —
At present, this page states the problem as follows:
For n=1, the solution is stated as follows:
Now, obviously this is incorrect. For example, suppose n=1, and a1=4. Then there are obviously an infinite number of integers that cannot be expressed as linear combinations of the set { a1}. Similar errors appear in the solutions for n=2 and n=3 -- each of these assumes that the GCD is 1, and yet this is not stated in the problem itself. Indeed, the text in the Coin problem#Statement section following the problem itself explicitly allows for the possibility that the GCD is not 1.
The simplest fix would be to insert the GCD restriction into the problem itself, as follows:
Alternatively, the error could be fixed by beginning each of the solution sections (n=1, n=2, n=3) with the statement that if the GCD is not one, the inaccessible integers are boundless, but if the GCD is one, then the solution is so-and-so.
Aesthetically, I prefer the first choice. But I don't know if there is actually an "official" statement of the coin problem in mathematical literature; if there is, we of course must follow that. Does anyone know if there is? If not, I will make the change I have suggested here. — Lawrence King ( talk) 00:41, 30 March 2011 (UTC)
Okay, I changed the wording. The old wording was unclear, because the paragraph following the problem appeared to further analyze the problem rather than adding new conditions to it. —
Lawrence King (
talk)
15:16, 30 March 2011 (UTC)
The closed form for n= 3 where 3!<= p< q< (r> 2p and r> 2q) is g(p,q,r)= (p-2)(q-2)(r-2) -2[(p-1)(q-1)-1 +(p-1)(r-1)-1 +(q-1)(r-1)-1] +3[p +q +r +1] -1. It took me about 45 minutes to see it. You might want to add it to the wikipedia page as a possible answer, even though it would be hard to prove it!
For example, the McNugget problem is p= 6, q= 9, r= 20, g(6,9,20)= 4*7*18 -2[(5*8 -1 +(5*19 -1) +(8*19 -1)] +3[6 +9 +20 +1] -1 = 504 -2(284) +3(36) -1 = 43. Nice!
Try it... for 6, 8, 27; you'll get 37, and it's right! Nobody has seen it since about the year 1880. Mighty fine,... huh?? William Bouris I saved it onto a YouTube video. 108.242.169.13 ( talk) 18:48, 20 November 2015 (UTC)
I have a few suggestions.
1, Several citations occur twice, I don't know how to fix it.
2, The paper proving NP-hardness is not cited: Jorge L Ramirez Alfonsin. Complexity of the Frobenius problem. Combinatorica, 16(1):143–147, 1996.
3, I don't understand what the person had in mind who wrote "No known algorithm is polynomial time in the number of coin denominations" - how could an algorithm run without taking into account the denominations' sizes? I think that this only confuses the reader and should be removed.
4, A claimed proof of Sigma2-completeness has appeared recently: https://arxiv.org/abs/1602.05657
Domotorp 12:21, 14 February 2017 (UTC)
I flagged the current section on the case n=3, since there is no citation given and googling the author's name only produces a YouTube video by the editor. However, it appears that there is an actual recent paper on the general formula. The section should be updated to reflect this, preferably by someone with more maths expertise. Petrilaarne ( talk) 16:09, 1 October 2017 (UTC)