Hacker News Reader

Comment by hnfong | Hacker News Reader

Here's an actual case where understanding computer science would have been immensely helpful...

> The motivation for this aberrant behavior was a contest put on by a local radio station. Each day a disk jockey would read a serial number aloud on the air, and if any listener was able to produce the matching dollar bill they would win $30,000. Michael reasoned that 100,000 one dollar bills was 100,000 opportunities to win the prize, giving him a statistical advantage. And even if his scheme proved fruitless he would just redeposit his money, so he figured he had nothing to lose.

> Michael and Teresa spent each day rifling through piles of cash looking for matches, pausing only for such distractions as eating, bathing, and excreting. They soon realized that it was impossible for two people to examine that much money in the allotted time

(sort then binary search)

View on HN

Maybe, but even then I doubt the scheme was well thought out. He had 100,000 bills but the total number of serial numbers is many magnitudes greater than that. The chance that he'd actually have a hit was close to zero. And that is assuming the contest was legitimate in the first place.

Seems like the classic form of this contest would be for the radio DJ to pull a bill out of his wallet and read that serial number over the air...

Haha this is what I was thinking. Did anyone ever actually win this prize?

IIRC serial numbers aren't unique. Even if the DJ was doing that, there would still be a chance. (albeit extremely small)

> A unique combination of eleven numbers and letters appears twice on the front of the note. Each note has a unique serial number. The first letter of the serial number corresponds to the series year.

https://www.uscurrency.gov/denominations/bank-note-identifie...

It's not the whole story. In genuine currency, serial numbers are only unique within a series. Series 2017A and series 2021 notes can (and in fact do, since they start over at A00000001A) have identical serial numbers.

In 2014, the Bureau of Engraving and Printing (BEP) accidentally assigned overlapping sets of serial numbers for replacements notes to its currency-printing facilities in both Washington, D.C. and Fort Worth, Texas. The overlap occurred from serial numbers B00000001* to B00250000* and B03200001* to B09600000*. On the lower right-side of the front of the note, the letters “FW” with the face plate number indicate it was printed in Fort Worth.

https://www.pmgnotes.com/news/article/9321/Duplicate-serial-...

A significant quantity of those bills has probably been pulled from circulation. One of the things the Reserve does is swap damaged bills and look for counterfeits. Every bill they destroy is another crisp bill they can return to banks without fucking with inflation.

Notes prior to 1996, and $1 and $2 notes, use only a 10-digit serial number so there's repeats in new series.

You’re thinking of parallel numbers.

I can explain. But first, we have to talk about parallel universes and half-button-presses.

Great way to catch forgeries

That would be fraud by the radio station, wouldn't it? You can't run a contest that is impossible to win.

So? Who's gonna know?

Giveaways like that were far less regulated at times in the past.

Looking at a dollar bill, I guess the serial-number space is 8 digits plus 2 letters. So naively the chance of any hit with 10^5 bills is 1 in 676000, yeah. (But maybe the serials were smaller then?)

Re the lookup problem, you could initially "hash" all the bills by say the two leading figures, in your first pass.

It's all way stupider than the game-show hack.

Other comments take the letters to not count, which would make the chance 1/1000 per trial -- not so ridiculous.

Yeah like, even if he somehow owned 10% of all dollar bills in existence and had a somewhat efficient way of looking them up, his expected value is still only $3,000! Does it really make sense to do all the work of taking your hard-earned, once in a lifetime windfall of $100000 (easily 4x the median annual income at the time, even for a person who had a steady professional job), out of the literal bank where it safely sits making ~10% interest in the mid 80s, and store it in your messy house in drawers and trash bags, for the opportunity to make 3% back? Not the thoughts of a rational person!

You mean the E[V] is 103,000. He still gets to keep the 100,000 he withdrew and re-deposit it.

I wouldn't consider the original 100K to be part of the expected value since that's money they already have, not money they're winning...

He should have just put it in a savings account and looked for something else.

Actually it's only 6 digits of the serial number that needs to match. According to [1] the game Michael Larson was trying to win was organized by $ale of the Century (SOTC), which was actually a TV show, not radio show. And as per [2] it was run for only 2 weeks in the fall of 1984, and the prize was indeed $30k as the Damn Interesting article claims. And there is a recording of an episode at [3] showing the six digits to match were "550085". Since Michael Larson had 100,000 bills, he basically had 10% chance of winning the $30k prize. If the game was run 14 times (over 2 weeks), he would have had a 77% chance of winning (1-.9^14)

I found another episode at [4] where the host even explains "according to the Treasury Department there as 3.7B one-dollar bills in circulation; that means [...] there are 3700 dollar bills with the winning number"

[1] https://www.gameshowforum.org/index.php?topic=5153.0

[2] https://tvtropes.org/pmwiki/pmwiki.php/Series/SaleOfTheCentu...

[3] https://www.youtube.com/watch?v=neCxKLjsow8&t=1510s

[4] https://www.youtube.com/watch?v=bnvSJZj3m0U&t=1296s

> Since Michael Larson had 100,000 bills, he basically had 10% chance of winning the $30k prize.

A bit less than 10%, since some bills would be functional duplicates.

Oh, you are right. It looks like it's around 9.5% according to a quick simulation I ran.

I had the same thought too, if you take the time to sort the bills the lookups are easy. And it probably doesn’t take much more time to sort them than it does to go through them all once looking for a number.

For a radix sort on the 8 digit USD serial numbers, it takes 8x more time (the 2 letters can be ignored). That could be halved by radix sorting on pairs of digits, but then keeping track of 100 piles instead of 10 probably negates most of the gain. In practice, partial sorting suffices to reduce the serial number search time to a reasonably short amount, e.g. by 4 rounds of radix sorting.

Right, so basically by your ninth time doing this you’d have broken even (ish) on time. He was doing it every day so that’d be a great investment.

It also would reduce the possibility of errors greatly I’d think.

100k bills doesn’t need an exact sort to be vastly faster.

Day one you sort by first digit, then keep sorting matching digits stopping when you have say 20 numbers in a pile. My guess is you break even on day 2 and the first day is only slightly worse.

That’s a good point, each individual sort probably takes only slightly longer than just looking through them for the number. So the actual sorting might not really add much time at all

in a single round of digit-pair radix sorting, you can put 100 piles of ≈1000 bills each into 10×10 cubbyholes, a piece of furniture which is small enough to fit on a desk. then you need about 20 minutes to linearly search through one such pile when the dj announces a number, which is probably fast enough to win

if you have a second cubbyhole array, when you linearly search through a pile chosen from the first cubbyhole array, you can radix-sort that pile by another two digits, dividing it into piles of ≈10 bills. those piles are small enough that you can keep them sorted as you build them without much loss of efficiency, even on a computer

if you can fill the first array with 100 wallets with 10 numbered tabs each, like the tabbed dividers in a looseleaf notebook, you can divide the bills into 1000 piles on the first radix-sorting pass. in practice it might be too much work to find or make the wallets

but i think the sad thing about michael larson's story is not that he didn't know enough about computer 'science' (or, i guess, library 'science'), but that he spent more effort searching for a hack that would make hard things easy than it would have taken to do them the hard way, destroying his personal relationships in the process

Yeah this part bothered me. It's surprising if they really didn't immediately realize randomly looking at single bills was an impossible strategy.

Kind of an interesting problem. Complete sorting in a timely manner is basically not possible because of the physical reality of 100k pieces of paper. But maybe you can group the bills into 100 piles of "last 2 digits", so then for each lookup you "only" have to check 1000 bills. And then later, while searching a group, you can take the time to further sort them by the 3rd digit. I guess it also depends on how long you expect the contest to go on, i.e. how many lookups you will do.

Even with the simplified grouping strategy, let's be generous and assume it takes you 3 seconds to look at a bill, figure out what to do with it, and physically move it to the correct place. That's still 83 person-hours to do a single pass and put the bills into 100 groups for quicker lookup. With 2 people, that's 5 full 8 hour days of non-stop sorting.

I would copy the serials onto paper in sorted order. Then I only need to find the bill after I know I have it. I'd still need to find the bill on demand - but you typically get 10 minutes to call and then days to prove it (this was the 1980s - you couldn't email a digital photo back then. Today I'd forge the digital photo and have hours to set the real one aside for when they check)

This is more or less the way I’d go. It’s “what the client asked for” versus “what solves the client’s problem”. You don’t need to find the bill within minutes, you need to know that you _have_ the bill quickly.

Grab a big binder, half dozen packs of dividers, a pack of loose leaf paper, and a box of pens.

Divide the binder into ranges. In each range use a separate piece of paper for the next digit. Don’t worry about sorting past there, just write all your serial numbers down.

Now you can use the dividers to narrow it down to around 2,000 bills. Flipping through ten pages to find the next digit you’ve narrowed it down to about 200 bills. You can probably scan two hundred numbers quickly enough.

I think I'd scan them all, and divide them into 100 piles of 1,000. While one person is working on uploading and processing scans to a database system (tagging/adding a field for its pile), the other could be sorting the piles if they want. Basically, seeing if you have a match and limiting it to a pile of 1,000 while not having too much overhead of a ton of different piles.

If you do match, each person could check through 500 bills easily, and there's no sorting needed.

in 01984 the apparatus to scan them all would have cost you more than the bills

Indeed, the first consumer digital camera, the Sony Mavica was only 3 years old and wrote still frames to tape, and it would still be 2 years before a digital still video camera would make it to the US market, and you'd have to shuffle the images around on a Still Video Floppy, as USB (and 1.0 at that) wouldn't appear for another 12 years, and even the first serial port webcam would be 10 years.

there existed drum scanners, flatbed scanners, and I think even hand scanners that you could drag over a bill https://en.wikipedia.org/wiki/Image_scanner#Hand_document_sc... but maybe you'd have to check computer shopper from 01984 to be sure

Maybe less lucrative but when we had some new bookshelves installed and moved all our books onto them I used mergesort to get them in order. ;)

Bucket-(insert-)sort is also an all time favorite. I've taught it to many people already.

It helps that it works in a very intuitive way.

Teach it to us! I'm not familiar with this.

It's bucket sort, and parent is suggesting insertion sort within each bucket as the pre-merge step.

Say you're sorting alphabetically by title. You make one bucket per letter- put books into their respective bucket based on first letter of title. Then sort using insertion sort within each bucket. Then you're done.

(insertion sort is the human natural one- look for where the next one goes based on what you have so far and insert)

Same works for other heuristics.

I've often pondered the optimal book organisation, sorting and inserting system. Organising by subject seems a good start, but then you have size to conser. Then you also tend to arrange by space - i.e. you might put two subjects together based more on similar size or shelf capacity then logical subject grouping.

For inserts a reverse-sorted inserting-from-the-back makes most sense to reduce moving of books, but I suspect there's probably an optimal 'free space' value to allow for easier inserting.

> I've often pondered the optimal book organisation

Let me introduce you to an option I recently found. I went to get a book from our (large) bookcase and found they’d all been reorganised based on cover colour.

that's grounds for divorce

Makes it much easier to buy new books that way: https://www.ebay.com/sch/i.html?_nkw=red+books+by+foot

This reminds me of the old website, "Where's George?"

Sample bill report: https://www.wheresgeorge.com/b:QZHjxdYnJ&entry=17

I got one of those bills as change on NAVSTA Rota back in the early 2000s, it was neat to see the path it took.

Reply on news.ycombinator.com