login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A289362 Largest possible number of white squares (cells) in an n X n square board such that each cell is either white or red; among the cells adjacent to each white one, the number of white cells is equal to the number of red ones; and for each red cell, the number of adjacent white cells differs from the number of adjacent red cells. 0
1, 0, 0, 4, 8, 10, 10, 16, 28, 32, 40, 46, 58, 68, 88 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Suppose that in each square of an n X n square board there is either a knight (who always tells the truth) or a liar (who always lies). Let's say each person makes the statement: "Exactly one half of my neighbors are knights." Then a(n) is the maximum possible number of knights.

For all the known exact values of a(n), a(n) is much less than (1/2)*n^2. However, as n increases, a(n) tends to (2/3)*n^2.

From Luca Petrone, May 14 2018: (Start)

The claimed value a(16)=88 was incorrect, since a(16) >= 92 from a nonexhaustive search. Each of the following two configurations has 92 knights:

.

  . . . . . . . . . . . . . . . .

  . o o o o o o o o o . . o o o .

  . o . . . . . . . o . . o . o .

  . o o . . . . . o o . . o . o .

  . . o . . . . . o . . . o o o .

  . o o . o o o . o o o . . . . .

  . o . o o . o o . . o . . . . .

  . o o o . . . o o o o . o o o .

  . . . . o o o . . . . o o . o .

  . . . o o . o o . . o o . o o .

  . . . o . . . o . . o . . o . .

  . . . o o o o o . . o o . o o .

  . . . . . . . . . . . o o . o .

  . o o . . . . . . o o . o o o .

  . o o . . . . . . o o . . . . .

  . . . . . . . . . . . . . . . .

.

  . . . . . . . . . . . . . . . .

  . o o o o . . o o o o . . o o .

  . o . . o . . o . . o . . o o .

  . o o o o . . o o o o . . . . .

  . . . . . . . . . . . . . . . .

  . . . . . o o . . . . . . o o .

  . o o o . o o . . o o o . o o .

  . o . o o . . . . o . o o . . .

  . o o . o o . . . o o . o o . .

  . . o . . o . . . . o o . o . .

  . o o . o o . o o o . o o o . .

  . o . o o . o o . o o . . . . .

  . o o o . o o . . . o o . . . .

  . . . . . o . o o o . o . . . .

  . . . . . o o o . o o o . . . .

  . . . . . . . . . . . . . . . .

.

a(17) >= 104.

(End)

LINKS

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

Vladimir Letsko, Mathematical Marathon: Problem 140 (in Russian).

CROSSREFS

Sequence in context: A108806 A310967 A310968 * A074776 A310969 A153762

Adjacent sequences:  A289359 A289360 A289361 * A289363 A289364 A289365

KEYWORD

nonn,more

AUTHOR

Vladimir Letsko, Jul 07 2017

EXTENSIONS

Incorrect a(16) deleted by Luca Petrone, May 14 2018

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 June 1 09:53 EDT 2020. Contains 334762 sequences. (Running on oeis4.)