6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you describe the possible states and allowable moves abstractly, say using sequences of $1$s and $0$s? $\endgroup$ – Douglas Zare Aug 23 '16 at 18:06
  • $\begingroup$ @douglas, I guess you are right. I am saying "close" in the sense that the glass doors are being "closed" against the wall but surely the terrace is being opened in the process. I am new in this system and I'd appreciate your advice as to whether I should edit my question to correct for this. $\endgroup$ – Ruy Aug 23 '16 at 18:39
  • $\begingroup$ It's been edited. $\endgroup$ – Ruy Aug 23 '16 at 18:55
  • $\begingroup$ Hi @douglas, here is the description you asked for. Number each position in the balcony from right to left, so that position 1 is the rightmost, while position n is the leftmost. The states would consist of assigning 0 or 1 to each position. A move is the choice of a position k affecting the state as follows: all 1's in positions from 1 to k are shifted to the right as much as possible leading to an adjacent block of 1's. In addition the '1' at position 1 would be changed to 0 (the panel was stored). Here is an example: 11011001 -> 11000110. I hope I've made myself understood. $\endgroup$ – Ruy Aug 23 '16 at 19:32
  • $\begingroup$ Ok, and the cost of that move is $k$, and you want to minimize the total cost of converting the string of $1$s to the string of $0$s? $\endgroup$ – Douglas Zare Aug 24 '16 at 4:14
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.