Category: Random

The Coin-Change Problem

Since moving to the UK, I’ve been interested in what’s called the "coin-change problem." Simply put, it comes down to what is the best set of coins that minimizes the number of coins in my wallet.

Canada currently has 5c, 10c, 25c, $1, and $2 coins (having recently eliminated the penny), while Britain and Europe have 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1 and 2 coins (in their respective currencies).

The problem appeals to my random interests in applied mathematics and programming (aka engineering) but it turns out to be just slightly beyond what I can do now (I’ve likely forgotten some of the better tricks to solve this).

Luckily, the internet provided me with a link to University of Waterloo’s Jeffrey Shallit’s paper where he solved the problem for various cases in 2003.

For currencies that need to spend up to 99c, he found the following optimal change mixtures.

image

At the time, Canada and the USA both had the same 4 coins under $1, but should have changed dimes out for 18c piece. Interestingly enough, Shallit also determined that the best improvement to both country’s coin systems would be the introduction of an 18c piece.

Europe and the UK both have 6 coins worth less than a Euro/Pound but neither come close to the optimal system.

The mathematical analysis obviously makes a few unjustifiable assumptions. First, as Shallit points out, prices aren’t equally likely to end in every digit from 1 to 99. More importantly though, this approach assumes that people are equally as good at adding any set of integers together, which is hardly true. Even I couldn’t easily count by 18s and 29s. But perhaps the introduction of such an unorthodox system of coins would spark a renew a country’s arithmetic skills (or spur the move to electronic payments).

Most importantly though, this paper vindicates my hatred of Britain’s obnoxious 2 pence coin.

Always fully read email subjects

Because when you skim a subject and see “SFU Notice: More gunfire at Surrey Campus” there’s cause for alarm, but when the actual email says:

Movie gunfire at Surrey campus

The sci-fi TV series “Caprica” will be filming at SFU Surrey and Central City on Friday night, October 30. The Dale B. Regehr Grand Hall (mezzanine level) will be used as a futuristic airport lounge.

The action may include running through the grand hall, down the staircase to the main entry lobby. The actors will carry and fire weapons and fake blood capsules will explode.

If you’re visiting, working or studying at the Surrey campus be aware that the film shoot will begin at 6 p.m. It should finish by 9 p.m. but will continue in the Tower lobby and outside on the Plaza until 4 a.m.

Campus access will remain open on Friday night. There may short periods when the cameras are rolling when people on campus will be asked to stop for a few minutes as they come in from street level or the parkade. Security guards will be posted to assist with the access. The Surrey Fire Fighters Computer Lab and all other study spaces on campus are open as usual without restrictions during this film shoot.

Then you can rest easy.

On a side note: It is pretty sweet to attend a school that’s been used to film shows like Battlestar Galactica and Star Trek in the past.

Update: For factual honesty, SFU has never been used in a Star Trek episode or movie. It has made the following though:

  • The Day the Earth Stood Still
  • Personal Effects
  • Two for the Money
  • Agent Cody Banks
  • The Sixth Day
  • Anti-Trust
  • Fallen
  • Kyle X/Y
  • Masters of Science Fiction
  • Battlestar Galactica
  • Stargate SG-1
  • Millennium
  • X-Files.

Oh meme oh my

I’ll play along with the tag that was given to me by Dr. Jim at his little tea room and thinking shop (or some iteration thereof). So what is my “something unusual about yourself that I probably wouldn’t guess about you”

  • I’ve never broken a bone and have 20/20 vision. The worst injury I’ve suffered was running my eye socket into a trailer ball hitch (missing my eye by less than an inch) and getting a few stitches for it. Beyond that my body’s in pretty prime condition.
  • This is roughly how experimental physicists view the work of theoreticians and is roughly about how productive I am with grad-level homework assignments:
  • When I was young (about grade 9/10) I wrote an essay for Social Studies about how I would vote Reform since the “West” wasn’t being heard and deserved a voice. I now realize that the “West’s” (meaning Alberta) voice is not that intelligent.

Anyways, for my half-dozen minus one tags, I choose:

Massimo at Exponential Book, Aditya at Heuristicism, Chris at In Vivo, Brian at Left as an Exercise, and Devin at Simulating Reality. Of course, feel free to propagate if I didn’t choose you.

Updates

Blogging’s been a little infrequent of late, and it’ll be at least a week before anything comes up regularly since on Wednesday I head to Edmonton for the Canadian Undergraduate Physics Conference – both to represent SFU Physics at the Graduate Studies fair and to support my overstressed girlfriend who’s been organizing this event for the past year.

So here’s some news (in no particular order or even semblance of relatedness other than that it all interests me):

  • Obama is doing a better job defending our medicare system then most (but not all) Canadian politicians
  • On the CFI and accountability issue, I had received an informal response from CFI Transnational a few weeks ago (essentially saying the system works so why fix it), but they have yet to release anything official. I’ll likely come back to this next week.
  • In Malaysia, they’re going to cane a Muslim woman for drinking a beer. She’ll be the first woman in Malaysia to be caned for drinking under the Sharia Law there that only applies to Muslims (for now). It’s supposed to be a “ceremonial” caning as opposed to anything painful, but I still don’t think that cuts it. We don’t “ceremonially” spank children because it’s nearly as bad as actually spanking a child.
  • I got a new Netbook, and it kicks ass. I also got an external DVD burner and used it to put Windows XP on my old netbook which I plan to give to my girlfriend (so she no longer has to lug around her 10 lb “laptop”). The funds for this were provided by the UofA ECE department for me having the top presentation of the 2009 EE 495 research project.

  • If you’re interested in what my research career is shaping up to look like for the next couple years, and don’t want to wait for my inevitable posts that attempt to boil it down for easier consumption, you can try to get through this guy’s thesis [pdf] which somewhat relates to what I might be doing (I’m still not 100% sure since our lab’s not fully operational yet). Short form: measuring exotic micron-scale forces with Bose-Einstein Condensates.
  • Finally, North Vancouver is considering an obscure piece of technology to make getting up the steep hills easier on bicycles. See the video below:

Get on the bus!

Hey Edmonton Transit: Where the hell did all the hybrid buses go?

Did gas drop enough in price so we can continue to piss it away? Did the research phase end and the city decided to cheap out on them?

At least Sherwood Park is still trying out new buses. And on that – let’s get some double decker buses everywhere, if they work for England, they can work here!

Investments in public transit can reduce greenhouse gas emissions, general pollution, traffic, and give people a way to actually commute and read/text/anything-else-you-idiots-are-doing-behind-the-wheel-that-you-shouldn’t-be-doing. Give me more buses!

Of course, all of this is hopefully in part to give Alan a sense of bus-envy as his goal-of-the-year is to buy and renovate a bus.

Scrambling to find a hallowe’en costume?

Try going as Sarah Palin, because she is one scary bitch. Of course, don’t blame me if you don’t get let in to parties. Before you do that, chew on this: according to the Globe, Hallowe’en costume sales tend to be more accurate than most polls in predicting the election. Its impossible to verify amongst all the news and blogs bogging down the google machine, but if this is true, what the fuck is wrong with American politics that the scariest person usually wins?