Counting number of filled squares 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.

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.
