Puzzles of the {0, 1, 2}^3 grid: December 1992
--------------------------------------------------------------------
Select as much as possible vertices from the grid (3*3*3)
such that there are no three in a line.
Solution: maximal number is 16. (Achim Flammenkamp)
. o o o . o o o . 12 edges &
o . o . . . o . o 4 vertives (tetrahedron)
o o . o . o . o o
--------------------------------------------------------------------
Select as much as possible vertices from the grid (3*3*3)
such that there are no four in a plane.
Solution: maximal number is 8. (Achim Flammenkamp, Torsten Sillke)
there is only one solution. It has threefold symmetry.
o . . . o o . . .
. o . o . . o . .
. o . . . . . . o
Proof of the upper bound 8: (Achim Flammenkamp)
As in each layer you can place maximal 3 vertices, you get an upper
bound of 9. But 9 is impossible. If you place in each layer 3 points,
you have in each layer 3 lines through the 3 pairs of points. So there
are 9 lines in the 3 layers. Now count the different slopes a line can
have in a 3*3 layer. As there are only 8 different slopes, you have two
parallel lines by the piginhole pinciple. But this means you have four
on a plane. I assumed, that there are no 3 points in a line in a layer,
but if there were 3 in a line in the cube then each additional point
gives a 4 in the plane configuration.