Note: This answer is here for potential future solvers. Due to the high elegance of this solution I thought it would be ideal to post it as an alternative to @Dark-Thunder's solution. You can see many similarities between these answers, the general movement is the same! All other potential valid solutions should be caught under these ...
Generalizing my comment on Gareth's solution, we can
arrange Pascal's triangle as a right triangular array and ignore the right half ($n < 2k$) to obtain something like this:
1 4 6
We then, for any $N$,
Gareth has found the optimal solutions, but here is an R script if anyone wants to mess around with the upper bounds for n, just change the value of the variable"UpperBound".
gets to within about
of the desired answer. I think this is best possible with <= 100 cards.
Found with the help of a computer, but purely as an aid to calculation. My approach was to
[EDITED to add:]
Out of curiosity, I also ran a more automated search for the larger bound of n=500 mentioned in the OP. For this,
The automated search also ...
since they are 1/64th increments, you can be left with a minimum of 1/64th of a cup. Add 1 cup, remove 1/2 cup, remove 1/4 cup, remove 1/8 cup, remove 1/16 cup, remove 1/32 cup, remove 1/64 cup, there is 1/64th of a cup left.
A) If the board were instead very large (many billions of cells, for example), what limit could we place on the maximum sign density?
B) Again on a very large board, what limit could we place on the sign density if we eliminate the 4th rule and allow older signs to be blocked?
C) Solutions for odd-size boards, with and without rule 4
This is not a (new) answer to the original question, but I don't have enough reputation to comment. I tried to address the call for generalization using a similar technique as Jaap. Below the results for the board sizes that fit in my main memory. Unfortunately, 6 x 6 does not fit.
size # configs w b
3 x 2 180 12 13
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3\times3$ the optimal number of moves is $16$.
Without the need to alternate moves the optimum is $14$ moves, for example just by ...
EDIT: As @greenturtle pointed out in a comment, it seems that everyone else is doing the count by ply, and not the whole moves. The question is unclear to me about this on how the count is done. So thus my count is wrong by the majority's decision.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below ...
Postscript: in hindsight I was able to run an exhaustive search with the minimum distance between signs set to 17 km and no restriction on the first sign.
Edit: a revised solution
My first solution
The maximum distance marker I have managed to construct is
Using the following placement of stickers (in bold as suggested).
Progression on the upper bound
I had originally thought I had a solution with distance
Using the following signs
But as Weather Vane correctly pointed out in the comments, I had constructed a new sign using only ...