Category: Open questions

Some Puzzles

A tale of two slugs: If you drop a bullet and simultaneously fire one horizontally from the same height, which one hits the ground first?

From Mythbusters. It’s a mini Airplane on a treadmill myth of sorts.

When tested on laypeople, the first reaction is incredulity:

“Don’t bullets move in straight lines?”

“I thought bullets move horizontally for an incredibly long time before they start to fall!”

As a first approximation, you would assume that they take the same time. But then air drag mucks up the analysis, and before you know it, you’re writing Matlab code to deal with Ugly Nonlinear Coupled Ordinary Differential Equations. (UNCODE)

Or, you know, you could just do the real thing:

The problem with this- and with Mythbusters in general, is that their confirmations aren’t really confirmations, and their busts aren’t often busts either. They map every experiment, often involving hundreds of parameters, onto a set with three elements: Confirmed, Plausible and Busted. This argument has been made, probably a dozen times over.

So what’s the problem here?
Air drag scales as the square of the object’s speed, and for
sufficiently high muzzle velocities, the vertical component of the air
drag on the fired bullet can exceed the air drag on the dropped bullet.
This means we can expect at least two kinds of behaviour! All this
fuzziness is masked by the fact that the air drag on a bullet is really low1 to begin with. This article illustrates nicely.

It gets worse! Once bullet speeds get transonic (most rifles fire at supersonic muzzle speeds), all the modeling goes out the window. I haven’t an inkling of what happens then, save for the realization that the drag increases manifold.

It’s interesting. And definitely not simple. Now, onto the UNCODE!

A war of attrition: Well armored species in the animal kingdom engage in duels that are staring contests. The winner is the one that stands its ground and glares until the opponent turns tail. Of course, both contestants have other work to do; time is of the essence! Assume that the rewards and the costs associated with winning and losing the contest are the same for both contestants. What is the staring rule that, once adopted by the entire group, cannot be exploited by any individual member to its benefit?

From chapter five of The Selfish Gene.

Dawkins calls such strategies evolutionarily stable; strategies that individuals cannot exploit at the group’s expense. Once a group adopts such a strategy, it sticks. (It explains, for instance, why lions don’t eat other lions. No, really.)

So: what is the evolutionarily stable strategy in a war of attrition? The name is telling. Both contestants incur the cost of lost time, irrespective of who wins.

Suppose you estimate that the reward of the contest, a mate, say, or a stash of food, is worth a certain amount of your time. (Time that you could spend foraging for food elsewhere, for instance.) Since your opponent makes the same estimate, keeping up the glare for that much time is inherently unstable. Whoever keeps it up for an instant longer wins!

The book goes on to explain the solution, but I’m looking for a rigorous proof. Every time I try, it feels just out of reach!


Risking the perils of blogging about blogging2, I’m going to mention that the primary purpose of this blog, as a notepad for interesting snippets of text (and the odd ramble), has been taken over wholesale by web note-taking tools (Evernote, in particular), leading to this most depressing state of affairs.

I’m reminded of a short Archie comic where the gang has rigged up a house of horrors, and everyone except Jughead is thoroughly spooked. Just when it seems that nothing can faze him, he goes into a catatonic stasis at the central exhibit: an empty refrigerator.

Yeah, fallow blogs are the empty refrigerators of the Internet.

+1 for fantastic note-taking tools, though. They suffer from only two problems, as I see it.

  1. They’re not public. At least, not easily findable when you need them to be.
  2. They’re not Emacs.3
Footnotes:

1How low? The force of drag is given by one half of the drag coefficient times the density of air, times the projected area of the bullet, times the square of it’s velocity. For typical values, the deceleration due to air drag comes to about 0.001 m/s^2 for the dropped bullet, and about 10 m/s^2 for the fired bullet. Note that the latter acts almost horizontally through much of the the bullet’s flight.

2It’s the one golden rule of writing on the web: Don’t write about your writing!

3 Or Vi. Or anything decent when it comes to text editing.

Obscurantism

Seinfeld (the sitcom) was filled to the brim with self-reflexive scenarios. On a number of occasions, Costanza and Seinfeld engage in a conversation on their conversation- but the one occasion this was particularly striking  was when the two brainstorm to find an idea for the sitcom Jerry. (The irony.) The series nested itself in a self-deprecating public display of self-awareness, exemplified by the instance where Costanza utters in a moment of ennui: “This, this is what the show’s about! The show, is about nothing.”- breaking the fourth wall in the process (and, some might add, exposing it to be the tripe it is).

From mathworld, a corky, off-beat answer to a question from the Google Labs Aptitude Test:

19. ‘Tis known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining.

Find though a cooler bijection, where you show a knack uncanny, of making your choices contain all K of mine.  Oh, for pedantry: let K be no more than half N.

Answer: ‘Tis more problematic to disentangle semantic meaning precise from the this paragraph of verbiage peculiar.

At this point, some exposition might be in order. What can a satirical in-joke from a TV series have in common with a well known binomial coefficient rule (and sentence construction that would spoof a recursive transition network)?

What, indeed.

Continue reading

Recursive Regexes

…have been troubling me for days now.

The Regex engine maintains a stack, so regular expressions in Perl can be constructed recursively. For instance,

$paren = qr/ \( ( [^()]+ # Not parens | (??{$paren}) # Another balanced group )* \) /x;

matches a string if parentheses in the string are paired correctly. (Taken from Regexp Power.)

That funny (??{}) (apparently) keeps qr/ / from interpolating the variable in the funny brackets when the expression is compiled- saving the interpolation for when the matching is carried out, which sends it recursing deeper.

So here’s the question:

A palindrome is a nested set of palindromes. That is, a [ palindrome – {first character, last character} ] is a palindrome again, and so forth until there is (i) nothing, or (ii) one character left. Cases (i) and (ii) are palindromes by definition. So how do you write a regex that matches any palindrome?

The best I could do was:

$palin = qr/ (.)? #Any character or no character, captured (??{$palin})? #A palindrome, not interpolated yet \1 #Character captured in line 1 /x;

But this doesn’t work. Any ideas?