How to get a better proof

Question

Given a string $S$ which is a representation of a number in base $2$ i.e. a string of 0s and 1s, we need to find out the maximum possible value obtainable by erasing exactly one digit. The string's most significant digit is 1. This means $S$ represents a number greater than $0$.

I have a proof. If there is a more short and sweet proof please post it.

Let $S = aXYb$ where, $X$, $Y$ are single digits and $a$, $b$ are the bits to left of $X$ and to right of $Y$ respectively.

Then two important observations.

a. If $X$ = $Y$, we will obtain the same value aXb whether we remove X or Y.

b. We can then represent String S as a sequence of alternating groups of 1's and 0's i.e.

1. $S = 11..100...011..100...0$, if $S$ ends in zero

2. $S = 11..100...011..1$, if $S$ ends in one.

Within each group of 1's or 0's, we can remove any of digits of the same digit group and obtain same final value as obtained from observation above. Now, if $N = length(S)$, then our result is of length $N - 1$. We proceed fromthe $(N-1)$th bit(MSB) to the 1st bit(LSB) of resultant string and see if we can set the $i^{th}$ bit. We can have MSB of final result as 1 as the MSB of $S$ is 1. Using similar logic, we won't remove any of digits from the leftmost 1 digit group of $S$. Now consider the next digit of resultant string. We can place a 1 there only if the leftmost 0s group of $S$ is of length 1 since we can remove only one digit. Otherwise, we we will have the bit set to 0. To see that, we can write $S$ as $S = 1...10..01X$. To obtain maximum value, it is easy to see that we need to bring 1 (adjacent to X) to the left. Thus we need to remove a 0 from the lefmost 0 group.

I want to improve my discrete mathematics thinking. Thank you.

Answer 1

It’s essentially the same argument, but presented a bit more elegantly.

Suppose that the bit string is $\sigma=1b_1b_2\ldots b_n$. For $k=1,\ldots,n$ let $\sigma_k$ be the bit string that remains when $b_k$ is deleted, and let $\lambda_k$ be the substring of $\sigma$ to the left of $b_k$.

• If $b_k=b_{k+1}$, clearly $\sigma_k=\sigma_{k+1}$.

• If $b_k=0$, $b_{k+1}=1$, and $k<\ell$, the first $k+1$ bits of $\sigma_k$ are $\lambda_k1$, while the first $k+1$ bits of $\sigma_\ell$ are $\lambda_k0$, so $\sigma_k>\sigma_\ell$, where the order may be thought of either as lexicographic order or as the ordinary numerical order of the integers represented in binary by the bit strings.

• Similarly, if $b_k=1$, $b_{k+1}=0$, and $k<\ell$, the first $k+1$ bits of $\sigma_k$ are $\lambda_k0$, while the first $k+1$ bits of $\sigma_\ell$ are $\lambda_k1$, so $\sigma_k<\sigma_\ell$.

Clearly if all bits of $\sigma$ are $1$, it makes no difference which we remove. Now suppose that $\sigma$ has a zero bit, and let $b_k$ be the leftmost zero bit. The first two points combined show that $\sigma_k\ge\sigma_\ell$ for all $\ell>k$, and the third shows that $\sigma_k>\sigma_\ell$ for all $\ell<k$, so removing the first zero maximizes the resulting string.