Hacker News Reader

Comment by murbard2 | Hacker News Reader

In case you're wondering, there are 8 digits on the one dollar bill serial number, so assuming a random draw by the DJ, the odds of one of the 100,000 dollars matching the draw every day would be very close to 1 in a thousand. After a year, you'd only have a 30.58% chance of winning at least once. The expected value of combing through the dollars to find a match would be about $30 every day. I wonder if he sorted them into a binary tree.

View on HN

Of course, the DJ might well have been reading a number off a bill from his own wallet each day, ensuring there'd be no payouts...

Yeah, I was thinking the same thing. What kind of radio station has a $30,000 promo budget for a one off contest, especially in 1980s dollars. That's around $60,000 today.

I imagine no one ever won that money.

I was thinking that too. Especially if word ever reached the radio station that some guy just had just withdrawn 100,000 dollar bills from his bank...

He was too focused on finding loopholes in rules of the world he lived in and did not realise there are robbers who didn't adhere to rules at all, robbers who made their own hole in his house.

I feel like this is a guy who is in that danger zone of intelligence where he can recognize an opportunity before others but doesn't have enough lightbulbs on to power through it properly.

He could have really used some CS/math coursework

I think this is where a lot of small-time criminals lie in the spectrum of intellectual capacity I'd say. Add in some arrogance / conceit and you have a recipe for distrust / hatred of authority including those that might actually be smarter than you. He fell victim to a number of pyramid / Ponzi schemes after all.

I think it's more a combination of being creative with above avergage intelligence and determination coupled with low risk assessment (poor judgement).

I think it obvious that he did not sort the bills. The article say that he and his wife spend all their time going through stacks of bills, stopping only to eat and bathe (and they couldn't even check all the money in time). If they sorted the money it would have taken him looking at under 20 bills to determin if he had the matching bill or not.

So they lost because that was what happens when a hacker doesn't take the time to learn about algorithms and data structures, eh?

I think you could probably, after some practice, radix-sort bills into a 10×10 array by a digit pair at about 4Hz by hand, maybe 1Hz at the outset. 100k / 4Hz would be about 7 hours, so your initial sort pass (with piles averaging 1000 bills) would take 7 to 28 hours. A second sort pass over the next most significant digits would take another 7 hours, and then the bills would be sorted into groups of about 10. At that point you'd want to put the money into, say, a thousand or ten thousand envelopes, organized into drawers or folders or something, so that when the DJ calls the number, you open the right drawer, pick out the right envelope, and scan through the five, ten, or twenty bills in there to find the right one, if you have it.

You could do the passes lazily, too. Spend the 7 (or 28) hours to do the first sorting pass into piles of 1000. Then, when the DJ reads out the number, pick out the right pile of 1000 and spend 4 minutes sorting it into 100 piles of 10 or so, which you then stuff into 100 envelopes, possibly calling the DJ at the time. If the DJ calls another number with the same leading two digits, you're prepared; if not, hey, it's 4 minutes.

So you're right.

Sad. He legit hacked the Press Your Luck show by figuring out hidden patterns that he could use to do the apparently impossible. Too bad he didn't have the knowledge to hack the DJ's contest.

Sadder still that he let the money come ahead of his girlfriend.

I certainly agree with you that sorting makes sense, and that sounds like a logical algorithm. I think 4Hz, or even 1Hz, is wildly optimistic though. 100,000 bills is bags and bags of cash. You're going to be spending a lot of time dealing with the envelopes and folders and things. You're certainly not going to be able to make 10 piles of 10,000 bills each in front of you. As soon as you get more than a few bills in a pile you'll need to spend time straightening them, putting them in envelopes or whatever, pulling more bills out of the bags, etc. Not to mention resting your hands and eyes. You could make it easier with cash trays or something to keep them from flying all over the place as you sort, but even so, there's no way you're going to be firing out more than one a second continuously for hours.

I wasn't suggesting making 10 piles; I was suggesting making 100 piles. (With cash trays with cubbyholes you could reasonably do 1000.)

You can take, say, 300 bills in your off hand, use your thumb to flip each new one, and use your good hand to take it from the handful and place it into one of the 100 piles within arm's reach on the table, according to the digits you saw on it while your hand was returning from placing the last one. If you're doing this in 800ms, then when your hand is empty, you have spent 240 seconds and can easily spend 10 seconds picking up and riffling another 300 bills, bringing you to 270. After two hours of this, you have sorted 8000 bills into 100 piles of 80 or so bills; you should now take a ten-minute break. After another two hours, you should spend five minutes putting those 100 piles into envelopes so they don't fall over, and take another ten-minute break. (Or a half-hour break for lunch, which I wasn't counting as part of the workday.)

That's what 1Hz looks like, and I think you can get to that speed pretty much right off the bat, especially since accuracy is not crucial here (unlike in almost all cash-handling operations!). And yeah, 4Hz sounds "wildly optimistic", but it isn't, really. That kind of speed improvement for manual movements with experience is common for assembly-line tasks. Watch the knife movements of a sous-chef on video, and consider that every one of their movements is irrevocable; they don't get a chance to spend time straightening crooked cuts.

That's still a lot of bill sorting though. Not sure if you can demand sequential bills from the bank, but getting your bills pre-sorted might have been the best option, then it's just a matter of looking at the first and last bills.. Could have even just left it at the bank knowing the digit range and avoided the whole theft problem.

Oh sure, and take all the fun out of the problem by invoking an oracle....

hey lateral solutions are the most fun.

some other obvious ideas:

- only the serial numbers matter not the physical bills, write them down on a ledger with an index

- bill reading machine with simple ocr, scans all serial numbers into a db

- solve the opposite problem: given the dj's serial number, is it possible to track down that particular bill? Arbitrage the opportunity by running the same contest in other states for a lower sum

I guess a binary tree is not necessary. Just separate them in bricks by the first few digits, and sort them inside too. Then, just put all the bricks that start with 1 in the kitchen, the bricks that start with 2 in the bedroom, ... People is fast scaning a few items and select the right brick from the vault.

(Disclaimer: I didn't try this at home.)

Can you imagine actually trying to sort 100,000 bills by serial number? Even if you can sort a bill every 10 seconds continuously, which you obviously can't, it would be about 7 weeks of full time work. Radio stations tend to run contests for what, a few months? So your expected return is perhaps a few thousand dollars. I can't imagine many worse jobs.

See my comment above for a better complexity analysis of this task.

some sort of hashtable/BST hybrid - where each entry in the table points to a BST, and the hash function just returns the first base-10 digit off of the bill.

Presumably the 10^8 space doesn't get exhausted, though. They don't run bills until they've literally printed 83,200,000,000 of them.

So the operative question is how many bills were ever in circulation, not how big the theoretical space of the serial numbers are.

Well the dj would presumably be searching within the theoretical space, since he wouldn't have access to the list of actual serial numbers printed.

Oh, maybe I didn't read it well enough. I thought he was pulling a bill out of his own pocket and then checking to see if anyone had a matching serial number.

Does anyone know if the serial numbers are printed in order? I didn't see the answer in a very cursory web search. If they are, presumably it would be trivial for such a contest to avoid ever paying out -- just choose from the upper end of the SN range.

Perhaps I don't understand your thought process, but how could anyone have a matching bill that way? If the DJ was reading off a serial number, the only person to have a match would be the DJ himself, since they are unique.

Afaik, the only time serial numbers get reused is when a bill is reissued because it is damaged or worn, in which case they would shred the old bill (also, the new bill would get a neat star next to its serial number).

To begin, there are 32 bills on a sheet. In addition, they can re-run the process, but increment the letter portion of the serial each time.

Depending on which parts of the serial number the DJ read off (just number, or number and letter), there could be up to 832 bills for a single serial number: http://onedollarbill.org/decoding.html

> Does anyone know if the serial numbers are printed in order?

That's generally what the "serial" part of "serial number" means. And why the smarter bank robbers ask for non-sequential bills, because new bills generally have consecutive serials which are simpler to trace

The government prints about 2-5 trillion dollar bills each year. I'm pretty sure the entire range of serial numbers has been exhausted for $1: http://www.moneyfactory.gov/uscurrency/annualproductionfigur...

http://onedollarbill.org/decoding.html

Billion, not Trillion!

1 Trillion is 150 singles for every human alive

Oops - I was off by an order of magnitude. Regardless - the treasury prints about 5% of the total serial numbers each year and according to the links I provided they already cycle through serial numbers.

To be pedantic: you were off by three orders of magnitude. An order of magnitude is a 10x multiplicative factor.

Your expected value calculation is also missing an important factor. He had a ~30% chance of being +$30k after a year, sure, and he probably did that math. But he also had a non-zero chance of being -$100k through robbery. He was spinning the wheel each day the cash was in the house, with less control over the odds than he had on the game show, and in the end he whammied after all.

Yeah, the problem is you have to sort your 100,000 dollar bills. If you had 100 boxes with 1,000 bills each -- maybe sorted into 10 smaller stacks of 1000 bills each -- then you'd only have to spend a few minutes each day checking whether you'd won.

But how long would it take to sort out those 100,000 dollar bills in the first place?

Reply on news.ycombinator.com