This is a problem via fakalin.

You have 10 pieces of string, each with two ends. You randomly pick two ends of string (possibly from the same string, possibly from different ones) and tie them together, creating either a longer piece of string or a loop. You keep doing this until you run out of free ends.

What is the expected number of loops you end up with?

(Read the article)

Comments(0)

Walking around campus these days, there are cryptic-looking things like

\(\binom{n}{2}\mathrm{.com}\) and \(\binom{n}{2} \ni \binom{i}{u}\)

obviously referring to a dating site — currently it’s restricted to MIT and Harvard students. This one tries on an idea that I’ve heard discussed numerous times in different contexts, but apparently nobody went and did it in all these years. Instead of running a matching algorithm, it asks third parties (i.e. matchmakers) as well as the interested parties themselves to suggest matches. The thing that is supposed to keep this low-risk is anonymity: a match isn’t revealed until the two primary parties involved mutually accept or their lists intersect.

As with all things that involve anonymity, this asks for trollish and antisocial behavior. I’ve already registered three aliases on moira for exactly this purpose — ok, ok, so they’ve suppressed that antic after people raised concerns, though these and other ramifications should have perhaps been worked through a bit more carefully pre-launch.

The spam potential remains. A matchmaker’s identity isn’t revealed unless both people accept her suggestion, so pranks and insults can be conducted to an extent. One way around this may be grafting social graph data onto the system for collaborative filtering (if they manage to obtain such data…). And if they do, perhaps the suggestions of more closely related people should weigh more, along with those of successful matchmakers. Perhaps there should even be more weight if multiple matchmakers concur. This is extremely intriguing, because eliminating spam is equivalent to predicting who is a likely match, and collaborative filtering for this problem is an unexplored direction.

The more fundamental question is why such a site is even necessary.
(Read the article)

Comments(0)

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)