Hello everybody! The above problem you see is a combinatorics problem I could not solve. :( The answers are $00110111, 000111011011$ and $001111011101011$. This is problem $4$ from ZIO $2011$.
Notice that the last column (the given column) is just a rearrangement of the numbers of the original number (but we don't know in which order). It can also be observed that since in the first sub-case, sometimes the 1's are after the 0's, it must be that the rest of the piece of the number must be lexicographically "more" than the next one??? Also, there are $\frac{8!}{5!3!} = \frac{6 \times 7 \times 8 \times 9}{6} = 504$ such numbers which is too difficult to brute force on a pen and paper test.
Any help would be much appreciated. Thanks!
I'll walk you through the (a) problem, the other parts can be done with the same method.
What we are doing is to reconstruct the sorted array, column by column. We have the last column already given, the construct column 1, then column 2, a.s.o.
Each column in the initial array is a permutation of the original binary sequence, so sorting the rows doesn't change that (it just permutates it some more). So we know in problem (a), that the sequence consists of exactly $3$ zeros and $5$ ones. So the first column of the sorted array also consists of $3$ zeros and $5$ ones.
But since it is the sorted array, and sorting starts from the beginning = most significant bit, we know that the first column has $3$ zeros on top and $5$ ones at the bottom:
So this is what we know about the sorted array, with columns 2-7 still unknown: $$ \left( \begin{matrix} 0 & ? & \ldots & 1\\ 0 & ? & \ldots & 0\\ 0 & ? & \ldots & 1\\ 1 & ? & \ldots & 1\\ 1 & ? & \ldots & 1\\ 1 & ? & \ldots & 1\\ 1 & ? & \ldots & 0\\ 1 & ? & \ldots & 0\\ \end{matrix} \right) $$
Now if you look at the picture of the initial array given in the problem description, you see that in each row the element in the first column is the one that comes in the sequence after the element in the last column (in row $2$, the element in the last column is $b_1$ and the element in the first column is $b_2$, a.s.o.) The only exception is in row $1$, where the last column contains $b_N$ and the first column contains $b_1$.
But since we are rotating the binary sequence anyway all the way around, we can just consider $b_1$ to be the element coming after $b_N$ and consider the binary sequence on a circle with no real start and end. That's the reason why the problem wants you to find the first row of the sorted array, and not of the initial array: After sorting, you get the same sorted array if you started with the sequence $100$ or $010$ or $001$, so can't distinguish between them any more.
So from the above partial sorted array, we know from the first row that the sequence has a $1$ followed by a $0$, from the second row we learn that there is a $0$ followed by a $0$,a.s.o. From rows $4-6$ we learn that there are 3 ones that are followed by a one. And since each column is a permutation of the initial sequence, it means we have 3 different ones followed by a one.
Looking at the partial sorted array, we see that we have as part of the sequence (on the circle)
$$2\times "10", 1\times "00", 3\times "11" \text{ and } 2\times "01"$$
Of course, the first element of each such 2-element subsequence appears exactly once in column $1$ in the sorted array. And because it is the sorted array, we know that the one $00$ subsequence will be first, follow by the two $"01"$ sequences, a.s.o.
This means we have determined the $2$nd column of the sorted array:
$$ \left( \begin{matrix} 0 & 0 & ? & \ldots & 1\\ 0 & 1 & ? & \ldots & 0\\ 0 & 1 & ? & \ldots & 1\\ 1 & 0 & ? & \ldots & 1\\ 1 & 0 & ? & \ldots & 1\\ 1 & 1 & ? & \ldots & 1\\ 1 & 1 & ? & \ldots & 0\\ 1 & 1 & ? & \ldots & 0\\ \end{matrix} \right) $$
And now we continue this algorithm for the next, the $3$rd column. We know that the eight $3$-element subsequences are
$$1\times "100", 1\times "001", 1\times "101", 2\times "110", 1\times "111", 2\times "011"$$
and thus can fill in the $3$rd column of the sorted array:
$$ \left( \begin{matrix} 0 & 0 & 1 & ? & \ldots & 1\\ 0 & 1 & 1 & ? & \ldots & 0\\ 0 & 1 & 1 & ? & \ldots & 1\\ 1 & 0 & 0 & ? & \ldots & 1\\ 1 & 0 & 1 & ? & \ldots & 1\\ 1 & 1 & 0 & ? & \ldots & 1\\ 1 & 1 & 0 & ? & \ldots & 0\\ 1 & 1 & 1 & ? & \ldots & 0\\ \end{matrix} \right) $$
I think now the process should be clear. You have to look at the 8 created $4$-element subsequences and sort them into the sorted array, creating the $4$-th column, a.s.o. I'll just show the final complete sorted array now:
$$ \left( \begin{matrix} 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ \end{matrix} \right) $$
This shows the top row of the sorted array is $00110111$, just as the given solution shows.
In practice, once you have 'enough' columns, you may be able to reconstruct the sequence by trial and error, as a given subsequence may only be continued in one way for many subsequences. But doing the above algorithm always works.