Ken's Puzzle of the Week
Hiding in a Forest

In an NxN forest, position as many hunters as possible, such that there are no more than two hunters in any straight line, and no hunter can see another because there is at least one tree between any two hunters.  After maximizing the number of hunters, try to minimize the number of trees.  Each tree and each hunter take up one unit square in the forest.  For example, in a 3x3 forest, four hunters can be placed.  In a 5x5 forest, at least five hunters can be placed.  Find the maximum number of hunters for N=4,5,6,7,8,9.

Source: Original.

Keith Lynch's solutions are a good summary:

If I define a "mandatory tree" as one that's in a position that's the
*only* position between two hunters, and if whenever the line between two hunters 
doesn't intersect a line between any other two hunters, such that where on that 
line the tree goes doesn't matter, I arbitrarily define the middle position as 
being a mandatory tree (there's always a middle position, as there are always 
an odd number of spaces between any two hunters), then all the minimal solutions 
of up to eight on a side consist of nothing but mandatory trees.

3 or 4 on a side: 4 hunters, 5 trees:

H t H
t t t
H t H

5 or 6 on a side: 6 hunters, 12 trees:

H t H
t t t t
H t   t H
  t t t t
    H t H

7 or 8 on a side: 8 hunters, 17 trees:

H t H
    t t t
t t     H t H
    t t t
H t H     t t
    t t t
        H t H

9 or 10 on a side: 10 hunters, 31 trees:

    H t H
  t t T   t t
H         t     H
  t t t t     t t
t t   t   t H t H
    t t t t t t
H t H     t   t
    t t t
        H t H

I'm not yet absolutely certain the last one is optimal, and not just because of 
the lack of any obvious symmetry.  I capitalized the one non-mandatory tree (T).  
It can be moved one space down and to the right, or two spaces down and to the right.
[Update 6Mar07: Dan Chirica notes this is indeed optimal.]

There's a semi-unique solution for eleven on a side, and it's much prettier than
the one for nine.  There are 12 hunters and 39 trees.  37 trees are "mandatory"
in the sense I used before.  The two that aren't (but are still mandatory in
the ordinary meaning of the term) are uppercase.

    H t H
          t t t
  t T t         H t H
        t t t t
H t   t H     t   t t
      t t t t t
t t   t     H t   t H
      t t t t
H t H         t T t
      t t t
            H t H

The number of ways of having N+1 hunters on an N by N board (N odd) is given by