Algebraic and Transcendental

A number is called algebraic if it is the root of a nonzero polynomial with integral coefficients (or, equivalently, rational coefficients); otherwise it is transcendental.

Item: there exists a nonintegral c > 1 such that c^n 'converges to the integers': that is, for any eps > 0 there's an N > 0 such that c^n is within eps of some integer, for all n > N. (I think the golden mean was an example, but I can't find or remember the reference book at the moment.)

Item: it is apparently open whether any such number can be transcendental.

***

Next up, two questions of my own on algebraic numbers. Possibly easy, possibly silly, but I don't know the answers.

Define the interleave of two numbers

b = 0.b_1b_2b_3... and c = 0.c_1c_2c_3...
(both in [0, 1], and using the 'correct' binary expansions) as

b@c = 0.b_1c_1b_2c_2...

1) Suppose b, c are algebraic. Must b@c be algebraic?

2) The other direction. Suppose b@c is algebraic. Must b, c be algebraic?

In both cases, I am inclined towards doubt.

***

Final thoughts (and these are observations others have made as well)... computational complexity theory seems to have certain things in common with transcendental number theory:
-an interest in impossibility/inexpressibility results;

-markedly slow progress on seemingly basic
questions--is (pi + e) irrational? does P = NP?

-attempts to use statistical and otherwise 'constructive' properties as sieves to distinguish simple objects from complicated ones.

So, could complexity theorists benefit from interacting and learning from transcendental number theorists? If nothing else, looking back on their long historical march might teach us patience and an appreciation for incremental progress.

Cardinal Rules

1. Pick your favorite countable set S. Let F be a 'nested' family of distinct subsets of S; that is, if A, B are members of F, then either A is contained in B or B is contained in A.

Then clearly F can be at most countable... right?


A puzzle from Bollobas' recent book.


2. Given a collection C of functions from N = {1, 2, 3, ...} to N, say that C is unbounded if for any function f (in C or not), there exists a function g in C such that g(i) > f(i) for infinitely many i.

Clearly the class C of all functions from N to N is unbounded. Also, standard diagonalization techniques tell us that no countable collection C can be unbounded (exercise).

The question then becomes: what is the smallest cardinality of any unbounded collection C? Assuming the Continuum Hypothesis is false, where does the threshold lie?

Fortunately or unfortunately, there seems to be little we can say about this issue within the standard axioms of set theory. Assuming CH is false, the threshold could be as low as the first uncountable cardinal, or as large as the continuum, or in between--this I learned from Jech's encyclopedic book Set Theory. There are many questions of this flavor, where the key construction (in our case, constructing a 'bounding function' for a given 'small' collection C) is easy to do in the countable setting, but essentially impossible to analyze when there are uncountably many requirements floating around.

The need to satisfy uncountable collections of requirements in a construction is so common that new axioms for set theory are put forward expressly to assert the possibility of doing so (under some restrictions that make the axioms plausible); 'Martin's Axiom' is an especially widely used axiom of this type. Kunen's book on set theory seems like a good reference for MA (though I'm just starting to learn about it).

Of course, the Continuum Hypothesis itself makes it easier to satisfy collections of requirements of size smaller than continuum, since such requirements are then at most countable! This leads to some bizarre constructions, the possibility of many of which stands or falls with the CH itself. The excellent book Problems and Theorems in Classical Set Theory gives many of these, and Bill Gasarch recently exposited one such application in Euclidean Ramsey theory. On the other hand, Martin's Axiom, which is independent of CH, allows set theorists to prove many interesting results while remaining more 'agnostic' about cardinality issues.


I think that set theory is a blast, and that its logical structure resonates with issues in computer science. But I'm far from expert on the subject, so if I've said anything inaccurate please let me know.

So a Puzzle Walks into a Bar...

In the Boston area, two American values--higher education and beer--converge in a big way. Possibly as a result of this convergence, it's a good bet that on any night of the week, there's a bar where you can watch or participate in a trivia contest. (Or so friends tell me.)

These contests have two features that make them interesting from this blog's perspective. First, there's apparently a company that sends its quizmasters all over town, and presumably supplies them with fun questions. So let's assume that the questions are drawn from some fixed distribution D, unknown in advance.

Second, these are team games. So now--let's say you've got n trivia-loving friends, and you're trying to form a team of k < n of them to maximize your chances of winning. k might grow with n.

To help you choose, you can take your friends out for drinks and watch the contests for a few weeks or months before deciding on your team. You can record who out of your friends answered which questions correctly as they watched. (For simplicity, let's say that if someone answers correctly, they know they're right, and if they don't know the answer they keep their mouths shut.) But you can only afford poly(n) of these expensive outings before you decide your team and start trying to rake in gift certificates or stuffed bears or whatever.

So--what are your prospects in general for determining the best team?

(i.e., we're looking for algorithms that, for any group of friends and any D, perform well with high probability.)

If one has only been exposed to computational problems in which all the necessary information is presented as a single input, a problem like this can be disconcerting. There appears to be both a computational and a statistical puzzle to solve, simultaneously. (If the computational aspect doesn't seem challenging, keep in mind: your friends' various knowledge-bases may be similar, disjoint, or anywhere crazily in between...)

My challenge to readers is to think about how this problem fits into algorithms/complexity theory. Not necessarily to solve it--I've found it touches on published research, and I will give references in a future post--but to relate it to what you've seen before. I'm hoping this might be a good warm-up to thinking about ideas from computational learning theory which I also have been wanting to exposit.

I should note that even slight tweaks on this problem could lead to questions I haven't thought about, but which I encourage others to (e.g., what if player ability is affected by drinking?).

New TOC Aggregator! And, a Puzzle.

Getcher daily Theory dose here, courtesy of Arvind Narayanan. It collects content from many of the best TCS blogs online... and somehow mine made it on there too.

In other news... recently a friend named William Torres (ordinarily more musical than mathematical) asked me an intriguing question:

Can you rotate a rigid, hollow sphere in space, holding its center fixed (but possibly varying the axis of rotation), in such a way that every point moves the same nonzero total amount?

Note that we're not referring to a point's net displacement; in fact, the net motion of the sphere will always correspond to a rotation about some axis (you shouldn't necessarily find this obvious... see wiki), hence two points will always have zero net displacement. What we're interested in is equalizing the path lengths of points' trajectories--how much 'exercise' they get. Of course, the amount should be finite.

I don't know the answer to William's question, but this doesn't mean it's hard. As a warm-up, see if you can prove the following (which I think I can show): It is possible for each point on Earth (understood as a sphere) for each point to have the same nonzero average wind speed over a 24-hour period (where wind is understood as a continuous vector field on the sphere, with vectors tangent to the sphere's surface, and varying continuously over time).

This contrasts with Brouwer's classical 'Hairy Ball Theorem', which states that at any given time, the wind speed will be zero at two or more points on Earth.

More Wordplay

Call a word 'orderly' if its letters are in alphabetical or reverse-alphabetical order. Consecutive appearances of the same letter is OK.

-Find a famous mathematician whose name is orderly.

-Now find a complexity theorist.

-How long an orderly word can you find?

-Have any other challenges for the rest of us? A CS research problem related to orderliness?


In a different but still-wordy vein, Free Rice is a fun site, where you donate rice to the UN by testing your vocabulary. The words get impressively obscure as you score more correct (multiple-choice) guesses, much more so than, e.g. the also-recommended Word of the Day page, and once you're arguing with friends about what 'carronade' means it's a good bet that you're not fighting poverty in the most effective way possible, but I still recommend it. What this quiz underscores for me is how much verbal knowledge we hold at the very edge of awareness and competence. (Hat tip to Chaya for the link.)

Another Heads-Up for Puzzlers

Two puzzle collections (both drawing on diverse sources) caught my eye recently. The first is 'The Art of Mathematics: Coffee Time in Memphis', by the famous mathematician Bela Bollobas. It's got a number of gems, for instance: is it possible to 'load' two dice, i.e. skew their faces' probabilities, possibly in distinct ways, such that when both are rolled the resulting distribution is uniform on {2, 3, ... 11, 12}?
The book is definitely worth looking at, but, perhaps as a function of its ambition to teach some important (and cool) math along the way, it is rather difficult on the whole, and ridiculously so in some cases (one of his 'puzzles' is to disprove the Borsuk conjecture, a problem that had been open for something like 60 years. Granted, there is a hints section, but come on...). The Amazon page lets you browse a number of the more approachable puzzles, so check it out.

The second is 'Mathematical Mind-Benders', Peter Winkler's much-anticipated sequel to the instant classic 'Mathematical Puzzles: A Connoisseur's Collection'. I haven't spent enough time on the new one to see how it stacks up to its predecessor, but it definitely contains some beguiling problems. Many are 'old friends' of the puzzle genre (bugs, prisoners, hats, etc.), but remade and fiendishly harder--think of the fight with Super Shredder at the end of 'Turtles II'...

However, while Winkler's books are also quite hard, they generally involve much less 'higher math' than Bollobas', which is really written for readers interested in mathematics proper. Another emphasis of Winkler's new book is on surprise answers, as in the following two puzzles from the first, warm-up chapter:

-A pencil has a regular pentagon as its cross-section, and its maker's logo on one face. If the pencil is rolled on a table, what is the probability that it comes to rest with the logo facing up?

-You have 15 bags. How many marbles do you need to produce an arrangement where each bag contains a different number of marbles?

Winkler also unveils a neat word puzzle called 'the HIPE game', something he co-invented as a teenager. One player comes up with a string of letters and challenges the other players to find a word containing it (as a block of adjacent letters): for instance, can you place HIPE in a word? Of course, the problem poser should actually have a word in mind...

Some other challenges he gives: BG, CM, FC, FW... and the book has many more (and harder). I'm normally pretty decent at word games, but this one is killing me so far.

Thanks, Bollobas and Winkler!

In Plane Sight

Flatland is in tumult after a spate of triangle-on-triangle violence, and the prevailing attitude is one of utter paranoia. The triangles, which can see out of each of their three vertices, are so mistrustful that they will not tolerate the presence another triangle unless they can see each of the other's vertices, and, moreover, see it with each of their own eyes. Triangles are assumed to be disjoint and opaque.

It is your job to help as many triangles as possible congregate, in a fashion acceptable to all participants, to promote dialogue and peace. Find yourself a pen, paper, and a bag of Doritos, and consider:

Problem: Can three equilateral triangles of equal size be placed in a 'acceptable' arrangement? (If yes, what is the upper limit, if any?)


Notes:

-I do know the answer, but it took me awhile. I've never really understood triangles...

-I haven't read Abbott's 'Flatland' since maybe age 12, so I have no idea how faithful this scenario is, or whether related visibility issues were explored in the book. As far as I know this puzzle has not been posed elsewhere, but I do recall there being at least one interesting visibility puzzle in Engel's book 'Problem Solving Strategies'.

-Notice how I refrained from saying 'acute paranoia'... it wasn't easy, but I think I'm a better person for having done so.

Be Rational

Today, enjoy a home-baked puzzle in real analysis--a somewhat old-fashioned subject that I can't help but love (much like automata theory).

We know that pi = 3.1415... is transcendental, i.e., it is not a zero of any nontrivial univariate polynomial with rational coefficients. Is it possible we could generalize this result?


Part I. Is there a continuous function f: R --> R, such that

a) f takes rational numbers to rational numbers,

b) f(x) is zero if and only if x = pi?


Part II. If you think no such f exists, then for which values (in place of pi) does such an f exist?
On the other hand, if f as in Part I does exist (I reveal nothing!), can it be made infinitely differentiable?


For those new to real analysis, 'weird' objects like the desired f above generally have to be created gradually, through an iterative process in which we take care of different requirements at different stages. We try to argue that 'in the limit', the object we converge to has the desired properties. (Does this sound like computability theory? The two should be studied together as they have strong kinships, notably the link between diagonalization/finite extension methods and the Baire Category Theorem.)

Passing to the limit can be subtler than it first appears; for example, a pointwise limit of continuous functions need not be continuous. Here is a pretty good fast online introduction to some central ideas in studying limits of functions.

Loopy Thinking

Earlier I posted on the 'backwards orientation' in mathematics, aimed at finding new characterizations or 'origin stories' for familiar objects. Here is an exercise in this kind of math, hopefully amusing.

We'll consider the class of simple, rectifiable closed curves in the plane, that is, non-self-intersecting continuous 'loops' in R^2 to whose segments a definite finite arc-length can always be assigned.

Given two points x, y on such a curve C, let d_C(x, y) denote the distance along the curve from x to y (in whichever direction is shorter). On the other hand, let d(x, y) denote regular Euclidean distance.

We say that a curve respects distances if, for all u, v, x, y on C, we have

d_C(u, v) < d_C(x, y) if and only if d(u, v) < d(x, y).

Now, a circle respects distances in this sense; do any other curves in our class?

Would your answer change if we used a weaker notion of respecting distances? Namely, for all x, y, z in C,

d_C(x, y) < d_C(x, z) iff d(x, y) < d(x, z).


Bonus problem: the analogous question for rectifiable-path-connected, closed plane sets with nonempty interior. Convex bodies respect distances; do any others? (Recall that we previously discussed a very different kind of characterization of convexity.)
It may help to know that between any two points in such a set, there exists a path of minimum length (see Kolmogorov & Fomin's book on functional analysis, Sect. 20, Thm 3.).

A Tricky Vote

An election is being held to select one of two candidates, A or B. n voters turn out in a long, orderly line. A motley crew of pollsters show up to predict the turnout, but none is diligent enough to survey the entire line, or savvy enough to conduct a proper statistical sample. Instead, each pollster arbitrarily selects some single interval of the line and queries everyone in that interval. The intervals may be of various sizes, and they may overlap.

After comparing their haphazard data, the pollsters notice that candidate A, the presumptive favorite, has more than two-thirds support in every survey interval.

Assume the process is 'nice' in the following senses:

-Everyone truthfully reveals their intentions to the pollsters, and intentions don't change;
-Everyone in line eventually votes (once) for their intended candidate, and votes are faithfully counted;
-No one changes position in the line.

Also assume that everyone is surveyed at least once.

Can you conclude that candidate A is the winner?


Note that 2/3 is the lowest threshold one could hope for: for consider 4 voters, with prefereces going B A A B, and with 2 survey intervals consisting of the first three and last three voters respectively; then A has exactly 2/3 support in each, yet the outcome is a tie.

If this problem gives you trouble, try solving it first with 'two thirds' replaced by 'ninety-nine percent'.

I enjoy questions like this one, that try to deduce 'global' conditions from a collection of 'local' observations. With the advent of 'property testing' in computer science, they have become increasingly important to the field. I hope to make further posts on the subject soon, and possibly also discuss generalizations of the above problem (Does anyone know if/where it's been studied before?)

Update, 9/27: I've since learned that this problem falls in well-trod territory of functional and harmonic analysis; specifically, the (affirmative) answer to this problem essentially states that a certain 'maximal operator' over a function space is 'bounded'. The solution techniques described by David and myself in the comments are standard and fall under the rubric of 'covering theorems', the most basic one being due to Vitali. I'll try to blog more soon on what I've learned about this problem, which gets very interesting in 2 dimensions...

Guardian Angel Decoding

In the conventional setting of error-correcting codes (ECCs), there are three parties: Sender, Receiver, and Adversary. Sender wants to send a message m to Receiver; problem is, Adversary may intercept the message string and modify as many as e > 0 symbols before Receiver gets the message.

The idea of an error-correcting code is to encode the message m in a redundant fashion as some 'codeword' C(m), so that even after as many as e errors are introduced, the original message m is uniquely recoverable.

For a simple example (not representative of the sophistication of more powerful codes), say Sender wants to transmit a single bit of information, and e = 1. Then we could have C(0) = 000, C(1) = 111, and Receiver can correctly recover the message bit by taking the majority vote of the 3 bits received.

For a much more comprehensive introduction of ECCs from a TCS perspective, see e.g. this survey by Sudan, or this one by Trevisan.


Now here's a slightly whimsical idea: suppose we add a fourth party to the scene, a Guardian Angel allied with Sender and Receiver. The Guardian Angel watches Sender encode the message; though it cannot completely stop the Adversary from making its modifications to the codeword, it can step in to prevent as many as d < e of these modifications. These 'saves' are performed all at once, after the Adversary reveals its intended modifications, and the Angel can choose which sites to protect; it cannot make new modifications of its own.

Clearly the Guardian Angel is a boon. Consider an ECC in the standard setting (no Angel) with an encoding/decoding system that successfully recovers messages even after as many as e errors are introduced; the same protocol can recover the message with as many as e + d errors, with the help of a 'lazy Angel' who arbitrarily selects d of the adversary's errors and corrects them.

So here's the question: is this as good as it gets? Or can the Angel act more cleverly to help Sender and Receiver succeed in the presence of even more errors?

Note that we might want to change the encoding/decoding protocol itself, to optimize for the Angel's presence. For example, suppose d = 1; then we can successfully transmit a single bit in the presence of any number of errors, by simply having the Angel encode the intended bit in the parity of the message sent (convince yourself this works). The challenge is to use the Angel effectively while preserving the information rate and other positive properties of our ECC, as much as possible.

This is meant as a puzzle, but a somewhat open-ended one (in particular, one that ought to be investigated in the context of specific ECCs) that feeds into active research in coding theory. I'm hoping it will stimulate readers to rediscover some of the important notions in the area. I'll give hints and/or literature pointers sometime soon.

***

...Ok, here goes:

Hint: 'List Decoding' is a concept which has seen a lot of applications recently. Its starting point is the realization that, if we are willing to not always uniquely recover the codeword after errors are introduced, but instead narrow down the possibilities to a 'short' list of candidate messages, we can, for many natural codes, tolerate many more errors. For instance, with a binary alphabet, we cannot achieve unique decoding for nontrivial codes beyond the threshold of a .25 fraction of errors. On the other hand, if we allow list decoding (say, returning a poly(n)-sized list of candidate messages given a corrupted codeword of length O(n)), then we can tolerate almost a .5 fraction of errors.

For more discussion and references, see this post of Lance's.

So: does list decodability of a code imply unique decodability with the help of a Guardian Angel, perhaps an Angel making only a relatively small number of 'saves'? And if the list decoding procedure is computationally efficient, can the Guardian Angel and its associated decoder be efficient as well?

***

For a more thoroughly whimsical puzzle scenario, check out Conway's Angel Problem.

Flooding and Kleitman's Theorem

In their classic, and highly entertaining, survey book on probabilistic methods in combinatorics, Alon and Spencer pose the following question: suppose we generate a random graph on n vertices, independently including each edge with probability 1/2. Suppose we do not look at the graph right away, but are informed that the graph we got contains a Hamiltonian path, that is, a path visiting each vertex exactly once.

Does this knowledge make it more or less likely that the graph is nonplanar?

Of course, it should make it more likely. Please stop and verify that this ought to be true. Can you prove it?

Results that prove facts like this are called 'correlation inequalities', and the simplest one that applies here is called Kleitman's Theorem. (In Alon and Spencer, Kleitman's Theorem is derived from more general results, but I encourage you to try to prove it directly.)

Say a subset A of the Boolean cube is monotone if, whenever x is in A and y >= x (bitwise domination), then y is in A too. We may also say that A is 'upwards closed'.

Kleitman's Theorem states that, given two monotone subsets A, B of the Boolean cube, if we pick a random cube element z, the chance of z being in B cannot decrease if we condition on the event that z is in A.

So, in the example, let the bits of the cube represent the presence/absence of edges in a graph of fixed size. Let A and B be the properties of Hamiltonicity and nonplanarity, respectively. Then Kleitman yields the intuitive fact we were looking for.

***

Now I am going to describe how Kleitman's result solves the previous flooded-city puzzle I posed last time. In fact, trying to reprove Kleitman's Theorem was what led me to pose the flooding puzzle in the first place, although I now tend to think of Kleitman's as the logically prior result.

To do this requires an easy generalization of Kleitman's Theorem, where we replace the boolean cube in the statement with {0, 1, ... m}^n. So, e.g., vector (3, 4, 5) dominates (3, 3, 4), but is incomparable with (4, 0, 0). In fact, we'll only need this result for n = 2.


Create a bipartite graph U x F, with unflooded houses on the left and flooded houses on the right. Add an edge from an unflooded house h to a flooded house h' if there exists an h-to-h' path with all steps running north or east.

Given a set S of unflooded houses, let N(S) denote the flooded houses adjacent to some house of S in the bipartite graph.



In the example above, the green-circled houses are S and the orange-circled flooded houses are N(S).

Each unflooded house contains a unit amount of water to be delivered, while each flooded house needs an amount |U|/|F| of water delivered, which can only be delivered from a house that is adjacent in the graph we defined. Then, by a version of Hall's Theorem, not difficult to derive from the original formulation, the delivery plan we seek exists if and only if for every subset S of U, the total water-need of N(S) meets or exceeds the amount of water available from S.

Suppose that the desired allocation does not exist. Then by Hall's Theorem, there exists some subset S of U such that the water supplied by S exceeds the need of N(S).

We take such an S and iteratively add into S all the unflooded north- and east-neighbors of houses in S. This doesn't increase the size of N(S), but it does increase the amount of water supplied by S, so the resulting modified S is still a witness to the impossibility of our desired allocation.

We repeat this until the union of S and N(S) is upwards-closed. Call the resulting set S'. Since S' supplies more water than N(S') demands, the ratio |S'|/|N(S')| exceeds |U|/|F|.

If S were as in the example above, S' would be the purple-circled set of houses below:



This means that, if we pick a house at random from within the union of S' and N(S'), we are less likely to get a flooded house than if we picked a house uniformly at random from the whole city. This means that, in picking uniformly from the whole city, the (upwards-closed) event of getting a flooded house is negatively correlated with the upwards-closed event of getting a house from the union of S' and N(S')--a contradiction to the generalized Kleitman's Theorem.

We conclude that the desired delivery plan exists, and can be found in polynomial time using known algorithms for bipartite matching.

Not Social Commentary

There's been some unfortunate flooding in Grid City:



The water swept in from the Northeast, so if any house is currently flooded, and it has neighbors to the North or East, it's a safe bet they're flooded too. (Other than this fact, and the grid layout, you should disregard the specifics of the map given.)

The water is low and flooded houses are still livable, but they need tap water. In a show of social cohesion befitting Grid City, each non-flooded household immediately donates 50 gallons of water to the effort. The goal is to distribute this water evenly among the flooded houses, and there is no shortage of volunteers to help. Also, quantities of water can be poured and combined or subdivided with precision.

But water is heavy and, let us say, has to be carried around on foot, so some plan is needed. An ideal of efficiency would be that water is never carried in the South or West directions.

Can both objectives be met simultaneously?

***

In the next post, I'll explain how this puzzle came up and my solution. But I'm curious to hear other approaches first, if you care to try.

Dogs in the Mineshaft

A couple posts ago I described some shenanigans with cats in a binary tree.
But that was just the front yard. The back yard is worse: it contains the opening of an old mineshaft that descends infinitely far into the earth's depths.

Well, there's some funky smell down there that dogs just have to investigate. So, every day, some finite number of dogs may enter or go further down the (unbranching) shaft. They never go back upwards. Here's the scene:



As before, you've got angry owners on your hands. You refuse to close off the shaft (it's too nifty) but again you're willing to try and ensure that any individual dog descends only finitely far into the shaft. Your tool this time: it turns out that after enjoying a good steak, a dog will curl up and fall asleep indefinitely.

The difficulty is that, before eating any steak you give it, the dog may carry it arbitrarily far further down the tunnel. If it passes sleeping dogs, they may be awakened by the steak aroma, and resume their descent.

Money, time, and steaks are no object, and you can outrun the dogs, who won't smell the steaks if they're sealed in your coat pocket. Can you keep your promise to the owners?

To get you started, consider a simple but unsuccessful strategy of giving a steak to every dog every day. The problem is that some dog D may have a sequence of 'accomplice' dogs: every time D falls asleep, a new accomplice will run into the tunnel and hang out above D in the shaft. When you give the accomplice a steak, it'll scamper past D, who'll rouse and go further. In fact, it may happen that every dog goes infinitely far down the tunnel!

Another simple idea is to give a steak every day to the dog furthest down the tunnel, if that dog is not already asleep. This avoids ever waking up sleeping dogs (assuming that the previous day's steak has had its effect; if not we can just wait longer), but it falls victim to a 'rear-guard' attack: a dog that trails constantly just above/behind the current leader.

***

This is a challenging puzzle (unless there's a glitch in the set-up, which I've checked over). But it's well worth thinking about, because the solution strategy--the 'finite injury' or 'priority' method of Friedberg and Muchnik--revolutionized computability theory. Some would say it marked the end of its comprehensibility to outside observers, but I'm optimistic that is not the case. The ingenious strategy is lovely, simple, and, fingers crossed, easier to see in a puzzle setting. I will discuss the solution in a future post, so stay tuned.

Update: Scratch that, Gareth Rees has solved the puzzle and clearly explained the solution for us, in the comments section of 'Trees and Infinity, part III'. I may still talk more in the future about its significance to computability.

Feed Me

A note to readers: I now have an RSS feed, accessible on the right toolbar ('Atom'). When used with appropriate software/sites (I have feeds on my homepage at My Yahoo), this will let you know when I've put up a new post--useful for a blog like this, where posts come strictly at random intervals. As always, I encourage feedback, which will bring more-frequent and more closely-tailored posts.

I try not to do throwaway posts, so how can I salvage this one? Hmm... a puzzle suggests itself:

Modern undergraduate that you are, you're watching bootleg 'Scrubs' episodes on your laptop. This goes on for three hours or so. Meanwhile, your site-feeds page occasionally updates to display someone's new blog post. When your favored blogs post, the content hits your feed within 10 minutes, but the precise delay is nondeterministic--could be 0, 10, or anything in between.

You register the order in which the feed updates come in. Now: is there an efficient method to calculate the number of 'true orders' in which the bloggers could have made their updates?

For example: say updates A, B, C came at 12:30, 12:35, and 12:41 respectively. Then this is consistent with the true-orders ABC, BAC, ACB, but not with, e.g. CAB. Thus the answer here is 3 ways.

Good luck! Does your method work if each individual blogger has their own (known) interval of possible delays?

Clarification: I haven't solved this problem. It might be #P-complete, and the proof of this might be very technical. It seems related to work on counting linear extensions of posets (which is #P-complete in general), discussed by Suresh here.

The 'Sack of Potatoes' Theorem

Tired of packing ham sandwiches for lunch every day? Have some spuds for a change.

You've got a countable collection A_1, A_2, A_3, ... of potatoes. A potato is a convex body of diameter at most 1.

(That is: if p, q are points in a potato P, P also contains the entire line segment between them; furthermore, p, q are at a distance at most 1 from each other.)

Furthermore, most of these spuds are incredibly dinky: the total volume of the entire collection is at most some finite value v, say, 4 cubic inches. You'd really like to eat them all.

Trouble is, mashing or cutting them up beforehand would ruin their freshness. You want to bring them all to work whole in your lunchbox.

Prove that these spuds can be packed into a box of finite dimensions. In fact, such dimensions can be computed solely in terms of v, independent of the precise shape of the potatoes.

***

How to get started on a puzzle like this? One should try to find a sequence of reductions to simplify the problem. So, first, suppose we could do it for rectangular potatoes. Show how to pack a single potato of volume c into a box of volume at most a constant multiple of c, also with bounded diameter. Then, if you can pack these boxes (which have finite total volume), you've packed the potatoes they contain.

I solved the 2-D case, but haven't yet worked on 3-D or n dimensions (where it is also true). I read about this result in a charming volume: The Scottish Book, a collection of research problems (some simple, some still open) compiled by high-caliber, and very imaginative, mathematicians, including Ulam, Banach, and Mazur, who met regularly in the 'Scottish Coffee House', confusingly located in Lwow, Poland, during the '30s. Their book of problems was kept there by the management and notes the prizes--'A bottle of wine', etc.--offered for various solutions. It's definitely worth looking over, both for its diverse contents and for the image of mathematical community it offers.

Trees and Infinity, part III

(Hat tip to Gareth--my first fan art!)

Today, a computability theory-inspired quickie puzzle. Can you face down the infinite in its many guises?

Cats in a Tree

Some GMO-contaminated sludge washed onto your property during the latest freak weather event. A few weeks later, a mysterious tree has sprouted on the lawn, and its progress is astounding--every day, a new layer of binary growth appears:



This would be peachy, but there's a problem: your neighborhood suffers from a plague of cats. Mangy, poorly drawn, tree-climbing cats:



On any given day, some (finite) number of cats may start climbing the tree, or continue their climb from a previous day. What they don't know how to do is come down, not even a single level.
The cats all have irate, protective owners. They want you to cut down this cat sinkhole at once (after rescuing their pets). But you're not going for that--you want the world's largest tree, with unending growth.

Here's the compromise you'd like to offer the owners: a guarantee that every cat C will eventually be prevented from climbing above some level n (which may depend on C).

To achieve this, you have the following means: on any day, you can climb to any number of nodes of the tree and strip the bark there, preventing further growth above the stripped nodes.
Of course, stripping the root node would stop the cats. The challenge, again, is to achieve unending growth as well (though not necessarily the full binary tree).

Good luck!



***

This puzzle models the theorem that there exists an infinite recursive tree with no infinite recursive path. (Interestingly, however, no recursive tree T can have the Halting problem computable with the aid of an arbitrarily chosen infinite path from T. Promise problems are subtle...)

Can the whole theory of computability be 'sweetened up' this way, like the Flintstones vitamins I gobbled up in my youth? Here's a proposal: once students understand programs' capacity to simulate other programs and other computational models, dovetail search procedures, and other 'infrastructural' techniques, it may be preferable to actively 'forget' the computational statement of a problem one aims to prove.
So, in the above puzzle, the cats correspond to different simulated programs in an enumeration, but we are so profoundly unable to predict in advance the behavior of these programs that it might be better to think of the situation adversarially--hence, mischievous cats who do just as they please.
Of course, one could also make a case for the aid to visualization, and possibly generalization, given by the metaphoric puzzle format, but here I mean specifically to ask whether metaphors might help students develop a stronger familiarity with the black-box methodology of computer science.

Next time: the Finite Injury method!

Math for Little People

I'm 22. There's a part of me that's asking: "Why haven't you proved any great theorems yet?" But I can't beat myself up too much over this--with Republicans in the White House, and with so much HBO magic happening lately, the odds are stacked against me.

But there's a different kind of math anxiety creeping up: one of these days, I might have kids. Those kids are going to be curious about the world around them, and they're going to look to me for answers--at least when their mother isn't around.

For the most part, I'll be happy to fend them off with a mix of idle speculation and propaganda. But... what if they ask why honeycombs have six sides?

What if they want to know why scooting towards the middle of the see-saw makes you go up? What if they ask why the rubber chain-links on the swing don't ever come apart, if they're not 'connected'? Could I in good conscience give sloppy answers to questions I know involve beautiful math?

I know the Feds wouldn't come and take them away; I know the kids won't be too disappointed; I know their appetite for rigorous proof will come slowly, if at all. But could I live with myself? No, I've got to get a better grasp of the 'basic facts' of life in our spatial world before I help bring someone new along, if only for my own sake.

But what are these? It's up for grabs, but here's the category I've had in mind mostly: qualitative features of structures, arrangements, and movement, observable by 'medium-sized' agents like children, and generated by/consistent with a naive 'block-world' understanding of matter and physical law (not referring to the AI environment of that name, but in a similar spirit). This is the conceptual space in which I've lived most of my life (and thought about discrete math and computer science), and if it's good enough for me it's good enough for my kids. Molecules and lightning bolts I won't sweat so much, but Block World I want to get right.

So then... how to pick out, think about, and explain its most important facts?

Some of them are, I think, topological, as I've alluded with the swing example. But kids won't swallow homotopy theory any more than they'll eat lima beans, even if I can still remember it by then. Anyways, there's a potential save here: Block World is basically discrete, so the space of 'topological' deformations of objects is much smaller and more well-behaved (I've already posted on discretization in topology).

A good place to start would be the Jordan Curve Theorem, famed for its difficulty in spite of its surface obviousness: what could be clearer than the fact that a non-self-intersecting loop in the plane divides the plane into two components, 'inside' and 'outside'?

As one discrete formulation, consider the loop as a path on the grid, where each step in any direction is of even length. Then it appears that the inside is path-connected, also by grid paths (without the even-length restriction), and separated from the outside. For example:



I think this problem is excellent fodder for thought, and I would encourage anyone who's been scared away by the Theorem in the past to work on it in this friendlier setting.

No hints, though--would your kids respect you?

(Clarification for concerned parties: there are no children on the horizon; I do believe in responsible parenting; and I don't get HBO, although I do swear by Curb Your Enthusiasm.)

The Vulcan in Me

Readers, here is a puzzle adventure in naive physics and topology. The author respectfully denies being a Trekkie. Enjoy!

***

I graduated last in my class at Starfleet Academy. Not much of a story, so don't ask. Anyway, you probably know what came next: it was either find a civilian job or go guard some worthless corner of deep space.

But I'm not exactly sociable, so I took the assignment with no hesitation. Sure enough, it was a real plum: I was put in charge of two monitoring stations (practically bathroom-sized, one of which I controlled remotely) orbiting neighboring stars, with nothing else even close.

For two years, there was nothing but silence as I idled there, chuckling at my fate and deepening my acquaintance with some bootlegged Romulan ale. Then, finally, something happened. I got an alert:

"Reports of extremely massive unidentified vessel, may be in your sensor range. Report: are gravitational readings consistent with null hypothesis (no vessel)?"

I almost panicked. I hadn't checked the sensors in ages, and I didn't even begin to remember how to interpret the readings--how did gravity work again? If I asked I'd definitely be canned. I fumbled through my old Academy lecture notes, struggling to penetrate the chicken-scratch handwriting and the alien sex doodles everywhere. Here is what I was able to recover:

1) Newton's laws govern the universe; quantum mechanics and other such exotic junk were conclusively disproved in 2247.

2) The world contains massive point-particles; the gravitational field at a point in space is the vector sum of its gravitational attractions to all point-masses. Beyond a critical range and below a critical mass, these attractions can be assumed zero. (so I could discard the mass of myself, the two monitoring stations, and everything beyond the two stars and, maybe, this weird vessel... all of which I could model as point-masses.)

3) The gravitational attraction v to a mass m felt by a point p in space is a vector pointing from p in the direction of m, with magnitude w*f(d), where w is the mass of m, d is the distance from p to m, and f is a function given by...

...but I couldn't make out the formula for f; it was totally obscured by a lascivious Ferengi.

Still, I'm not as thick as you think. I reasoned that this much is true:

4) f, the function governing the magnitude of the attraction, must be continuous, positive, and decreasing on the positive real numbers, tending to infinity as d goes to zero, and tending to zero as d approaches infinity. That is, it looks something like this:



Now, the readings from my two stations looked something like this:



(s[1], s[2] are the two stations, and v[1], v[2] are the two gravitational field readings.)

The picture's not much to go by--the vectors didn't all lie in a plane together, and I can't swear by the magnitudes I drew. The thing to notice is that a, b were obtuse--of that I'm sure.

Recall that there were definitely two stars kicking around in the vicinity. Don't ask me how massive they are; it was on record somewhere, but I was too frazzled to even look up the numbers. Also, my windows were frosted over and I had no way of getting a bead on the stars' position. The question was, could some placement of those two masses have generated the gravitational field readings?

What can I say... I may be lazy, but I'm also one-eighth Vulcan, and my genes chose that do-or-die moment to kick in. I confidently delivered my report: "Readings consistent with null hypothesis."


Well, they never found that vessel; still, doing my duty with flair like that was a high point for me, despite my usual tendency to shirk. But two more years have passed, and all this booze has given the Vulcan in me a sore beating.

So help me remember--how the hell did I know what to say?

More Parity Puzzles

...because I'm odd that way. Both are in the same 'can-do' spirit of the last one, yet neither use quite the same techniques; still simple.
Guaranteed correct, 'cause they're not mine, but lifted from the problem sets I'll credit.

1. Two delegations A and B, with the same number of delegates, arrived at a conference. Some of the delegates knew each other already. Prove that there is a non-empty subset A' of A such that either each member in B knew an odd number of members from A', or each member of B knew an even number of members from A'.

2. Given a finite set X of positive integers and a subset A of X, there exists a subset B of X, such that A are precisely the elements of X that divide by an odd number of elements of B.

(Hint: not a number theory puzzle.)


First is from the 1996 Kurschak Competition (Hungarian), via the Kalva site (see sidebar). Second is from the book '102 Combinatorial Problems' by Andreescu and Feng. Enjoy!