May 2005 - mathfun@mailman.xmission.com

Re: [math-fun] Greedy Change
by Jeffrey Shallit 04 May '05

04 May '05

Yes, there is an algorithm. See http://citeseer.ist.psu.edu/pearson94polynomialtime.html Jeffrey Shallit > > I understand that with US coins of denominations (100, 50, 25, 10, 5, > > 1) cents, making change by the greedy algorithm (at each step select > > the largest possible coin) leads to optimal change (fewest coins) for > > all amounts. > > > > There are other conceivable sets of denominations, e.,g, (10, 6, 1), > > where the greedy algorithm fails (for example, the greedy algorithm > > gives 18 = 10+6+1+1 whereas 18 = 6+6+6 uses fewer coins). > > > > Is there an algorithm for determining if a given set of coins gives > > optimal change via the greedy algorithm? > > > > - David W. Wilson

1 0

[math-fun] Greedy Change
by David Wilson 04 May '05

04 May '05

I understand that with US coins of denominations (100, 50, 25, 10, 5, 1) cents, making change by the greedy algorithm (at each step select the largest possible coin) leads to optimal change (fewest coins) for all amounts. There are other conceivable sets of denominations, e.,g, (10, 6, 1), where the greedy algorithm fails (for example, the greedy algorithm gives 18 = 10+6+1+1 whereas 18 = 6+6+6 uses fewer coins). Is there an algorithm for determining if a given set of coins gives optimal change via the greedy algorithm? - David W. Wilson "Truth is just truth -- You can't have opinions about the truth." - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"

4 4

RE: [math-fun] elliptic mean
by Daniel Asimov 02 May '05

02 May '05

<< Must a Mean associate? -- Rich Well, from ((x+y)/2 + z)/2 = x/4 + y/4/ + z/2 we see that even the arithmetic mean fails to associate. On the other hand, I have in the past worked with mean associates (though that was not obligatory). --Dan

6 7

RE: [math-fun] ~s solid angle <- trihedral angles
by Daniel Asimov 02 May '05

02 May '05

Hi, Bill. I'm always interested in your many identities (no, not aliases), but with my e-mail set to my favorite font (Garamond), they come across mangled somewhat. In trying what used to always work -- just copying your text to a primitive editor (Notepad) to an equal-width font, the text no longer reconstructs itself. Even after pushing some obvious things into place, I'm still not sure what you wrote. E.g., your trihedral post today came out after massaging as follows in Courier New: (cos(c) + cos(b) + cos(a) + 1) 2 acos(-------------------------------------- - 1). (cos(a) + 1) (cos(b) + 1) (cos(c) + 1) Duh, cos(c) + cos(b) + cos(a) + 1 2 acos(----------------------------). a b c 4 cos(-) cos(-) cos(-) 2 2 2 Any suggestions? Regards, Dan

2 1

[math-fun] ~s solid angle <- trihedral angles
by R. William Gosper 02 May '05

02 May '05

A couple of years ago I here gave 2 (cos(c) + cos(b) + cos(a) + 1) acos(-------------------------------------- - 1). (cos(a) + 1) (cos(b) + 1) (cos(c) + 1) Duh, cos(c) + cos(b) + cos(a) + 1 2 acos(----------------------------). a b c 4 cos(-) cos(-) cos(-) 2 2 2 Imaginary result means you violated the triangle inequality. Tsk. --rwg PS, for those interested in trig exercises, this started out as cos(a) - cos(b) cos(c) cos(b) - cos(a) cos(c) acos(----------------------) + acos(----------------------) sin(b) sin(c) sin(a) sin(c) cos(c) - cos(a) cos(b) + acos(----------------------) - %pi sin(a) sin(b) For those with an unhealthy interest in trig exercises, www.ippi.com/rwg/trigbelt.dvi

1 0

[math-fun] Laws of Average (2)
by Richard Schroeppel 02 May '05

02 May '05

Small systems that satisfy the Average axioms. AA = A AB = BA AB.CD = AC.BD elements systems tables group orders 1 1 1 1 2 1 2 1 3 3 10 1 2 6 4 7 92 1.2 2.3 6.2 5 22 1321 1.5 2.10 4 6.4 20 24 6 77 27882 1.19 2.31 4.7 6.12 12.4 20 24.2 120 7 314 819330 1.85 2.122 4.32 6.36 8.4 12.19 20.2 24.6 36.2 42 48 72 120.2 720 Elements is the size of the system. Systems is the count of non-isomorphic systems of that size. Tables is the total number of tables, with no culling for isomorphism. Group orders is the number of systems with each size of automorphism group. For example, there are 314 non-isomorphic Average systems with 7 elements. 85 of those systems have the trivial automorphism group (only the identity), and each system gives rise to 7! = 5040 distinct tables. There's one system with an automorphism group of 720 elements, which gives rise to only 5040/720 = 7 different tables. The total number of possible 7-element tables is 7^49, of which roughly 7^7 satisfy the Average rules. We have the obvious identities 314 = 85 + 122 + 32 + ... + 1 + 2 + 1, and 819330 = 5040 * (85/1 + 122/2 + 32/4 + ... + 1/72 + 2/120 + 1/720). "Minimum" satisfies the rules, both for integers and in a lattice. Also, any idempotent commutative semigroup is also Average. (Idempotent commutative semigroups are the same as partial orders with well-defined GLB operations.) It looks like, for odd primes P, the number of tables is 1 mod P. The number of tables seems to be around N^N. The number of systems seems to be around (N+1)!/2^N. Rich rcs(a)cs.arizona.edu

2 1