A logical puzzle

I’ve been remiss in writing for this blog because I’ve been busy with the courses I’ve been taking on Coursera.org. Currently I’m taking both Introduction to Finance and Algorithms. The Algorithms class is particularly challenging for me and involves significant work because there’s a programming assignment each week. It’s taught by Robert Sedgewick of Princeton, who is something of an authority in the subject. Interestingly, Sedgewick’s own doctoral thesis advisor was Donald Knuth, who is of course a legend in computer programming circles.

Anyway, just for fun, here’s a logical puzzle from a recent assignment for you to ponder over. I’ve converted it into a puzzle to make it more accessible, no actual programming necessary, but the essential logic of the problem remains the same.

Let’s say that you’re working at a booth of some sort and you have only one task. A client will come up to your booth and announce a number. Call this number k. This number represents how many items you will need to hand back to the client at the end of each task. The client then starts handing you items, let’s say they are beach balls, each of which are uniquely identifiable, one at a time. The client never tells you how many balls there are in total. He or she just starts handing them to you, one by one.

At some point, the client will announce that he or she has finished handing over balls. Now your job is to return k balls, selected with uniform randomness from the balls you were just given, back to the client. Sounds easy right? But here’s the constraint. Your booth can only store k balls at maximum. That is to say, you can only hold as many balls at a time as the number of balls you need to return to the client at the end of the task. You may choose to keep or discard any ball but once you choose to discard a ball it is gone forever and you can’t ever get it back.

So how do you ensure that you can select k number of items with uniform randomness, out of a pool of potentially many more items, while being restricted to only holding k items at a time?

“Curiosity has landed” video

Ok, this totally breaks this page’s formatting, but what the heck. Forget the Olympics. This is the greatest spectacle going on right now and it’s not even on Earth. Yes it’s a CGI rendition instead of real imagery but what do you expect about something going on on Mars? The landing procedure is the stuff of science-fiction.

Recent Interesting Science Articles (July 2012)

July 2012 has been a less awesome, insofar as science articles go. I guess things do slow down in the summer.

  • This isn’t the first article about empathy for humans as displayed in dogs that has appeared in this blog, and it won’t be the last! This article from The Economist covers experiments performed to see if dogs can really perform actions out of empathy for the perceived suffering in humans, as opposed to acting out of curiosity. This was done by observing the behavior of dogs when alternately encountering a human crying and exhibiting other signs of distress or merely humming. They also alternated between using a trusted human for the dogs and a complete stranger. The results were that the dogs could indeed recognize distress in humans and react by whining, nuzzling, licking, and fetching toys for the human perceived to be suffering. They did this to the suffering human even if he or she was a stranger and their master was in the same room, indicating that it was the comfort of the suffering human that they sought rather than their own comfort.
  • Just last month I had an article talking about how more modern pop music is getting sadder and sadder while becoming more emotionally ambiguous. This month I have a new article from Reuters making a different claim: that pop music is getting louder and louder, while at the same time becoming less diverse with a more limited variety of sounds. They’re not directly contradictory but they are odds enough that the two teams should probably have a good long discussion with each other about just what is going on.
  • This next one is cheating a bit as it’s more of a demonstration video than a science article. Its about the color shifting abilities of a species of cuttlefish in Australia, Sepia plangon. Nothing new, you say? Except that this one is not only capable of shifting its colors, it can apparently shift each side of its body to a different color scheme, in this case, mimicking a female with half of its body and a male with the other half. This demonstrates not only as astounding level of control over its own colors but also an awareness of just who is looking at it from each direction.
  • Ever wondered while walking in the rain if it would be more effective to run through the rain or walk steadily through it to minimize wetness. I did and judging by the contents of this Washington Post article, I’m not the only one. Intuitively, running is better to minimize your time spent in the rain but at the same as you travel fast, you run into more raindrops in your path. Walking steadily increases your exposure time, but you present a small target and you don’t walk into raindrops. The paper summarized in this article concludes that for most cases, running is best but the true answer really depends on your body shape, the direction of the rainfall (vertically or at a lateral angle), the angle of the path you are traveling across and so forth. It is truly a profound topic.
  • Finally, no rundown would be complete without the biggest scientific news of the month: the confirmation of existence of the Higgs boson at the Large Hadron Collider. There are many articles about it on the web but I’m partial to this one from the BBC. There are no practical applications for this but it is pretty solid confirmation of the Standard Model of physics.