The classic coupon collector’s problem asks for the number of samples it takes to collect all coupon types from a sequence of coupons in which each of the \(k\) types of coupons has an unlimited number of copies.

Here is a different kind of problem: if there are limited copies of each of the \(k\) coupon types (say, \(d\) copies), how many samples does it take to collect \(t\) coupon types?

(Read the article)

Comments(0)

Suppose there is a straight road, infinitely long at both ends, located 1 unit from your starting location. Find the most efficient path to reach the road, and the worst-case total length of this path.

The trivial but wrong way is to go for 1 unit in some direction, then trace the circumference of a unit-radius circle. The road will surely be found this way, but the path length is \(1+2\pi\), which can be improved upon.
(Read the article)

Comments(4)

Here’s an interesting and, shall I say, practical problem brought up at group meeting today: If you have say, n identical looking wires strung across a long distance between point A and point B, and your job is to label all wires with just an ohm-meter (to measure continuity, i.e. short circuit or open circuit), how many trips between A and B does it take?

Indeed, the only way to use an ohm-meter for this purpose is by tying wires together. Clearly the number of trips shouldn’t be larger than \(\log n\) or so, simply by tying various halves of the set of wires at one end and going to the other end to measure. But there are other kinds of coding that do better.
(Read the article)

Comments(0)