Author |
Topic: Going Postal (Read 1676 times) |
|
fieldazed
Junior Member
Gender: 
Posts: 55
|
 |
Going Postal
« on: Apr 11th, 2012, 12:03pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Going Postal
« Reply #1 on: Apr 11th, 2012, 2:59pm » |
Quote Modify
|
I believe there is a solution for amounts up to $1.26.
|
|
IP Logged |
|
|
|
fieldazed
Junior Member
Gender:
Posts: 55
|
|
Re: Going Postal
« Reply #2 on: Apr 14th, 2012, 8:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Going Postal
« Reply #3 on: Apr 16th, 2012, 7:36am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
fieldazed
Junior Member
Gender:
Posts: 55
|
|
Re: Going Postal
« Reply #4 on: Apr 16th, 2012, 8:33am » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Going Postal
« Reply #5 on: Apr 17th, 2012, 12:54am » |
Quote Modify
|
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?
|
| « Last Edit: Apr 17th, 2012, 12:54am by pex » |
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Going Postal
« Reply #6 on: Apr 17th, 2012, 4:19am » |
Quote Modify
|
on Apr 17th, 2012, 12:54am, 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 ....)
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Going Postal
« Reply #7 on: Apr 17th, 2012, 4:56am » |
Quote Modify
|
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 and the problem appears unsolved in the general case. It's called, believe it or not, the postage stamp problem.
|
| « Last Edit: Apr 17th, 2012, 5:01am by pex » |
IP Logged |
|
|
|
fieldazed
Junior Member
Gender:
Posts: 55
|
|
Re: Going Postal
« Reply #8 on: Apr 17th, 2012, 8:31am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Going Postal
« Reply #9 on: Apr 17th, 2012, 8:51am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print