Month: February 2003

Posted on

The 23 prisoner problem

I’ve been thinking about the 23 prisoners puzzle on David Weinberger’s blog, and I’ve come up with an answer. It’s different than the one Mike Booth found. Mike’s solution has a very nice elegance to it; mine is a brute force probability solution, which relies all numbers coming up equally often–eventually.

I don’t remember enough of my statistics to calculate the expected time for my solution to free all the prisoners, but I have a strong suspicion that it’s not nearly as long as you would think. I don’t think it’s a coincidence that there are 23 prisoners in the puzzle. This is exactly the number of people you need in a room for the probability of two of them sharing a birthday to be 50% (the “Birthday Paradox”).

Anyway, here’s the (a) solution. Look away now if you want to try the puzzle on your own.

Part 1: Properties of the two-switch system

With two binary switches, you can encode four digits: 0, 1, 2, and 3. However, because you have to change the state of one and only one of the switches, there are some states the switches cannot be in when you leave the room. For example, if the switches are set to zero (off, off), you can set them to 1 (off, on) or 2 (on, off), but you can’t set them to 3, nor can you leave them at 0.

What you can always do, however, is ensure that the switches encode an odd or an even number. No matter what state the switches were in when you entered the room, it is your choice whether they end up odd or even when you leave the room. (See diagram below.) Thus, you can leave a 1-bit message to the person who enters the room the next day.

State transitions for the switches in the 23 prisoners problem.

Part 2: Instructions for the prisoners

In your strategy session on the first day, every prisoner is given a number from 1 to 23. You also agree to keep a new kind of calendar, where every month has 23 days, also numbered from 1 to 23. (The names of the months are not important, just that after day 23, you roll back around to day 1 again.)

On all subsequent days, whenever you go into the switch room, you set the switches to “odd” if your prisoner number matches the number of the calendar day. If your number doesn’t match the calendar day, you sets the switches to “even”.

What you also have to do is “read” the 1-bit message the previous prisoner sent to you. As soon as you enter the switch room, you know two pieces of information:

  1. The number of the previous day (e.g., day 16)
  2. Whether that day’s prisoner (number 16) was in the room yesterday (if the switches were set to “odd”)

Now, all you have to do is wait, and keep track of all the days when a the correctly numbered prisoner was in the switch room the day before you. Eventually (after many months) you will have visted the switch room on all 23 days. And eventually you will reach a point where you will have marked off all the prisoner numbers on your checklist. Then you can go tell the warden to let you all go.

Will this really work?

I think so, eventually. The calculation isn’t quite the same as the Birthday Paradox, though. With birthdays, the probability of catching two on the same day increases as you get more people into the room. With the prisoner problem, even though each additional prisoner increases the chances of one of them getting an incredibly lucky streak, each additional prisoner also increases the number of “coincidence events” that are necessary for everyone to go free.

The real-world answer, of course, is that they’re all ‘gator food no matter what. Either

  • A) they wouldn’t agree on a strategy on that first day, or
  • B) someone would forget what strategy they’d agreed on, or
  • C) the solitary confinement would drive someone mad enough to fancy their chances with the alligators instead of spending another day in the box, or
  • D) the warden was just messing with their heads, and never had any intention of setting them free in the first place. He was twisted enough to come up with this scheme. Do you really think he’s going to let his evil plans be thwarted by a bunch of pesky kids?

Update: Several people have pointed out the flaw in my reasoning. I’ve written a little more about it here.

Posted on

New camera

Casio Exilim EX-S2Our new camera arrived yesterday. It’s a Casio Exilim EX-S2, and oooh it’s gorgeous.

We already have a perfectly good digital camera (an Olympus C3000), but it’s chunky, and we carry it around in a padded pouch. It has served us extremely well for the last two years, and will continue to do so. The pictures it takes are crisp, with vivid colours even under poor lighting conditions. It does great close-ups.

Alex in the car with Baby on his headBut we were finding that when it comes time to take Alex out on an adventure, it’s yet another bag to lug around. Alex is too tall to fit in the backpack any more, and so we usually bring the pushchair along. So we have a boy, a pushchair, a little backpack with supplies, and a camera bag. The camera bag does fit in the supplies bag, but taking snapshots becomes so much less spontaneous when you have to pull the pack off your back, open it, take out the camera bag, open it, take out the camera, switch it on, and…oh, he’s doing something else now.

The Exilim is the size of a credit card, only thicker. It’s pocketable. It turns on and is ready to take pictures in about a second. It has a fixed focus lens, so there’s very little shutter delay. And it has a 2 megapixel resolution, which means the images come in at up to 1600 x 1200. It is thoroughly sweet.

Alex with grapeThe photos it takes aren’t as good as those of the Olympus. But we got it as a snapshot camera, not as a high-end solution. And it takes some wonderful snapshots. It seems to do better with lots of light than it does indoors, but even indoors and without a flash it’s pretty good, provided you can keep the camera steady. (And this is not as easy as you might think. Its small size works against it in this regard.)

Overall, it promises to be a great addition to our photographic arsenal.

Posted on

Cards as Weapons

Ricky Jay - Cards as WeaponsOh, how I would dearly love to own a copy of this book. I first heard about it some time in the mid 90s, when I saw a TV documentary about the amazing Ricky Jay. It was the bit where he cut a pencil in half by throwing an ordinary playing card at it that got me really hooked. I practiced a bit, and got to the point where I could spin a card all the way across the room, but I didn’t take it any further than that.

Cards as Weapons was first published in 1977, and has been out of print since then. Today is the first time I’ve seen the book for sale on Ebay. (Admittedly, I’ve only been looking since last summer.) But at a cool $750, I don’t think I’ll be placing any bids. There’s a copy available through Amazon.com for $295, but even this is too expensive. I’m more interested in the text than in the book itself, so I’m hoping that maybe some day an enterprising small publisher might pick up the rights and do a new edition.

Posted on

The future of music lies with the promoters, not the publishers

Via the Shifted Librarian:

“Experiments are rife in the music business these days — and Boston will be a test market for one of the most novel of them. Clear Channel Concerts, the nation’s largest concert promoter, has ambitious plans to record live CDs of its shows and sell them to patrons within five minutes after those shows end. Clear Channel is targeting Boston as the first site for the new plan, according to sources within the organization.

Multiple CD burners would be brought in, and the live CDs would probably sell for around $15 in the same way that T-shirts and other merchandise can be purchased after concerts. No one knows what the demand would be, but the project is expected to begin at club shows within a couple of months, then be refined and work its way up to the amphitheater level, though that may not happen until next year, sources say.” (Boston Globe)

How cool is this? $15 to get a CD of a gig you’ve just been to, right after it has ended! I know that whenever I’ve just been to a good concert, I’m all jumped up on happy endorphins and almost eager to spend money on merchandise. (Unfortunately, Clear Channel is talking about trials in a “couple of months”, so the pilot will probably be to late for my road trip.)

I can see this making huge inroads into the way people get their recorded music. Rather than listening to bands on the radio, and going out to a shop to buy their CD (of which you may have heard one or two tracks), you get recommendations from friends about good concerts, and when you like one you buy the CD. Maybe there’d be more “compilation” gigs, with several bands on stage in a night, so you could sample your new music at live venues, rather than on the radio.

And this way, people wouldn’t all end up with exactly the same recording of a particular song. Because it’s live music, every gig is different. The music promoters would also start actively encouraging file sharing and swapping, because that would drive more people to their concerts. If the concert were at was particularly good, surely you’d want to have copies of those particular versions of the songs?

Yes, you could wait until someone else bought the CD and gave you a copy, but then we’re back to the fact that you’ve just been jumping and singing for two hours, you’re in a great mood, and you’re highly receptive to the idea of parting with your money.

There are a couple of articles I’ve read recently (“Piracy is Progressive Taxation” by Tim O’Reilly, and “Embrace file-sharing, or die” by John and Ben Snyder) that discuss the current battle between music publishers and the file sharing community. Anyone who isn’t in the music publishing industry (or is paid by them) seems to eventually come to the same conclusion:
File-sharing networks don’t threaten book, music, or film publishing, they threaten existing publishers.

There’s no law that says musicians and bands must go to existing publishers. If Clear Channel’s idea takes off, then it’s the concert promoters who will be the publishers of the next century. Bands won’t sign recording contracts with record companies, they’ll sign concert deals with promoters.

Will musicians end up with a better deal out of it? Maybe, but probably not. Concert promoters are in the game for the money just as much as the current record companies are, and by all accounts both industries are equally big nests of vipers. The difference is that Promoters will want the public to swap files, and will do everything they can to make this easy, while the Publishers won’t.

The public will love this, and technology companies will love it, too, because there’s a fantastic opportunity for them to make money from new hardware. The CD-R idea is just a transitional one. iPod and its lookalikes are the future of personal music players. Sooner or later, all music players will feature a firewire or USB2 port for sucking down hours of music in seconds. Concert venues will feature banks of docking cradles, or transfer cables, where you can swipe your credit card and suck down the gig in en eyeblink.

Suddendly the future of music publishing doesn’t look so grim any more. The only thing that could stand in the way of this revolution is if the current music publishers start buying concert promoters, and lock down this new business model before it can even start. That would suck.

Posted on

Martin and Scott’s Toad Road Trip

Martin and Scott's Toad Road TripIt has finally all come together. We got the flights. We got the hotel. And now we finally have the actual tickets for the gig… Scott and I are going to see Toad The Wet Sprocket in Boston–in just three weeks from now!

After splitting up in 1997, the boys from Toad decided to get together again at the end of last year to play a couple of benefit concerts. Then there came a rumour of a small tour in 2003. I was extremely excited. Scott and I are both big Toad fans, but we never got the chance to see them play live. Perhaps if they hit the East Coast of the US, we could get some cheap flights, and see them play!

Word of individual tour dates started leaking on the Glen Phillips and Lapdog message boards out during December. The official dates were released just before Christmas, and yes, there were plenty of East Coast dates to choose from. We looked at New York, Boston, Norfolk VA, Washington, Philadelphia, and Chicago, before we settled on Boston.

But although the Toad site listed dates when most of the shows would go on sale, they didn’t say when tickets for Boston would be available. We didn’t want to get flights before we had tickets for the show. We also noticed that some of the shows that went on sale early were selling out fast. So as January wore on, we were getting terribly worried that the tickets would be released without us knowing, and they’d sell out before we could buy any.

I watched the ticket site like a hawk, and just after I caught word that the public on-sale date was Saturday 18th, there came a helpful message from the Glen Phillips mailing list to say that fans could buy pre-sale tickets from Thursday 16th. I tried to buy tickets that day, through the Next Ticketing web site, but found that I couldn’t. Apparently they won’t issue pre-sale tickets to addresses outside the US. Fortunately, Abi’s family lives in California, and they were happy for me to get the tickets sent to them, so they could forward them to me. Phew!

Once that was sorted, we could go ahead and book flights and hotels. I’d previously found that Expedia gives excellent deals on holidays to the US. Oddly enough, though, you get a consistently better deal if you avoid booking at a weekend. The flight and hotel combinations were consistently £50-£80 more expensive on a Saturday or Sunday than if you book them during the week.

The first time I noticed this was at the start of January. I’d checked the prices mid-week, then gone in on a Saturday to look at them again. “Bugger,” I thought when I saw the increased prices, “we’ve missed all the cheap deals.” But this turned out not to be the case. When I showed Scott the prices again the following Wednesday, they were back down to their lower levels. And when I checked again the next weekend, they were back up.

It’s possible that cheap holiday deals are continuously being released in mid week, then all getting snapped up by the time the weekend arrives, but somehow I doubt it. I reckon they’ve found that most people book their holidays at the weekend, and so are trying to make the most of this. (So let that be a warning.)

Anyhow, with the concert being at the start of March (not exactly tourist high season), we got a fantastic deal on flights and a hotel. We’ll be flying from Edinburgh to Boston via Amsterdam on Friday 28th February, staying three nights at the Wyndham Boston hotel downtown, and then flying back again on Monday 3rd March. Toad are playing at the Avalon Nightclub on the Saturday evening.

Oh boy, am I looking forward to this.

Which is why I was marvellously surprised when I turned to Tantek Çelik’s blog this morning, and found that he’d been to the Toad gig at the Fillmore in San Francisco last night! Neat.

“The crowd was hilarious. I think we saw maybe one person under 30. Lots of sedated 80s styles–is big hair coming back? Guys should not wear white pants. Saw one guy who thought he was at a Pearl Jam concert and a few hippies too. Then there was tie-dye drunk guy that looked like he was having a seizure but it turned out he was only bopping his head and dancing.”

Yikes. I know I was never young and hip, but I guess I’m going to have to face the fact that I’m not young any more, either. On the other hand, being a thirty-ump professional means I have enough financial stability and flexibility to occasionally do wild stuff like fly across the Atlantic for a weekend.

I’m going to have to get my hair bleached again before we go, though 😉