First, the package — let’s call it ‘somecrap’ — contained a post-installation configuration. Linux has this terminal pseudo-GUI used sometimes for configuration of packages. You may have seen it, it looks like ASCII art. Unfortunately it’s so brittle that when you Ctrl-Z out of it there is no way to get it back. So I had to just Ctrl-C out of it. Turns out the process that runs it (‘whiptail’) is stuck using 100% of CPU. So that’s fine, it too can be killed, but how to get a configuration do-over? The package thinks it’s already configured — and indeed, wrote out a default configuration file. There is no way to get a redo short of removing and reinstalling the package. Right? And that’s where the real problem starts.

The package uses ‘dbconfig-common’. When you remove the package, the database modifications are not reverted (understandable), but the database configuration file ‘/etc/dbconfig-common/somecrap.conf’ that was generated by this pseudo-GUI was also not removed. When you remove and reinstall the package, it refuses to reconfigure that file, probably because dbconfig-common thinks everything is already configured! So then I just deleted ‘somecrap.conf’, in the quite natural belief that the package will then rerun the configuration to generate it, like on a fresh install.

Turns out no. Every installation gives

dbconfig-common: writing config to /etc/dbconfig-common/somecrap.conf
Not replacing deleted config file /etc/dbconfig-common/somecrap.conf
unable to read input file /etc/dbconfig-common/somecrap.conf

And the configuration fails. It’s really unbelievable how fatuous ‘dbconfig-common’ is here. Somewhere it’s tracking that ‘somecrap.conf’ is supposed to exist, instead of determining whether it actually does, from the ground truth.

All the ideas about removing, purging packages, reinstalling are not going to help here. The thing that worked was to reinstall dbconfig-common, to get it to fix itself:

apt-get install –reinstall dbconfig-common

debconf then screeches about ‘possible database corruption’ and ‘adding back missing question’ w.r.t. ‘dbconfig-common’. Reinstalling ‘somecrap’ at this point finally brings back the original pseudo-GUI configuration process.

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?

By the pigeonhole principle, we have two extremes: from \(n=0\) to \(n=t-1\) samples, it is impossible to collect \(t\) coupon types; and for \(n>(t-1)d\) samples, it is impossible not to. For number of samples in between, there is some monotonically decreasing probability that \(t\) or more types are not collected. Let’s call the latter probability \(P(n)\). The expected number of samples it takes to collect \(t\) types is then

Finding \(P(n)\) for \(n\ge t\) doesn’t appear easy, though the combinatorics could be written down (in theory), maybe involving partition functions, Stirling numbers, or whatever. But the question is reduced to the following, which somebody must have solved: given a \(d \times k\) 0-1 matrix, in which \(n\) 1′s are placed randomly, what is the probability that exactly \(z\) columns are 0-weight (have 0 column sums)?

These papers give some approximations:

http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.1480v3.pdf

http://cs.anu.edu.au/~bdm/papers/irregular.pdf

Does anybody know the actual answer?

xxx-xxx-3910

“This is a collect call from [buzz buzz, anytime]“.

Three surgeons (A, B, C) participate in an operation involving three patients (a, b, c). For simplicity, each surgeon operates with just one hand, and operates just once on each patient. There are a bunch of sterile surgical gloves that stop contamination from one side to the other. What’s the minimum number of gloves needed to ensure that no body part ever comes into contact with another, even indirectly? Note, surgeons do not want to contaminate each other either.

Clearly, the upper bound is 9, for the 9 pairings. The lower bound is 3, for the 3 patients, or alternatively the 3 surgeons. Is the answer something in between?

Here’s a hint, they are allowed to wear multiple gloves or flip them inside out or do any such thing as needed.

It turns out 3 is not sufficient, but 4 is. There are many ways to achieve 4. Here is one:

First label the 4 gloves 1, 2, 3, 4. The notation “X-m-n-y” indicates surgeon X wears glove n outside glove m and operates on patient y.

A-1-3-c
A-1-2-b
A-1-a
B-4-3-c
B-4-2-b
B-4-1-a
C-3-c
C-3-2-b
C-3-1-a

But no matter how you try, 3 is not possible. You are always short by 1 or 2 sterile surfaces, depending on how you count. And this counting argument lies behind the following proof that 3 is not sufficient. The proof is rather short:

First, two facts.

1. Clearly, once a sterile surface is used by a surgeon or patient, it cannot come into contact with somebody else, so each surface is somehow “assigned” to a specific person.
2. After all the operations involving that person is finished, only then can that person’s assigned surface be contaminated

So, suppose 3 were sufficient. Then, there are 6 persons in total, and 6 sterile surfaces initially. That means there can be no sterile-to-used surface contact until all 6 surfaces are assigned, or there would be a shortage.

There are three types of operations, one type involves contaminating sterile surfaces by direct use, let’s call this an “allocation” operation; a second type involves already contaminated surfaces cross-contaminating each other, let’s call this a “contamination” operation; a third type reuses already contaminated surfaces but in a different yet contact-compatible combination, without introducing additional contamination, let’s call this a “reuse” operation.

There can be at most 5 “allocation” operations to allocate the 6 sterile surfaces to the 6 persons. (The first operation necessarily contaiminates 2 sterile surfaces.)

There can be at most 1 “reuse” operation. This is due to a kind of parity constraint. 4 surfaces have to already be allocated, with 2 sterile surfaces left for this operation.

Now there are 9 operations in total, so there are at least 3 more to go. These remaining operations are “contamination” operations. That means any operation involving surgeons or patients associated with any of the contaminating “inside” glove surfaces must not occur again.

Now, without loss of generality, suppose the glove surface assignments are

A-1-a
B-2-b
C-3-c

(It has to be surgeon on one side, patient on the other, because any other way is necessarily more wasteful.) Now note that any 2 operations involves at least 3 distinct people, and simultaneously “disable” the 3 other sides of the gloves (and the associated people) from further operations. Further, for any 3 people, there can be at most 2 operations between them. That means we can only perform 2 “contamination” operations. As an example, the two operations A-1-2-b, A-1-3-c forbids a, B, and C from being in any further operations. That leaves A, b, c, but between them, there are only the two pairs that have already occurred (A-b and A-c).

Since there is 1 of the 9 operations that cannot be performed in safe conditions, that’s a contradiction. Q.E.D.

Now only if this can be generalized to larger numbers of patients and surgeons. One key number series in making bounds is the least number of distinct people that must be involved for \(N\) operations. We know that a full bipartite graph between \(n\) nodes and \(k\) nodes has \(n \times k\) edges, so \(N\) operations will involve at least about \(2\sqrt{N}\) people. The problem is this approximate lower bound grows too slowly and becomes loose for larger numbers of pairings so that doesn’t guarantee as simple a proof for those cases. So maybe another day for the generalization.