That's a Wrap

I had some gift-giving duties to attend to today... halfway into the wrapping phase, my mind wandered in a predictable direction:

Given a set of rectangular box dimensions, what is the smallest amount of paper that will wrap the box?

One would assume we want to cut out a rectangle of wrapping paper, since otherwise we get annoying scraps (and also the problem is mathematically trivial if we can cut a cross-type shape).

I haven't had any time to toy with this problem, but I had a feeling one particular MIT dude might have... and I was right. True to form, Erik Demaine delivers a whole page about various wrapping problems he's explored with colleagues.

To anyone reading who teaches a programming course, I would suggest that a fun algorithms assignment could be spun out problems of the above type. If the program outputted folding instructions too, so much the better.

Happy holidays, all!

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?).

Quick Links

First, a plug: Aaron Roth, a grad student at CMU is keeping up a cool, informative TCS blog that deserves to be on the map. Check it out, especially if you want an insider's perspective on the rapidly growing area broadly referred to as 'algorithmic game theory'.


Bill Gasarch has been posting a number of nice puzzles lately. A couple have served as direct illustrations of ideas I've tried to exposit here, so I thought I'd point to them as follow-ups. In both cases I tried to describe the connection within the comments section.

1) For readers who followed my two posts on statistical distance, Bill gave a CS puzzle (about the possibility of 'zero-knowledge distributed consensus') that is exemplary for the use of reasoning about distance between distributions.

2) Bill described variants on Van der Waerden's Theorem, one of the classic results that presaged ideas of Ramsey Theory. He asked about the relation between Van der Waerden's Theorem for the natural numbers and its immediate extension to the real numbers. In particular, is the latter simpler? In the comments, I describe how the idea of compactness in logic, exposited here a while back, can be used to derive VDW's theorem from its real-number version.

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.