wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Going Postal
        
(Message started by: fieldazed on Apr 11^th, 2012, 12:03pm)

Title: Going Postal
Post by fieldazed on Apr 11^th, 2012, 12:03pm

The annual debt of the United States Postal Service is projected to be $18 billion by the year 2015. To help stem this ever growing deficit, the USPS would like to increase the price it charges for a first class mailed letter from forty two to fifty two cents. Having to pay an additional dime (ten cents) to have a letter hand delivered, door to door, anywhere in the U.S. is terribly unpopular with the general public. Perhaps equally rational to these objections is the Post Office's most recent proposal to make the increase more acceptable. The concept is to charge a random amount in increments of whole cents between $.01 - $1.04 (inclusive). To save on printing costs it is expected that only five denominations of stamps would be offered and a maximum of five stamps per letter would be allowed. Can you suggest the five stamp amounts?

Title: Re: Going Postal
Post by Grimbal on Apr 11^th, 2012, 2:59pm

I believe there is a solution for amounts up to $1.26.

Title: Re: Going Postal
Post by fieldazed on Apr 14^th, 2012, 8:11am

hey hey Grimbal - thanks for the response. the highest i've been able to get so far is $1.15 but did not really expect that to be best. did you write a program? or am i just dense and missing the obvious. dont have any programming skills myself so back to the spreadsheet for me.

Title: Re: Going Postal
Post by Grimbal on Apr 16^th, 2012, 7:36am

A program? Who do you think I am?

I spent a couple of hours with an excel sheet trying to generate each possible sum from one to as high as possible, adding a new value only in last resort, then adjusting the values down to fill any gap that remains in the list, patiently trying one possibility after the other.... and ended up writing a program.

::)

Title: Re: Going Postal
Post by fieldazed on Apr 16^th, 2012, 8:33am

well, after checking out some of your respones in the cs forum, thought maybe...

anyway, good to know and thanks again. now i get to continue solving my own puzzle knowing it can be bested. cheers :)

Title: Re: Going Postal
Post by pex on Apr 17^th, 2012, 12:54am

FWIW, my program confirms Grimbal's result.

This seems to me like the sort of problem that "ought to" be solvable by dynamic programming. However, I can't think of anything, and fiddling around with the parameters (different number of denominations, different number of stamps per letter) doesn't reveal any obvious patterns.

Any ideas for non-brute-force solutions?

Title: Re: Going Postal
Post by JohanC on Apr 17^th, 2012, 4:19am

on 04/17/12 at 00:54:27, pex wrote:

Any ideas for non-brute-force solutions?

I didn't make too much calculations, but guess that http://oeis.org/A099063 is the series we're looking for.
(Now I just need a clever explanation of why this would be ....)

Title: Re: Going Postal
Post by pex on Apr 17^th, 2012, 4:56am

I'm afraid it isn't related... at least the 3rd and 6th terms are incorrect, and I haven't calculated any further terms yet. Moreover, such a sequence would only apply to the special case where the number of denominations equals the maximum number of stamps per letter, and I don't see why that case would behave any differently from the others.

Edit: actually it's A084193 (http://oeis.org/A084193) and the problem appears unsolved in the general case. It's called, believe it or not, the postage stamp problem (http://mathworld.wolfram.com/PostageStampProblem.html).

Title: Re: Going Postal
Post by fieldazed on Apr 17^th, 2012, 8:31am

Wow - had no idea this topic has been so thoroughly and officially investigated. And with the postage stamp theme to boot. Too cool. Had also tried to find a general solution for n x n stamps and had even used the OEIS but with too few terms (not to mention the wrong one for 5 x 5 until now). Thanks pex, et al.

Title: Re: Going Postal
Post by pex on Apr 17^th, 2012, 8:51am

My pleasure! I didn't know about this problem, and it was a fun little exercise to keep my programming skills from getting too lazy. So, thanks for posting it!