Counting number of filled squares

Question

recently I came across the following problem: Consider a string of $n \geq 3$ blank squares. Start by colouring the leftmost square and rightmost square. Now, consider the following protocol to colour squares: at each iteration, you colour the square that has a maximal distance to its two closest squares, and in case of equality you choose the one on the left. You colour this square as long as its two adjacent squares aren't coloured yet.

To make the problem more intuitive I should probably mention that it is a variant of the classical urinary problem, in which you are given n urinaries and each person choses the urinary that is the furthest apart from all the urinaries that are already used, and in case of equality, you choose the one on the left (closest to the door, for instance).

My question is for each $n$, how many urinals are filled. I can't seem to find an easy recurrence whatsoever, so any help would be appreciated.

Answer 1

After the ends are colored, you operate in a run of $m$ blank squares between colored ones. If $m$ is odd, you color a square and replace it with two runs of $\frac 12(m-1)$. If $m$ is even, you color a square and replace it with a run of $\frac m2$ and a run of $\frac m2-1$ With the clarification that you can't color a cell next to any colored cell, with $m=1$ or $m=2$ you can't color any. Our recurrence becomes $$T(m)=\begin {cases} 0&m=1\\0&m=2\\2T(\frac 12(m-1))+1&m \text{ odd}\\T(\frac m2)+T(\frac m2-1)+1&m \text { even} \end {cases}$$ The solution to your problem is $2+T(n-2)$ because you start by coloring the two end squares, leaving a run of $n-2$ blank cells between colored ones.

Added: I made a spreadsheet to compute the recurrence values. $T(3)=T(4)=T(5)=1, T(6)=2, T(7)$ through $T(11)=3$. The values get stuck at $2^k-1$ for $2^k+1$ numbers, then step by ones up to $2^{k+1}-1$, which repeats $2^{k+1}+1$ times. So $T(15)$ through $T(23)$ are $7$, then we step up to $T(31)=15$ and get stuck at $15$ through $T(47)$ then step up to $T(63)=31$ and stay there through $T(95)=31$.

The run of $2^k-1$ extends from $2^{k+1}-1$ through $2^{k+1}+2^k-1$. We can use that to write a nonrecursive algorithm for $T(m)$. Given $m$, let $k=\lfloor \log_2(m+1) \rfloor-1$. If $m \le 2^{k+1}+2^k-1, T(m)=2^k-1$. If $m \gt 2^{k+1}+2^k-1, T(m)=2^k-1+m-(2^{k+1}+2^k-1)=m-2^{k+1}$. I have not proven that this formula works, just observed that it seems to.

Answer 2

I think the first thing to be noted is that whenever you colour a square, what happens to the left of it is independent of what happens to the right of it, right? Thus, even if that isn't the actual order in which the squares are coloured, you can think of colouring the mid square, then everything to the left of it. Then everything to the right of it.

To colour the left-hand side, colour the mid square, everything to the left of it, then to the right. And so on, and so forth..

Let $C_n$ denote the number of coloured squares when you have $n$ squares, without taking into account the two ends. So, for example, $C_3 = 0$.

If $n$ is odd and big enough, $C_n = 1 + 2C_{(n+1)/2}$ which means you coloured a square, and then are left with colouring the two halfs. If $n$ is even, then you have $C_n = 1 + C_{n/2} + C_{n/2 + 1}$. You also have $C_i = 0, i<5, C_5 = 1$.

The real number you want will be $2 + C_n$, because the two ends are also coloured.

For example, $2 + C_6 = 2 + 1 + C_3 + C4 = 3$ which which matches $c0c00c$ and

$2 + C_7 = 2 + 1 + 2C_4 = 3$ which matches $c00c00c$.