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?

The trivial but wrong way is to go for 1 unit in some direction, then trace the circumference of a unit-radius circle. The road will surely be found this way, but the path length is \(1+2\pi\), which can be improved upon.

Every possible position for the road corresponds to a tangent line to the unit circle centered at the starting location. Therefore, this is a problem about finding a shortest path that touches all tangent lines to a unit circle. To make this more concrete, let us transform the space into polar form as below.

We see that in polar form, the unit circle becomes the line \(r=1\) and each tangent line touching the circle at angle \(\theta_0\) becomes the graph \(r=\sec(\theta-\theta_0)\). The trivial solution corresponds to a path that traces \(r=0\) to \(r=1\) at \(\theta=0\), followed by \(\theta=0\) to \(\theta=2\pi\) at \(r=1\). This is not efficient.

In fact, any continuous path starting at \(r=0\) “reaches the road” (i.e. touches every tangent line) as long as it touches \(r=\sec(\theta)\) somewhere on \(\theta\in [0,\pi/2)\) and somewhere on \(\theta\in (3\pi/2,2\pi]\), and it stays above \(r=1\) between those two points. And up to shifts in \(\theta\), these are the only possible solutions.* Note that the path doesn’t need to be closed, like the trivial path was. So we are left to find the shortest such path (e.g. the one in green above).

Whereas in rectangular form, the shortest path between two points is a straight line, in polar form, the shortest path between two points is along a secant graph. It is a fairly easy matter to show that the shortest path must take the following form:

1. Start from \((r,\theta)=(0,\phi)\) for some \(\phi\in [0,\pi/2)\);
2. Drop onto the graph \(r=\sec(\theta-2\phi)\), between the points \((r,\theta)=(\sec(\phi),\phi)\) and \((r,\theta)=(1,2\phi)\);
3. Take the path \(r=1\) from \(\theta=2\phi\) to some \(\theta=2\pi-2\psi\);
4. Drop onto the graph \(r=\sec(\theta-(2\pi-2\psi))\), between the points \((r,\theta)=(1,2\pi-2\psi)\) and \((r,\theta)=(\sec(2\pi-\psi),2\pi-\psi)\).

Finally, we need to solve two minimizations, which will find the best \(\phi\) and \(\psi\). \(\psi\) can actually be solved by inspection, but formally:

\(\min_{\phi\in[0,\pi/2)} \sec(\phi) + \tan(\phi) + \pi - 2\phi\)
solution at \(\frac{\sin(\phi)}{\cos^2(\phi)} + \sec^2(\phi) = 2 \Rightarrow \sin(\phi)=1/2 \Rightarrow \phi=\pi/6\).

The solved path has total length \(\tan(\pi/4) + \pi – \pi/2 + \sec(\pi/6) + \tan(\pi/6) + \pi – \pi/3 = 1+\sqrt{3}+7\pi/6\), and is plotted below. This is about 12% shorter than the trivial path.

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.

First, some examples.

Clearly, \(n=2\) is impossible to label.

For \(n=\binom{k}{2}\) for some \(k\) (call these binomial numbers), the number of trips between A and B is no larger than 2. Here is how. At point A, partition the \(n\) wires into groups \(P_1,P_2,P_3,…,P_k\) of \(1,2,3,…,k\) wires each and tie the wires in each group together. Go to point B and recover the partition set memberships by measuring continuity between pairs of wires. (Thus A has communicated set membership to B.) Now based on this side information, repartition the wires at B into groups \(Q_1,Q_2,Q_3,…,Q_k\) again of \(1,2,3,…,k\) wires each, but do this by taking 1 wire each from \(P_1,P_2,…,P_k\) to form \(Q_k\), take 1 wire each from \(P_2,P_3,…,P_k\) to form \(Q_{k-1}\), and so on. Go back to point A, undo all the original ties, and recover the new partitions. The membership pair \((P_i,Q_j)\) uniquely identifies a wire so all wires are fully labeled at both A and B. This establishes the main ideas of this class of partitioning solutions. It is also easy to see that at least 2 trips need to be made for any \(n>1\) since sets of the same size and wires within one set cannot be distinguishable without other information.

For \(n\) that are sums of unique binomial numbers (call these doubly binomial numbers), a two-phase procedure can label the wires in no more than 3 trips. The first phase is to partition the wires into clusters of unique binomial number sizes \(b_1,b_2,…,b_l\). Go to point B and identify the clusters by the unique sizes of the continuity sets. Then follow the previous technique to identify the wires within each cluster. And, you can generalize this by further nesting so you get 4 trips for \(n\) that are sums of unique doubly binomial numbers i.e. triply binomial numbers, 5 trips for quadruply binomial numbers, etc.

In essence, this is a generalization of binary partitioning to partitioning into many sets, and more sophisticated partition based codes can probably be found for all \(n\) on a case-by-case basis, however, these are not always optimal. For one, the multi-phase procedure is arbitrary and probably inefficient. And other kinds of coding that wipes away received information in the wire configuration in order to send new information (even if some information remains undecoded, e.g. sets of the same size yet to be distinguished) lose efficiency.

The better solution that solves the problem in the optimal 2 trips (A to B to A) uses clever feedback in the coding. The idea is based on the fact that if you chain all wire segments together in series (like Christmas lights), then the location of any single break in the chain can be determined by measuring continuity from one terminus. Here it is:

So suppose \(n\) is odd. At point A, arbitrarily label 1 wire to be “the left terminus” or node 0. Tie the remaining wires into \((n-1)/2\) pairs. Go to point B. By the coding at A, the single wire and collection of wire pairs can be distinguished. So node 0 at B is established. Then arbitrarily choose a pair and a node in the pair, and connect it to node 0. This becomes node 1, the remaining node of the pair becomes node 2. Choose another pair and a node in the pair and connect it to node 2, this becomes node 3 and the other of the pair node 4, and so on, until all wire segments are connected in series. This configuration becomes the feedback information. Go back to point A. Now we use the feedback to search for all nodes from 1 to \(n-1\). This is easy to do: just make a cut at any connection at A and measure continuity between node 0 and all other nodes. Say there are some s nodes that read short circuit and the rest open circuit. Then immediately it is known that the cut is between nodes \(s\) and \(s+1\). This can be repeated at all cuts so all nodes are labeled.

Suppose \(n>2\) is even. Then arbitrarily choose two wires to be the termini. Connect the remaining into pairs. Go to B and identify the two single wires. Choose one to be the left terminus, i.e. node 0 and the other one the right terminus, i.e. node \(n-1\). Then follow the previous connection procedure for the odd number of n-1 nodes not including node \(n-1\). Go back to A and identify the right terminus as the only one of two single wires that is open circuit with all other nodes; that gets labeled node \(n-1\). Then remove it from consideration. The other single wire is labeled node 0, and the same procedure is applied as previously to label the remaining nodes.