This problem is based on a problem from last year's United States of America Mathematical Talent Search (USAMTS).  While that problem had a simple solution, I have chosen to extend it to a more general problem that is as yet, open-ended.  After creating this problem, I realized its complexity and would appreciate input or advances toward a solution beyond the work I have included.  I do not know how to classify this problem.  It is most likely a combinatorics ("combinatorture") problem.  Let me describe the problem.

There are n integer lattice points (any point with integer coordinates). You must place these points in the smallest dimensional box possible such that no more than 2 points are on any line in any direction.  For example:

is a solution for 6 points, but and are not, because three points lie on the same line. 

How do you know that you have found the smallest box possible?  It's easy enough for n=1 to 14.  We know that we cannot place more than 2 points in any row, so the number of horizontal lines in the box cannot be less than n/2.  We know that we cannot place more than 2 points in any column, so the number of of vertical lines in the box cannot be less than n/2.  Thus, the minimum number of horizontal and vertical lines in the grid has to be the least integer greater than or equal to n/2.  These grids are examples of how you can place n points so that there are no more than 2 on any row or column. 

I am ignoring diagonal lines for a time to demonstrate that this can be extended to as many points you want, but actual solutions to the problem may not have three points in a line:

3

4

5

6

7

8

So, for n up to 14, the smallest box is the square I just described.  When you try to do the same for 15 and 16, there is a problem.  I have not been able to place 15 or 16 points on a 7x7 square (i.e. 8x8 lattice points) such that no more than 2 are on any line.  I have not been able to prove its impossibility either, although I ran a computer program written in C all night testing possible combinations.  The program did not complete, and did not find any solutions.  I conjecture that there are no solutions for 16 points.  The ultimate course of this conjecture would be to construct a function that would return the number of solutions possible in the smallest square given n points.  I have proven that there are only two solutions for n=6 in the smallest square (they are actually the same solution rotated 90˚), but have not found a method for doing so in the general case.

Here are solutions in the smallest possible square for up to 14 points.  Some of these may have other unique solutions, I am only using the solutions which have a diagonal line of symmetry and a point in the upper left corner.  If the grids are completely drawn and the segments are extended, none of them have more than 2 points on each segment:

3

4

5

6

7

8

9

10

11

12

13

14

You can see why the solutions get harder to find, and why there may be no solution for n=15 and 16.  Look at the number of slopes possible for each of the square grid sizes.  The red lines on these grids are examples of  lines with a slope that is able to intersect three or more lattice points.  In other words, when placing new points, these are the only slopes that will cause you trouble.  Their number appears to be increasing in increments of four, but I have not proved that this continues forever.

1x1: 0 slopes (3 or 4 point)

2x2: 4 slopes (5 or 6 points)

3x3: 4 slopes (7 or 8 points)

4x4: 8 slopes (9 or 10 points)

5x5: 8 slopes (11 or 12 points)

6x6: 16 slopes (13 or 14 points)

7x7: 16 slopes (15 or 16 points)

8x8: 20 slopes (17 or 18 points)

Since a solution or a proof of nonexistence of such a solution for 15 and 16 points on a 7x7 square would shed some light on the original problem, this special case should be the first thing to be solved.  An easy way to examine this particular problem is to look at it like trying to place all 16 pawns on a chessboard such that no more than 2 are in a line.  This makes it easier to manipulate the points and look at why certain combinations don't work.  It is possible to place 16 such that the first 14 do not cause a problem, and only the bottom three rows contain the offending three-to-a-line points.  You will notice that the last few points are forced to be in certain places, and those places happen to be right in line with one another. 

Thank you, and please send any ideas or solutions to quintopia@quintopia.net