Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site oddjob.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!ihnp4!oddjob!matt
From: matt@oddjob.UUCP (Matt Crawford)
Newsgroups: net.puzzle
Subject: Re: Find a set of ... [New and Improved] (1/2 SPOILER)
Message-ID: <1188@oddjob.UUCP>
Date: Thu, 20-Feb-86 20:19:59 EST
Article-I.D.: oddjob.1188
Posted: Thu Feb 20 20:19:59 1986
Date-Received: Fri, 21-Feb-86 07:49:35 EST
References: <1057@decwrl.DEC.COM> <9081@ucla-cs.ARPA>
Reply-To: matt@oddjob.UUCP (Matt Crawford)
Organization: U. Chicago, Astronomy & Astrophysics
Lines: 34

>       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