Making Change and... Partitions?

Today’s math fun involves portions of yesterday's, but with a few more steps. It may also—dare I say it?—involve partitioning! I might be using the word partitioning in an incorrect way, and if so, then pardons please, (also, please let me know). The question is, what are the fewest number of coins you need to make change for up to a dollar.

Here's how I worked, using an iterative algorithm, (fancy words for: "I'm going to use the same trick over and over"). It was all about granularity of coins, and getting quickly from one amount to the next. The quickest way, (where quick is defined by using the smallest number of coins), to get to a large amount of change is with large coins. So, as we move around within 99 cents, the biggest step we can make is with a half dollar. Using yesterday’s method, we can fit one half dollar into 99 cents. That leaves us with 49 cents left move around in. The quickest way to make progress within that interval is with a quarter. We can only fit one quarter into 49 cents. That gives us our next interval which is moving around within 24 cents. We use our next biggest coin, a dime, and figure out we can get two of those into 24 cents. Within the remaining 9 cents, (the space a dime can't make up), the quickest way to move is with a nickel. One of those will fit. That leaves us a four cent interval to move in. We can fit four pennies into that, and we’re done! So, the answer winds up being

1 50 cent piece
1 quarter
2 dimes
1 nickel
and
4 pennies.

The next step, would be to prove that I'm correct, but how?

Comments

The Valentine's Day Magnetic Monopole

There's an assymetry to the form of the two Maxwell's equations shown in picture 1. While the divergence of the electric field is proportional to the electric charge density at a given point, the divergence of the magnetic field is equal to zero. This is typically explained in the following way. While we know that electrons, the fundamental electric charge carriers exist, evidence seems to indicate that magnetic monopoles, the particles that would carry magnetic 'charge', either don't exist, or, the energies required to create them are so high that they are exceedingly rare. That doesn't stop us from looking for them though! Keeping with the theme of Fairbank[1] and his academic progeny over the semester break, today's post is about the discovery of a magnetic monopole candidate event by one of the Fairbank's graduate students, Blas Cabrera[2]. Cabrera was utilizing a loop type of magnetic monopole detector. Its operation is in...

Cool Math Tricks: Deriving the Divergence, (Del or Nabla) into New (Cylindrical) Coordinate Systems

Now available as a Kindle ebook for 99 cents ! Get a spiffy ebook, and fund more physics The following is a pretty lengthy procedure, but converting the divergence, (nabla, del) operator between coordinate systems comes up pretty often. While there are tables for converting between common coordinate systems , there seem to be fewer explanations of the procedure for deriving the conversion, so here goes! What do we actually want? To convert the Cartesian nabla to the nabla for another coordinate system, say… cylindrical coordinates. What we’ll need: 1. The Cartesian Nabla: 2. A set of equations relating the Cartesian coordinates to cylindrical coordinates: 3. A set of equations relating the Cartesian basis vectors to the basis vectors of the new coordinate system: How to do it: Use the chain rule for differentiation to convert the derivatives with respect to the Cartesian variables to derivatives with respect to the cylindrical variables. The chain ...

More Cowbell! Record Production using Google Forms and Charts

First, the what : This article shows how to embed a new Google Form into any web page. To demonstrate ths, a chart and form that allow blog readers to control the recording levels of each instrument in Blue Oyster Cult's "(Don't Fear) The Reaper" is used. HTML code from the Google version of the form included on this page is shown and the parts that need to be modified are highlighted. Next, the why : Google recently released an e-mail form feature that allows users of Google Documents to create an e-mail a form that automatically places each user's input into an associated spreadsheet. As it turns out, with a little bit of work, the forms that are created by Google Docs can be embedded into any web page. Now, The Goods: Click on the instrument you want turned up, click the submit button and then refresh the page. Through the magic of Google Forms as soon as you click on submit and refresh this web page, the data chart will update immediately. Turn up the:...

Copasetic Flow

Search This Blog