|
%I #52 Aug 13 2021 19:12:39
%S 1,0,0,4,8,10,10,16,28,32,40,46,58,68,88,98,110,126
%N 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.
%C 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.
%C 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.
%C From _Luca Petrone_, May 14 2018: (Start)
%C 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:
%C .
%C . . . . . . . . . . . . . . . .
%C . o o o o o o o o o . . o o o .
%C . o . . . . . . . o . . o . o .
%C . o o . . . . . o o . . o . o .
%C . . o . . . . . o . . . o o o .
%C . o o . o o o . o o o . . . . .
%C . o . o o . o o . . o . . . . .
%C . o o o . . . o o o o . o o o .
%C . . . . o o o . . . . o o . o .
%C . . . o o . o o . . o o . o o .
%C . . . o . . . o . . o . . o . .
%C . . . o o o o o . . o o . o o .
%C . . . . . . . . . . . o o . o .
%C . o o . . . . . . o o . o o o .
%C . o o . . . . . . o o . . . . .
%C . . . . . . . . . . . . . . . .
%C .
%C . . . . . . . . . . . . . . . .
%C . o o o o . . o o o o . . o o .
%C . o . . o . . o . . o . . o o .
%C . o o o o . . o o o o . . . . .
%C . . . . . . . . . . . . . . . .
%C . . . . . o o . . . . . . o o .
%C . o o o . o o . . o o o . o o .
%C . o . o o . . . . o . o o . . .
%C . o o . o o . . . o o . o o . .
%C . . o . . o . . . . o o . o . .
%C . o o . o o . o o o . o o o . .
%C . o . o o . o o . o o . . . . .
%C . o o o . o o . . . o o . . . .
%C . . . . . o . o o o . o . . . .
%C . . . . . o o o . o o o . . . .
%C . . . . . . . . . . . . . . . .
%C .
%C a(17) >= 104.
%C (End)
%H Vladimir Letsko, <a href="http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_140">Mathematical Marathon: Problem 140</a> (in Russian).
%H Paul Tabatabai and Dieter P. Gruber, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Tabatabai/taba4.html">Knights and Liars on Graphs</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.8.
%e From _Paul Tabatabai_, Jul 06 2020: (Start)
%e Optimal configurations for n = 16, 17 and 18:
%e a(16) = 98:
%e . . . . . . . . . . . . . . . .
%e . o o o o . . o o o . o o o . .
%e . o . . o . . o . o o o . o . .
%e . o o o o . . o o . . . o o . .
%e . . . . . . . . o o . o o . . .
%e . . . . . o o o . o o o . o o .
%e . . . . . o . o o . . . . o o .
%e . o o o . o o . o o . . . . . .
%e . o . o o . o o . o . . . . . .
%e . o o . o o . o o o . o o o . .
%e . . o . . o . . . . o o . o . .
%e . o o . o o . . . o o . o o . .
%e . o . o o . . . . o . o o . . .
%e . o o o . o o . . o o o . o o .
%e . . . . . o o . . . . . . o o .
%e . . . . . . . . . . . . . . . .
%e a(17) = 110:
%e . . . . . . . . . . . . . . . . .
%e . . . . . . o o o o . o o o . . .
%e . . . . . . o . . o o o . o . . .
%e . o o o o . o o o . . . o o . . .
%e . o . . o o . . o o . o o . . . .
%e . o o o . o o o . o o o . o o o .
%e . . . o . . . o . . . . o o . o .
%e . . o o . . o o . . . o o . o o .
%e . . o . . . o . . . . o . . o . .
%e . . o o . . o o . . . o o . o o .
%e . . . o . . . o . . . . o o . o .
%e . o o o . o o o . o o o . o o o .
%e . o . . o o . . o o . o o . . . .
%e . o o o o . o o o . . . o o . . .
%e . . . . . . o . . o o o . o . . .
%e . . . . . . o o o o . o o o . . .
%e . . . . . . . . . . . . . . . . .
%e a(18) = 126:
%e . . . . . . . . . . . . . . . . . .
%e . o o o . . . . . o o o . . . . . .
%e . o . o . . . . . o . o . o o o . .
%e . o o o . . . . . o . o o o . o . .
%e . . . . . o o o . o o . . . o o . .
%e . . . . . o . o o . o o . o o . . .
%e . o o o . o o . o o . o o o . o o .
%e . o . o o . o o . o o . . . . o o .
%e . o o . o o . o o . o o . . . . . .
%e . . o . . o . . o . . o . . . . . .
%e . o o . o o . o o . o o . . . . . .
%e . o . o o . o o . o o . . . . o o .
%e . o o o . o o . o o . o o o . o o .
%e . . . . . o . o o . o o . o o . . .
%e . . . . . o o o . o o . . . o o . .
%e . . o o . . . . . o . o o o . o . .
%e . . o o . . . . . o o o . o o o . .
%e . . . . . . . . . . . . . . . . . .
%e (End)
%K nonn,more
%O 1,4
%A _Vladimir Letsko_, Jul 07 2017
%E Incorrect a(16) deleted by _Luca Petrone_, May 14 2018
%E a(16)-a(18) from _Paul Tabatabai_, Jul 06 2020
| 