Here’s a fun riddle posed by a student in the recent Algorithms: Design and Analysis course from Stanford University I participated in on the Coursera platform. I’m recording it here for posterity so I won’t forget. It’s fun to collect such riddles. That might make for cool party tricks. Note that I no longer have access to the original post so all this is paraphrasing from memory.
There is a sadistic warden in charge of a prison with 100 prisoners. He wants to execute these prisoners, but after much persuasion on your part, condescends to play a game with them that could result in some of them from spared. Each of the prisoners is numbered from 1 to 100. A room is set up with 100 drawers, all also numbered 1 to 100. Inside each drawer is a slip of paper, again numbered 1 to 100. However, the placement of each slip of paper in the drawers is randomized.
The game is that each prisoner is allowed to visit this room, one at a time. He is allowed to open the drawers one at a time and may open no more than 50 drawers. If he finds his own number on a slip of paper after having opened 50 or fewer drawers, he is saved. He must return each slip of paper into the drawer he found it in and is not allowed to exchange the positions of the slips of paper.
As an additional concession, you are allowed to visit the room before any of the prisoners may do so and examine the contents of all of the drawers. Furthermore, you may perform one and only one exchange before the game starts. That is after having viewed the contents of all 100 drawers, you may choose any two drawers and exchange the slips of paper inside them. You may not make any other changes and you may not communicate anything about the contents of the drawers to the prisoners.
The riddle is thus: what is the optimal strategy for the prisoners and how many the prisoners may be saved from execution using this strategy? The solution is after the break.
I’m leaving on holiday to Taiwan soon and will be leaving my job after that. This means that this blog will probably be updated only intermittently while I’m a in transition phase. In the meantime, here are a few links to some of the most interesting things I’ve read recently.
As everyone knows by now, the Rapture did not in fact arrive on schedule. Or perhaps it did but no one, including the folks from Family Radio International who so hyped up the event, was judged worthy. The station’s owner and preacher Harold Camping has since come out with a statement claiming that he’d made a mistake. May 21st was merely the spiritual Judgment Day during which God evaluated everyone’s souls. But the judgment will actually be executed only on October 21st, five months from now, triggering the end of the world.
Thankfully Malaysian high schools are nothing like the hellholes that public US high schools seem to be but thanks to American shows and movies, we have a decent idea of what they’re like. One aspect of the US high school experience is how students are segregated into different groups that are organized into a hierarchy that revolves around popularity. This extended essay examines why nerds in school, who are consistently found to be smarter than their peers, are consistently among the least popular students and comes up with some interesting insights.
Many vegetarians don’t eat meat because of the perceived moral issues involved in killing an animal for food. What if meat no longer had to obtained by butchering animals? What if you could simply grow the meat in a test-tube? This article looks at how meat could be grown by immersing stem cell samples in nutrient-filled petri dishes, and then moving them into scaffolding platforms to get them to grow into muscle tissue. If this gets off the ground, not only will it dispense with the moral issue of eating animals, it will also be a far cheaper and more environmentally friendly way to farm the meat that we so crave.
When I mentioned on QT3 that Ted Chiang had never published a novel, a fellow fan was quick to correct me. Actually, it’s more like a novella than a novel, but you can judge for yourself since The Lifecycle of Software Objects is now freely available to be read online. To be honest I find it to be the weakest of Chiang’s works I’ve read and it’s really more of an essay presenting many different insights and ideas about conscious software as pets and children than a novel. The central thesis is that you can’t create an artificial intelligence by writing an algorithm and running it iteratively until it reaches sentience. Instead, you need to nurture it just as you would a pet or a child, patiently teaching it and allowing it to have a variety of different life experiences to enable it to grow.
Finally, just for Malaysians, here is a link to the latest report on house price indices for Malaysia, updated for the first quarter of 2011. Some very tentative conclusions are that overall house prices in Malaysia are still increasing and especially prices for terrace houses in the Klang Valley are still holding up. But prices for high-rises in the Klang Valley is stagnant and has dropped for Malaysia as a whole. Condo prices in Penang in particular seem to be dropped significantly and the index has dropped to 2009 levels. This is especially illuminating since I’ve heard many people complain about very low occupation rates for condos in Penang despite the high prices. As always, a single quarter’s worth of data is not proof of a developing trend and should be taken with the usual grain of salt.
I’ve been amused by the recent news reports of fake eggs in Malaysia, which were supposedly imported from China. By now, the Veterinary Services Department has announced that the eggs are actually real, albeit low-grade ones that aren’t supposed to be sold to the general public. But the Consumer Association of Penang continues to insist that at least some of the eggs are fake. All this is despite an earlier announcement that Malaysia does not actually import fresh eggs at all from China.
So what prompted all this? My guess would be that someone noticed some odd looking eggs in a shop, recalled reading the widely e-mailed news reports of fake eggs from China from about 3 to 4 years ago, and put two and two together. But were those reports credible in the first place? My curiosity piqued, I set out to do some serious Googling.
The gold-standard in websites exposing scams and hoaxes of all sorts is of course Snopes, but unfortunately they don’t appear to have an article on this subject. The forum on Snopes however does have this discussion thread dating back to 2007 which largely concludes that making artificial eggs from chemicals doesn’t make economic sense and that no mainstream news organization picked up on the story. Since the tainted milk scandal in China was widely reported around the world, it doesn’t make sense that something as egregious as fake eggs would escape notice.
Another website specializing in scams and hoaxes, Hoax-Slayer, does have an article on the subject, also dating from 2007. It shows the widely circulated e-mail about the fake eggs in its entirety. This article also broadly concludes that there is no credible evidence that such reports are true and also traces how the hoax was originally spread by a number of websites and subsequently retracted. But as with all rumors, people only remember the rumor itself and never the retraction or refutation.
I’m on holiday for a while and getting last minute stuff done is taking its toll on my time, so here’s some links for stuff that you may or not may not find interesting. I won’t be updating this blog or Knights of the Cardboard Castle while I’m gone.
This article has traveled widely around the Internet so I’m guessing that most people will already have seen it. It’s about a tourism campaign organized by the small resort town of Atami in Japan. What’s unusual about this one is that the target demographic are players of a dating-simulation game known as LovePlus+, available on Nintendo’s hand-held DS system. This is a game targeted at males in which the object is to woo a girlfriend from a selection of virtual women. Accordingly, many businesses in the town are playing along with the fiction, checking hotels guests in as couples even though there is just one physical person for example and providing toiletries and towels for two persons. The same thing goes for restaurants who offer special themed sets. One QT3 posted noted that the game actually makes use of the device’s built-in microphone to oblige players to say “I love you” to the virtual girlfriends.
Are you tired of television executives’ ever more ridiculous ideas for reality shows? Well, no matter how much you hate them, you probably can’t match the Iraqis’ bile for this new show. The concept is that the producers invite local celebrities to the studio to conduct an interview but they’re actually secretly working with the Iraqi Defense Forces to plant fake car bombs on the celebrities’ vehicles. Then the army stops them at a checkpoint and accuses the celebrities of being terrorists and threatens them with imprisonment in American-operated prisons. All the while, hidden cameras are filming the celebrities’ shock and terror. Needless, this has provoked a withering storm of criticism.
Ever thought that garish carpeting and casinos go hand in hand? Well, I did. This article from Gizmodo claims that it’s deliberate and the purpose is to obscure the gambling chips that fall onto the floor so that it’s hard to retrieve them. Apparently, the casinos are supposed to rake in a significant sum of money whenever they sweep their floors, turning the carpets into another source of money. Other readers have written in to pour cold water on that theory however and explain that it’s meant to hide the wear and tear on the carpeting from so many people walking about and constantly moving machines and tables. Yet others claim that the garish designs make it easier to hide vomit stains. Whatever the real reasons are, it still makes for a fascinating line of inquiry.
It’s been a while since I last posted a YouTube video as a post and since I’m busy at work today, here’s a video showing how well a modern computer equipped with suitable sensors can parallel park a car. Note that there’s a human driver in the car but he’s just there for safety reasons and is not driving the car in the maneuver shown in the video. Certainly few human drivers will be able to pull this off.
Not much to write about at the moment, so here’s a link to the publicized map of how “touristy” different parts of the world are. What’s interesting about this is that the data is more fine grained than just tourist arrival numbers sorted by country. You can actually see which specific hotspots tourists are flocking too. Of course, it’s all automatically generated based on Panoramio so there’s obvious selection bias in the data. I wouldn’t imagine that many tourists from China for example use the site.
Rather shocking how western Europe is basically one huge tourist hotspot, but some parts of Malaysia are right up there in popularity. You can check out the full map on Google Maps as usual. It seems Google had nothing to do with this. It was just someone’s cool idea to link Google Maps with data from the Panoramio website.
Here’s a highly entertaining list of 18 of the world’s strangest airports, via Marginal Revolution. My favorite entry is the one with the runway cutting straight across the city’s main road, just like an old-style rainway crossing. Normally I dislike spreading links for lists like this but this one is particularly eye-opening.