×

Putting dots in triangles. (English) Zbl 1234.05050

Summary: Given a right-angled triangle of squares in a grid whose horizontal and vertical sides are \(n\) squares long, let \(N(n)\) denote the maximum number of dots that can be placed into the cells of the triangle such that each row, each column, and each diagonal parallel to the long side of the triangle contains at most one dot. It has been proven that \(N_f(n)=\lfloor{2n+1\over 3}\rfloor\). We give a new proof of the upper bound \(N_f(n)\leq\lfloor{2n+1\over 3}\rfloor\) using linear programming techniques.

MSC:

05B30 Other designs, configurations
90C05 Linear programming