login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..50.

Kevin K. Ferland, Record crossword puzzles, The American Mathematical Monthly, 121 (2014), 534-536.

Kevin Ferland, Proof of Crossword Puzzle Record

Rob Pratt, Illustrations of solutions for n <= 50

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.

From Elizabeth Axoy, Aug 20 2019: (Start)

Here is a 15 X 15 crossword with 96 words, where 0 is a white square and 1 is a black square.

  000010000100000

  000010000100000

  000010000100000

  111000111000111

  000001000010000

  000100000001000

  000010000100000

  111000111000111

  000001000010000

  000100000001000

  000010000100000

  111000111000111

  000001000010000

  000001000010000

  000001000010000

(End)

CROSSREFS

Sequence in context: A168335 A315852 A155776 * A295318 A184111 A181764

Adjacent sequences:  A243823 A243824 A243825 * A243827 A243828 A243829

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 10:20 EDT 2019. Contains 328317 sequences. (Running on oeis4.)