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?