Martin Gardner’s Minimum No-3-in-a-Line Problem

DOI10.4169/AMER.MATH.MONTHLY.121.03.213zbMATH Open1303.05020arXiv1206.5350OpenAlexW3098097583MaRDI QIDQ2928610FDOQ2928610

Authors: Alec S. Cooper, Oleg Pikhurko, John Schmitt, Gregory S. Warrington 

Publication date: 10 November 2014

Published in: American Mathematical Monthly (Search for Journal in Brave)

Abstract: In Martin Gardner's October, 1976 Mathematical Games column in Scientific American, he posed the following problem: "What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal?" We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.

Full work available at URL: https://arxiv.org/abs/1206.5350

Recommendations

• Extensions of sufficient conditions for starlikeness and convexity of order \(\alpha \)
• scientific article; zbMATH DE number 1949137
• Extensions of sufficient conditions for starlikeness and convexity of order \(\alpha\) for multivalent function
• scientific article; zbMATH DE number 2069779
• Some classes of order \(\alpha\) for second-order differential inequalities

zbMATH Keywords

\(n\)-queens problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Orthogonal arrays, Latin squares, Room squares (05B15) Other designs, configurations (05B30) Recreational mathematics (00A08)

Cited In (5)

• Some classes of order \(\alpha\) for second-order differential inequalities
• Domination in chessboards
• Repeatedly applying the combinatorial Nullstellensatz for zero-sum grids to Martin Gardner's minimum no-3-in-a-line problem
• Geometric dominating sets -- a minimum version of the no-three-in-line problem
• Progress in the no-three-in-line-problem

This page was built for publication: Martin Gardner’s Minimum No-3-in-a-Line Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2928610)