What is the most efficient way to open glass curtains This question originated from a real life problem. It has to do with a
certain system of sliding glass panels used to close a
terrace. Describing exactly how it works would take a long time, so
here is a youtube video showing the concept:
https://www.youtube.com/watch?v=QMvF3TcPUDA
(Disclaimer: I am in no way associated with the company marketing the
product advertised in this video)
As the video shows, the person has to slide each glass panel to the
right hand side of the balcony before being able to rotate it, thus
getting it out of the way. Observe that the rotation can only take
place when the panel is at the right hand side due to a single slot in
the top railing.
In order to state my question it is best to imagine a set of glass
panels covering a single side of a very long terrace, rather than the
one in the video, where two perpendicular sides are involved.
In the video, the person opens the glass panels one by one, having to
walk further and further in order to bring the next panel towards the
rotating position. This is obviously not the most efficient way of
doing it (too much walking) since she could easily bring more than one
panel each time. However, since the panels are not attached to each
other, should she want to bring more than one panel at once, she would
have to walk a little further to the leftmost panel about to be slid
and then push them all together. She could even walk all the way to
the absolute leftmost panel and slide them all together but, after
doing so, she would be required to come back to the right hand side to
rotate the single panel by the slot in the railing.
First question: what is the most efficient method for opening all
glass panels with the minimum amount of walking?
As far as I know, this is an open problem. I have asked it to a few
people in combinatorics but so far I do not have an answer.
What do I know about it? I wrote a computer program to find the
solution by brute force, which is capable of dealing with up to 16
panels. Once you see the solution, a conjecture immediately pops up in
your mind. You do it recursively! Split all panels in two halves,
open the rightmost half (using recursion), walk all the way to the
left, bring the remaining doors to the right and open them (using
recursion again).
Second question: is this indeed the best method?
 A: Suppose there are $n$ $1$s in a row at the start. Let $f(n)$ be the cost of the most efficient way to clear the second position, $n-1$ $1$s followed by a $0$. $f(1) = 0, f(2)=2, f(4) = 8.$
Say that a move $a_i$ (counting from the right) is a record if for all $j \lt i, a_j < a_i$. 
Claim: In an efficient strategy, just before every record the position is a string of $1$s followed by a string of $0$s (empty on the first move).
Proof: If there is a $0$ followed by a $1$ to the right of the leftmost window you are moving, then you could reach the same configuration faster by not creating the leftmost $0$. 
So, in any efficient strategy, after any record, you clear all of the $1$s you move before the next record. 
The last record's value is $n$. Consider the second-to-last record, of value $m$, in an efficient sequence.  $f(n) = f(m) + n + f(n-m)$. You clear the bottom $m$ places, then shift the remaining $n-m$ $1$s, then clear those $n-m$ $1$s. So, $f(n) = \min_{m\lt n} f(m) + f(n-m)+n$. 
Claim: $f(n) \ge n \log_2 n$ with equality when $n$ is a power of $2$.
Proof: This is trivially true for $n=1$. If each $f(k) \ge k \log_2 k$ for $k \lt n$ then $f(n) \ge n + \min_{0 \lt x\lt n}(x \log_2 x + (n-x) \log_2(n-x)).$ The minimum value is when $x=n/2,$ so $f(n) \ge n+ 2 (n/2) \log_2 (n/2) = n \log_2 n.$ So, by strong induction, $f(n) \ge n \log_2 n$. This is achieved when $n$ is a power of $2$ by the recursive construction so that the penultimate record is $n/2$.
Claim: If $n=2^k+a$ with $0 \le a \le 2^k$ then $f(n) = k(2^k) + (k+2)a$. You can choose any penultimate record $m$ so that $2^{k-1} \le m,n-m \le 2^k$. This gives a recursive description of the set of all optimal strategies.
Proof: Strong induction. The formula holds if you set the penultimate record $m = \lfloor n/2 \rfloor$. Note that $f(n+1)-f(n) = 2+\lfloor \log_2 n \rfloor$ so decreasing $m \le n/2$ by $1$ and increasing $n-m$ by $1$ only changes $n+f(m)+f(n-m)$ if $m-1$ and $n-m$ are between different powers of $2$. 
