Salvaging a damaged cable

580 Views Asked by At

Let's say we have a cable of unit length, which is damaged at one unknown point, the location of which is uniformly distributed. You are allowed to cut the cable at any point, and after a cut, you'd know which piece is damaged and which is not. You can do this as many times as you want, and you want to maximize the expected length of the biggest undamaged piece after all the cutting. What is the best you can do? The strategy need not be deterministic.

I currently have a lower bound of $\frac12$ and upper bound of $\frac34$. The lower bound comes from just cutting the cable in half once.

For the upper bound, notice that if the fault is at $\frac12 \pm x$, then you cannot do better than $\frac12 +x$. So taking the expected value, $$ \int_0^{\frac12} \left(\frac12+x\right)2 dx = \frac34$$

I initially thought that an optimal strategy would have to be applied recursively to the damaged piece, but now I'm no longer convinced of this. If you've already obtained an undamaged piece of length $l$, then there is no point in cutting a damaged piece into two pieces of length $\leq l$.

Any reference to an existing treatment is also welcome.

4

There are 4 best solutions below

3
On BEST ANSWER

An "algorithm" (though it might possibly run indefinitely, depending on our strategy) necessarily goes like this

Step 0. Let $k\leftarrow1$.

Step 1. [Now we have $k$ parts of cable, i.e. subintervals of $[0,1]$, exactly one of which is defective] If the defective part is strictly longer than all good parts, go to step 2. Otherwise there exists some good part at least as long as the defective part and further subdivisions cannot improve the result; pick a longest good part as result and terminate.

Step 2. [Now the defective part $[a,b]$ is strictly longer than all other parts] Pick a suitable point of cutting the defective part, i.e. pick some $x_k\in(a,b)$, thus replacing $[a,b]$ with $[a,x_k]$ and $[x_k,b]$. [The probability that $x_k$ equals the point of defect is zero and can be ignored] Let $k\leftarrow k+1$ and go to step 1.

Thus a strategy consists of a sequence of cutting points $x_i\in[0,1]$ for all $i\in N$ with $N=\mathbb N$ or $N=\{1,2,\ldots n\}$ (i.e. the sequence might be finite or infinte). We may assume wlog. that $N$ is not unnecessary big, i.e. if step 2 will never be entered with some value $k$, no matter where the actual defect is in the cable, we can as well assume that $N\subseteq\{1,\ldots,k-1\}$. In other words, if $k\in N$, then there exists a point $x\in[0,1]$ such that a defect at $x$ will make the algorithm above make use of the cutting point $x_k$.

By symmetry, we may assume in step 2 that $$\tag1x_k-a\ge b-x_k,$$ i.e. the new left part is always at least as long as the new right part. Then we can show by induction, that the interval $[a,b]$ in step 2 is always $[0,x_{k-1}]$ (formally letting $x_0=1$). In fact this is trivially true when $k=1$. If the claim is true for some $k$, then in step 2 interval $[0,x_{k-1}]$ is divided into $[0,x_k]$ and $[x_k,x_{k-1}]$. By $(1)$ the interval $[0,x_k]$ is at least as long as $[x_k,x_{k-1}]$ (i.e. after $k\leftarrow k+1$, interval $[0,x_{k-1}]$ is at least as long as $[x_{k-1},x_{k-2}]$). Thus in step 1, we either terminate or continue with step 2 and $[a,b]=[0,x_{k-1}]$ as was to be shown.

In other words, the sequence $(x_i)_{i\in N}$ is strictly decreasing and more precisely $$\tag2 \frac {x_{k-1}}2\le x_k<x_{k-1}\qquad\text{for all }k\in N.$$ As the sequence is also bounded from below, $L:=\max\{\,x_{k-1}-x_{k}\mid k\in N\,\}$ exists. Note that we may assume $x_k\ge L$ for all $k\in N$ as otherwise by $(2)$ neither of the pieces $[0,x_k]$ or $[x_k,x_{k-1}]$ can be an improvement over $L$.

Let $f(x)$ denote the length of longest good cable obtained by employing the strategy $(x_n)_{n\in N}$ if the actual point of defect is at $x\in[0,1]$. If $x_k< x< x_{k-1}$ for some $k\in N$, then we will stop after performing the cut at $x_k$ and the longest part will be $[0,x_k]$, so $f(x)=x_k$ for $x\in(x_k,x_{k-1})$. If $x<x_k$ for all $k\in N$, then $f(x)=L$. The expected length is simply $\int_0^1f(x)\,\mathrm dx$. The graph of $f$ is bounded from above by the diagonal, except for the triangle on the lower left with vertices $(0,0) (0,L), (L,L)$. On the other hand, a triangle of the same size is "missing" over an interval $[x_k,x_{k-1}]$ with $x_{k-1}-x_k=L$. Proof without words of <span class=$(3)$ for an example function $f$" />

We conclude that $$\tag3 \int_0^1f(x)\,\mathrm dx\le \int_0^1x\,\mathrm dx=\frac12.$$

The estimate $(3)$ also applies to mixed strategies (i.e. a strategy $(x_n)_{n\in N}$ is picked randomly according to some distribution). On the other hand, inequality $(3)$ is strict: A strategy that does indeed lead to $\frac12$ as expected value is given by $N=\{1\}$, $x_1=\frac12$ (as already noted by the OP).

4
On

I believe that the maximum possible expected good cable length (K) is .5.

The first cut at location $x$ will yield a K of $1-x$ with a probability of $x$ and otherwise a $x$ long piece which will be a minimum K you will have no matter what you do in subsequent steps.

If you have the shorter good piece and the damaged long piece, you might as well cut of infinitesimally small parts of the damaged piece as you already have a good piece of minimum length $x$. If the damaged portion gets shorter than $x$, there is no point continuing as it will be shorter than piece you are already holding. This infinitesimal cutting stage will yield an average size of:

$$\int_x^{1-x}(1-t)dt = 1/2-x$$

This means that: $$K=x(1-x)+x^2+1/2-x$$ $$K=x-x^2+x^2+1/2-x$$ $$K=1/2$$

No matter what x you pick (even infinitely small) K=.5.

I cannot determine another method that would have an expected K value greater then 1/2.

2
On

Suppose the best strategy is to cut at point $p$ and this gives you an optimum expected length of $q$. wlog we can choose $p\ge 0.5$ (measure from the other end).

Consider the situation after $1$ cut. With probability $1-p$ (the probability that the fault is in the shorter piece) we have a good piece of length $p$.

If the fault is in the longer piece, (probability $p$ - thanks to @AndrewPoelstra for the correction here), we have an expected value at least $qp$ from the longer piece (the difficult bit is to factor in those cases where the longest piece at the end of all the cutting is the shorter piece at the first cut). So we have $$q\ge (1-p)p+p^2q$$ so that $$q\ge \frac{(1-p)p}{1-p^2}=\frac {p}{1+p}$$

This gives a value for the salami-slicing strategy of at most $0.5$, which is the same as the "cut in half" strategy. Note that with salami-slicing the short bits are negligible in size and don't affect the calculation.

When $p=\cfrac12$ we have $q\ge \cfrac 13$ - in fact we know that the influence of the "shortest piece" brings this up to $q=\cfrac 12$. So this is inconclusive, but instructive.


Note that the first version of this was carelessly incorrect - I've left it up now as an example of where a simple argument gets us. There will be better approaches.

0
On

A strategy consists of snipping off pieces of length $\ell_1,\ell_2,\ldots$, subject to the condition $\ell_1+\ell_2+\cdots = 1-M$, where $M=\max\{\ell_1,\ell_2,\ldots\}$, and stopping if and when the cut-off piece is found to contain the bad spot. The probability that the bad spot lies in the $i$th snippet is $\ell_i$, and the probability it lies in none of them is $M$. Therefore the expected longest piece when the process ends is

$$\ell_1(\ell_2+\ell_3+\cdots+M)+\ell_2(\ell_3+\ell_4+\cdots+M)+\cdots+M^2$$

It's easy to see that this sum is unchanged if any $\ell_i$ and $\ell_{i+1}$ are interchanged:

$$\begin{align} &\cdots+\ell_{i-1}(\ell_i+\ell_{i+1}+\ell_{i+2}+\cdots+M)+\ell_i(\ell_{i+1}+\ell_{i+2}+\cdots+M)+\ell_{i+1}(\ell_{i+2}+\cdots+M)+\cdots\\ &=+\ell_{i-1}(\ell_{i+1}+\ell_i+\ell_{i+2}+\cdots+M)+\ell_{i+1}(\ell_i+\ell_{i+2}+\cdots+M)+\ell_i(\ell_{i+2}+\cdots+M)+\cdots\\ \end{align}$$

Consequently, any strategy is equivalent to one in which $\ell_1\ge\ell_2\ge\ell_3\ge\cdots$, for which $M=\ell_1$. But this leaves us in the case that kaine earlier analyzed: As soon as you are guaranteed a piece of length $M$ and plan to make all subsequent cuts no longer than $M$, you can only improve the final result by making the subsequent cuts infinitesimally short. So the best you can get, as kaine showed, is an expected value of $1/2$.