login
The OEIS is supported by the many generous donors to the OEIS 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, 98, 110, 126 (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
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
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)