verma@ucla-cs.UUCP (02/18/86)
[eat this ...]
The origional problem was simple, so lets make two new ones:
Find a bag/set of natural numbers which sum to N and have a
maximal product.
TS Vermamatt@oddjob.UUCP (Matt Crawford) (02/21/86)
> Find a bag/set of natural numbers which sum to N and have a > maximal product. > TS Verma Well, the "bag" problem is easy, the "set" part will have to wait until tomorrow. ... Suppose a bag of natural numbers is given which has sum N >= 1. (If you need an existence proof, start with the bag { N }.) Perform the following replacements, all of which increase the product while preserving the sum: 1) for any x, replace the members { 1, x } with { x+1 } 2) for any x >= 4, replace { x } with { 2, x-2 } (actually, this leaves the product the same if x = 4) 3) replace { 2, 2, 2 } with { 3, 3 } When no more of these substitutions can be made, you have found a bag which maximizes the product. (Purists will easily convince themselves that the process does terminate!) By construction, it can only be: one "1" if N = 1 N/3 "3"s if N > 1 and N=0 (mod 3) two "2"s and (N-4)/3 "3"s if N > 1 and N=1 (mod 3) one "2" and (N-2)/3 "3"s if N > 1 and N=2 (mod 3) (In the third case, the maximizing bag is not unique -- you could substitute a "4" for two "2"s.) _____________________________________________________ Matt University crawford@anl-mcs.arpa Crawford of Chicago ihnp4!oddjob!matt
matt@oddjob.UUCP (Matt Crawford) (02/28/86)
In article <9081@ucla-cs.ARPA> verma@ucla-cs.UUCP (Thomas S. Verma ) writes: > > Find a bag/set of natural numbers which sum to N and have a > maximal product. > TS Verma I already posted the answer to the "bag" half. I have an algorithm which solves the "set" half, but so far no explicit representation of the solution. Come on, let's not always see the same hands! _____________________________________________________ Matt University crawford@anl-mcs.arpa Crawford of Chicago ihnp4!oddjob!matt