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.

1, 0, 0, 4, 8, 10, 10, 16, 28, 32, 40, 46, 58, 68, 88, 98, 110, 126

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..18.

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

Paul Tabatabai and Dieter P. Gruber, Knights and Liars on Graphs, J. Int. Seq., Vol. 24 (2021), Article 21.5.8.

Example

From Paul Tabatabai, Jul 06 2020: (Start)
Optimal configurations for n = 16, 17 and 18:
a(16) = 98:
. . . . . . . . . . . . . . . .
. 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) = 110:
. . . . . . . . . . . . . . . . .
. . . . . . 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(18) = 126:
. . . . . . . . . . . . . . . . . .
. 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 . .
. . . . . . . . . . . . . . . . . .
(End)

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

a(16)-a(18) from Paul Tabatabai, Jul 06 2020

Status

approved