login
A243826
Maximum number of clues in a certain class of n X n crossword puzzles.
1
0, 0, 6, 8, 10, 12, 22, 28, 32, 40, 50, 64, 72, 84, 96, 116, 126, 144, 158, 184, 198, 220, 236, 268, 284, 312, 332, 368, 388, 420, 442, 484, 506, 544, 570, 616, 642, 684, 712, 764, 792, 840, 872, 928, 960, 1012, 1046, 1108, 1142, 1200
OFFSET
1,3
COMMENTS
Uses New York Times rules of: connectivity, 180-degree rotational symmetry, answer length at least 3.
a(1)-a(50) computed by using integer linear programming.
Because each row or column can have at most (n+1)/4 clues (consider appending a black square, and note that every clue requires 4 squares), we have a(n) <= 2n floor((n+1)/4).
LINKS
Kevin K. Ferland, Record crossword puzzles, The American Mathematical Monthly, 121 (2014), 534-536.
Kevin K. Ferland, Counting Clues in Crosswords, Recreational Mathematics Magazine, (2020) Vol. 7, Issue 13, 1-7.
FORMULA
Except for n = 7, 11, and 19, conjectured recursive formula is a(n) = a(n-4) + 4(n-3) - [2 if mod(n,8) in {1,7}]. In particular, conjectured explicit formula is a(n) = 2n floor((n+1)/4) if mod(n,4) = 2.
EXAMPLE
The trivial all-white puzzle is optimal for 3 <= n <= 6.
The Ferland paper shows that a(15) = 96.
CROSSREFS
Sequence in context: A168335 A315852 A155776 * A295318 A343569 A331549
KEYWORD
nonn
AUTHOR
Rob Pratt, Jun 11 2014
EXTENSIONS
Upper bound and conjectured formulas from Rob Pratt, Jun 23 2014
More terms from Rob Pratt, Jul 06 2015
STATUS
approved