Talk:Coin problem

Mathematics B‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

"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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

[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)[reply]

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)[reply]

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)[reply]

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) —[reply]