Talk:Coin problem

Rename/merge?

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)

The misnamed Chicken McNuggets problem is a subarticle fork from this article. The question of whether there is enough to split off was previously decided in the negative in AfD. Any content should be added here first before a split is considered. — Arthur Rubin | (talk) 18:51, 3 November 2007 (UTC)

The current article is not helpful at all for a casual reader. Would any non-mathematician be able to understand the general concept of the Frobenius problem when reading about quatloo's? For didactical purposes it is much better to discuss the well-known special case g(6,9,20) in a separate article (Chicken McNuggets problem) that contains links to Coin problem (potentially renamed Frobenius problem). JocK 19:14, 3 November 2007 (UTC)

The section #McNugget Number seems to contain all that is needed for a casual reader. I have no objection to the McNugget number redirects to be re-redirected to redirect to that section. But I'm a mathematician, so what is obvious to me may not be obvious to the casual reader. WP:3O, anyone? — Arthur Rubin | (talk) 19:24, 3 November 2007 (UTC)

Whether the more specific, didactical article should be named Chicken McNuggets problem or McNugget number is largely irrelevant for this discussion. However see: here, here, here and here. JocK 19: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 n²" 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)

You do have a sense of humour "..it's advertising form McDonalds", but miss my point entirely. Of course this specific case of the Frobenius problem is not "a problem in mathematics pioneered by the brightest of research mathematicians". Indeed, it is just a specific case (g(6,9,20)=43) of a more general theory. Just like the article Theorem on friends and strangers is a special case (G(3,3)=6) of the more general Ramsey's theorem. The article Theorem on friends and strangers is not "a problem in mathematics pioneered by the brightest of research mathematicians", but I would not like to see it merged&redirected into the article Ramsey's theorem that is much less suitable for a casual reader with little or no background in mathematics. I'm trying to do the same here with the Frobenius problem. Surely there is room for a rigorous mathematical article (although I have to say that the current article coin problem hardly qualifies as such) as well as an article of didactical nature that presents the concept by focusing on a specific example.

I guess it all boils down to what are we trying to establish here on Wikipedia. I am trying to create some math articles accessible to a larger audience of interested laypersons.

Hope that some non-mathematicians place their opinions here as well! Cheers, JocK 07:52, 4 November 2007 (UTC)

I'm just not aware of this as some outstanding or notable "problem" and would also like to see the article reflect what it really is - not representing it as some important mathematical problem. --Cheeser1 10:13, 4 November 2007 (UTC)

Outside layperson's 2 McNugget's worth

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)

I totally agree, and I am (or will probably be) a mathematican. Paxinum 16:43, 7 November 2007 (UTC)

But that could be said for this page - in fact, coins are a far more appropriate context than McNuggets, in terms of worldview. --Cheeser1 16:48, 7 November 2007 (UTC)

Postage stamp problem

What about Postage stamp problem? Probably that page should be merged into this one too. Sean Eberhard (talk) 06:27, 9 January 2019 (UTC)

"McNugget Theorem"?

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)

I've removed the McSubsection. Michael Slone (talk) 23:33, 9 March 2009 (UTC)

And I have restored that section. McNugget numbers feature in both MathWorld and in OEIS, which are cited in the section. Certainly this example is better known and better sourced than the two sports examples which follow it. I believe what Arthur Rubin was objecting to above was the use of the term "McNugget Theorem", which no longer appears in the article. If anyone still thinks this section should be removed, let's discuss and find consensus.Gandalf61 (talk) 07:23, 10 March 2009 (UTC)

Frobenius numbers for special sets

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)

Good call- I copied the wrong formula for the first one. It works out now. As for the geometric sequence formula, believe it or not, it IS symmetric. The source is in an online (peer-reviewed) journal, so you can check it yourself. Borisblue (talk) 18:55, 15 August 2008 (UTC)

Change making problem

For those of you who are impartial in your judgement of article material, I make the case that my edit should stand as follows:

• the change-making problem is widely cited

• what I have written about it is concise

• each part of what I have written is supported by links to other articles

• it contains useful information which will enable many people to resolve a wide range of change-making problems more quickly than they otherwise would

• if there is any part of what I have written that you don't like, then editing it would be a more appropriate action than summarily deleting it

• regarding Arthur's rationalisation of "notability", please compare the notability of the change-making section with the notability of other parts of the article

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)

The change-making problem is not normally considered related to the coin problem, although there is some relationship. If an article on the change-making problem could be created, it might be OK, but solution methods to the change-making problem should not be in this article, but only in a separate article. (Integer) linear programming and dynamic programing are not relevant here, unless you wish to assert (and can demonstrate) they're used for the coin problem. — Arthur Rubin (talk) 16:49, 31 December 2008 (UTC)

I agree, I think the change-making problem is both substantial enough to merit its own article, and not closely related enough to the coin problem to be a subsection here. Borisblue (talk) 03:48, 1 January 2009 (UTC)

Mistake?

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)

From coprime:

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.)

So {6, 9, 20} are indeed relatively prime, because their createst common divisor is 1. However they are not pairwise relatively prime. Gandalf61 (talk) 12:22, 5 April 2009 (UTC)

Is there a closed formula for the case n = 3?

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)

Isn't there a polynomial algorithm for all fixed n?

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)

MathWorld article says "Fast algorithms are also known for three numbers, but the more general problem for an arbitrary number of numbers is known to be NP-hard if n is fixed (Kannan 1992) or n is variable (Ramírez-Alfonsín 1996)". If a polynomial-time algorithm were known for any fixed n then the general problem would not be NP-hard. Gandalf61 (talk) 08:17, 1 January 2010 (UTC)

Er, I am rusty on complexity theory, but why not? For example, the obvious brute-force algorithm for finding an n-clique in a graph is polynominal for any fixed n, but eponential if n is part of the data. As for the mathworld quote, what does it mean "for an arbitrary number of numbers ... if n is fixed"? All the best, --Jorge Stolfi (talk) 22:30, 1 January 2010 (UTC)

If there is a polynomial-time algorithm for any NP-hard problem, then there are polynomial-time algorithms for all problems in NP, and hence P = NP - see NP-hard. It is not known whether P=NP, therefore a polynomial-time algorithm is not known for any NP-hard problem, and in particular a polynomial-time algorithm is not known for the coin problem for an arbitrary value of n. Gandalf61 (talk) 23:17, 1 January 2010 (UTC)

Well, it seems that there is a misunderstanding here. That much I still remember. But, as, I said, a problem *can* be polynomial for any fixed value of a parameter, but NP-had if the parameter is part of the data. All the best, --Jorge Stolfi (talk) 02:31, 2 January 2010 (UTC)

You can look up some details on associated algorithmic problems and conjectures at Google Books. Maxal (talk) 23:35, 1 January 2010 (UTC)

• I could not get Kannan's paper, but Beihofer et al. say "Kannan [Kan89] used similar methods to establish, for every �fixed n, the existence of a polynomial-time algorithm to compute the exact Frobenius number. However, Kannan's algorithm has apparently never been implemented. Moreover, the Kannan algorithm does not solve instances of equation (1)." If this is correct, the Mathworld article is simply wrong (even if one ignores the self-contradiction) and the coin proble is in P for any fixed n.
  The last sentence of the quote merely says that Kannan's algorithm can compute the largest un-representable number, but does not tell how to obtain a representable one with the given coins.
  By the way, the Mathworld article also says that the n=2 case is "folklore" whereas Beihofer et al. attribue it to Sylvester.
  All the best, --Jorge Stolfi (talk) 22:02, 2 January 2010 (UTC)

Yes, there does seem to be an inconsistency between MathWorld and the Beihofer paper. I think we can only resolve this by getting access to the Kannan paper to see what it actually says. Gandalf61 (talk) 10:02, 3 January 2010 (UTC)

Kannan's paber is not available, but its abstract is, and it clearly states the claim. Since it has been reviewed, I can't see what other confirmation we may ask for. All the best, --Jorge Stolfi (talk) 13:50, 3 January 2010 (UTC)

The abstract also agrees that the problem is NP-hard. On the face of it, Kannan is claiming to have shown the existence of a polynomial-time algorithm for an NP-hard problem. So why doesn't that lead to the conclusion that P=NP ? Gandalf61 (talk) 15:18, 3 January 2010 (UTC)

There is no inconsistency, see above. There are quite a few problems that have polynomial algorithms for each fixed value of some parameter, but are NP-hard if the parameter is free. For example, consider deciding whether a graph has a clique of size k. The obvious algorithm -- list all subsets of k vertices and check whether each is a clique -- has complexity Θ(v^k+2), where v is the number of vertices; which is polynomial for any fixed k but exponential if k is part of the data. All the best, --Jorge Stolfi (talk) 16:41, 3 January 2010 (UTC)

So you seem to be suggesting, by analogy, that Kannan's algorithm is not polynomial-time in n, the number of coin types, but is instead polynomial time in some other parameter, when n is fixed. What is this other parameter ? Gandalf61 (talk) 17:18, 3 January 2010 (UTC)

The set of coin denominations $a_{1},a_{2},\dots ,a_{n}$ — they form an input for any algorithm that computes Frobenius number $g(a_{1},a_{2},\dots ,a_{n})$. Maxal (talk) 20:15, 3 January 2010 (UTC)

Right. "Polynomial time" (and "NP", etc.) almost alway always means "polynomial in the length of the input data", not "polynominal in the parameter called n". In this case, the length would be a little bit more than the sum of log₂(a_k), plus log₂(n). All the best, --Jorge Stolfi (talk) 20:33, 3 January 2010 (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)

I disagree. If you prefer log to magnitude, then let's say log, but just saying "polynomial time" without further qualification is potentially misleading. Cheers mate, Gandalf61 (talk) 09:32, 4 January 2010 (UTC)

It is not a matter of what I prefer, but what we know for sure. Anyway, since the article now coincide with my guess, I will not dispute it. All the best, --Jorge Stolfi (talk) 12:44, 4 January 2010 (UTC)

Symmetrical form for geometric sequences

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) —

Were you trying to say:

• ${\frac {m^{k+1}\cdot \left(n-1\right)-n^{k+1}\cdot \left(m-1\right)}{m-n}}$

? — Arthur Rubin (talk) 17:59, 8 October 2010 (UTC)

Error in either the statement or the solution for n=1

At present, this page states the problem as follows:

In mathematical terms the problem can be stated:

Given positive integers a₁, a₂, ..., a_n, find the largest integer that can not be expressed as a non-negative integer linear combination of these numbers, i.e., as a sum

k₁a₁ + k₂a₂ + ··· + k_na_n,

where k₁, k₂, ..., k_n are non-negative integers.

For n=1, the solution is stated as follows:

If n = 1, then a₁ = 1 so that all natural numbers can be formed. Hence no Frobenius number in one variable exists.

Now, obviously this is incorrect. For example, suppose n=1, and a₁=4. Then there are obviously an infinite number of integers that cannot be expressed as linear combinations of the set { a₁}. 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:

Given positive integers a₁, a₂, ..., a_n   such that the greatest common divisor of the set { a₁, a₂, ..., a_n } is 1, find the largest integer that can not be expressed as a non-negative integer linear combination of these numbers, i.e., as a sum

k₁a₁ + k₂a₂ + ··· + k_na_n,

where k₁, k₂, ..., k_n are non-negative integers.

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)

The restriction to a GCD of 1 is actually mentioned in the paragraph following the part you quoted, which says:

"Frobenius number is defined if the greatest common divisor of the elements is 1. If the GCD is not 1, any integer that is not a multiple of the GCD will be unobtainable with the given coins, and therefore there is no largest such integer."

This could be better worded - for example, "The Frobenius number is only defined if the greatest common divisor of the elements is 1.". I also see no difficulty with moving the CGD restriction to an earlier place in the problem statement so that it is more obvious. Gandalf61 (talk) 14:16, 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 long-awaited closed formula for n= 3

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)

1. Wikipedia is not an appropriate place to publish original research.

2. Your formula is certainly not right. This is easy to see by taking for example the set {7, 8, 17}, with Frobenius number 27; your formula gives 54.

--JBL (talk) 20:35, 20 November 2015 (UTC)

Update needed for computational complexity part

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)

Updating case n=3

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)

Someone has added citations since 2017. Maybe the update template can be removed? IvicaInsomniac (talk) 17:37, 15 December 2023 (UTC)