OFFSET
1,2
COMMENTS
All the numbers listed so far were calculated using LpSolveIDE. It can be shown that the sequence of densities a(n)/n^2 has a limit as n goes to infinity, which is the supremum of all the elements in the sequence. With the help of the computer, it was shown that a(n) is not more than 0.608956n^2.
LINKS
E. J. Ionascu, D. Pritkin and S. E. Wright, k-Dependence and Domination in Kings Graphs, Amer. Math. Monthly, vol. 115, no. 9, (2008), pp. 820-836.
FORMULA
a(n) is approximately 3n^2/5 (conjecture).
EXAMPLE
a(2)=2 because one can check that any arrangement of two kings will satisfy the requirement but any arrangement of three kings will not.
PROG
(LpSolveIDE) /* Objective function n=10*/
max: x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x19 + x110
+ x21 + x22 + x23 + x24 + x25 + x26 + x27 + x28 + x29 + x210
+ x31 + x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 + x310
+ x41 + x42 + x43 + x44 + x45 + x46 + x47 + x48 + x49 + x410
+ x51 + x52 + x53 + x54 + x55 + x56 + x57 + x58 + x59 + x510
+ x61 + x62 + x63 + x64 + x65 + x66 + x67 + x68 + x69 + x610
+ x71 + x72 + x73 + x74 + x75 + x76 + x77 + x78 + x79 + x710
+ x81 + x82 + x83 + x84 + x85 + x86 + x87 + x88 + x89 + x810
+ x91 + x92 + x93 + x94 + x95 + x96 + x97 + x98 + x99 + x910
+ x101 + x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 + x1010;
/* Variable bounds */
2x11 + x12 + x22 + x21 < 3;
2x110 + x19 + x29 + x210 < 3;
2x101 + x91 + x92 + x102 < 3;
2x1010 + x109 + x99 + x910 < 3;
3x12 + x11 + x21 + x22 + x23 + x13 < 5;
3x13 + x12 + x22 + x23 + x24 + x14 < 5;
3x14 + x13 + x23 + x24 + x25 + x15 < 5;
3x15 + x14 + x24 + x25 + x26 + x16 < 5;
3x16 + x15 + x25 + x26 + x27 + x17 < 5;
3x17 + x16 + x26 + x27 + x28 + x18 < 5;
3x18 + x17 + x27 + x28 + x29 + x19 < 5;
3x19 + x18 + x28 + x29 + x210 + x110 < 5;
3x21 + x11 + x12 + x22 + x32 + x31 < 5;
3x31 + x21 + x22 + x32 + x42 + x41 < 5;
3x41 + x31 + x32 + x42 + x52 + x51 < 5;
3x51 + x41 + x42 + x52 + x62 + x61 < 5;
3x61 + x51 + x52 + x62 + x72 + x71 < 5;
3x71 + x61 + x62 + x72 + x82 + x81 < 5;
3x81 + x71 + x72 + x82 + x92 + x91 < 5;
3x91 + x81 + x82 + x92 + x102 + x101 < 5;
3x210 + x110 + x19 + x29 + x39 + x310 < 5;
3x310 + x210 + x29 + x39 + x49 + x410 < 5;
3x410 + x310 + x39 + x49 + x59 + x510 < 5;
3x510 + x410 + x49 + x59 + x69 + x610 < 5;
3x610 + x510 + x59 + x69 + x79 + x710 < 5;
3x710 + x610 + x69 + x79 + x89 + x810 < 5;
3x810 + x710 + x79 + x89 + x99 + x910 < 5;
3x910 + x810 + x89 + x99 + x109 + x1010 < 5;
3x102 + x101 + x91 + x92 + x93 + x103 < 5;
3x103 + x102 + x92 + x93 + x94 + x104 < 5;
3x104 + x103 + x93 + x94 + x95 + x105 < 5;
3x105 + x104 + x94 + x95 + x96 + x106 < 5;
3x106 + x105 + x95 + x96 + x97 + x107 < 5;
3x107 + x106 + x96 + x97 + x98 + x108 < 5;
3x108 + x107 + x97 + x98 + x99 + x109 < 5;
3x109 + x108 + x98 + x99 + x910 + x1010 < 5;
4x22 + x11 + x12 + x13 + x21 + x23 + x31 + x32 + x33 < 8;
4x23 + x12 + x13 + x14 + x22 + x24 + x32 + x33 + x34 < 8;
4x24 + x13 + x14 + x15 + x23 + x25 + x33 + x34 + x35 < 8;
4x25 + x14 + x15 + x16 + x24 + x26 + x34 + x35 + x36 < 8;
4x26 + x15 + x16 + x17 + x25 + x27 + x35 + x36 + x37 < 8;
4x27 + x16 + x17 + x18 + x26 + x28 + x36 + x37 + x38 < 8;
4x28 + x17 + x18 + x19 + x27 + x29 + x37 + x38 + x39 < 8;
4x29 + x18 + x19 + x110 + x28 + x210 + x38 + x39 + x310 < 8;
4x32 + x21 + x22 + x23 + x31 + x33 + x41 + x42 + x43 < 8;
4x33 + x22 + x23 + x24 + x32 + x34 + x42 + x43 + x44 < 8;
4x34 + x23 + x24 + x25 + x33 + x35 + x43 + x44 + x45 < 8;
4x35 + x24 + x25 + x26 + x34 + x36 + x44 + x45 + x46 < 8;
4x36 + x25 + x26 + x27 + x35 + x37 + x45 + x46 + x47 < 8;
4x37 + x26 + x27 + x28 + x36 + x38 + x46 + x47 + x48 < 8;
4x38 + x27 + x28 + x29 + x37 + x39 + x47 + x48 + x49 < 8;
4x39 + x28 + x29 + x210 + x38 + x310 + x48 + x49 + x410 < 8;
4x42 + x31 + x32 + x33 + x41 + x43 + x51 + x52 + x53 < 8;
4x43 + x32 + x33 + x34 + x42 + x44 + x52 + x53 + x54 < 8;
4x44 + x33 + x34 + x35 + x43 + x45 + x53 + x54 + x55 < 8;
4x45 + x34 + x35 + x36 + x44 + x46 + x54 + x55 + x56 < 8;
4x46 + x35 + x36 + x37 + x45 + x47 + x55 + x56 + x57 < 8;
4x47 + x36 + x37 + x38 + x46 + x48 + x56 + x57 + x58 < 8;
4x48 + x37 + x38 + x39 + x47 + x49 + x57 + x58 + x59 < 8;
4x49 + x38 + x39 + x310 + x48 + x410 + x58 + x59 + x510 < 8;
4x52 + x41 + x42 + x43 + x51 + x53 + x61 + x62 + x63 < 8;
4x53 + x42 + x43 + x44 + x52 + x54 + x62 + x63 + x64 < 8;
4x54 + x43 + x44 + x45 + x53 + x55 + x63 + x64 + x65 < 8;
4x55 + x44 + x45 + x46 + x54 + x56 + x64 + x65 + x66 < 8;
4x56 + x45 + x46 + x47 + x55 + x57 + x65 + x66 + x67 < 8;
4x57 + x46 + x47 + x48 + x56 + x58 + x66 + x67 + x68 < 8;
4x58 + x47 + x48 + x49 + x57 + x59 + x67 + x68 + x69 < 8;
4x59 + x48 + x49 + x410 + x58 + x510 + x68 + x69 + x610 < 8;
4x62 + x51 + x52 + x53 + x61 + x63 + x71 + x72 + x73 < 8;
4x63 + x52 + x53 + x54 + x62 + x64 + x72 + x73 + x74 < 8;
4x64 + x53 + x54 + x55 + x63 + x65 + x73 + x74 + x75 < 8;
4x65 + x54 + x55 + x56 + x64 + x66 + x74 + x75 + x76 < 8;
4x66 + x55 + x56 + x57 + x65 + x67 + x75 + x76 + x77 < 8;
4x67 + x56 + x57 + x58 + x66 + x68 + x76 + x77 + x78 < 8;
4x68 + x57 + x58 + x59 + x67 + x69 + x77 + x78 + x79 < 8;
4x69 + x58 + x59 + x510 + x68 + x610 + x78 + x79 + x710 < 8;
4x72 + x61 + x62 + x63 + x71 + x73 + x81 + x82 + x83 < 8;
4x73 + x62 + x63 + x64 + x72 + x74 + x82 + x83 + x84 < 8;
4x74 + x63 + x64 + x65 + x73 + x75 + x83 + x84 + x85 < 8;
4x75 + x64 + x65 + x66 + x74 + x76 + x84 + x85 + x86 < 8;
4x76 + x65 + x66 + x67 + x75 + x77 + x85 + x86 + x87 < 8;
4x77 + x66 + x67 + x68 + x76 + x78 + x86 + x87 + x88 < 8;
4x78 + x67 + x68 + x69 + x77 + x79 + x87 + x88 + x89 < 8;
4x79 + x68 + x69 + x610 + x78 + x710 + x88 + x89 + x810 < 8;
4x82 + x71 + x72 + x73 + x81 + x83 + x91 + x92 + x93 < 8;
4x83 + x72 + x73 + x74 + x82 + x84 + x92 + x93 + x94 < 8;
4x84 + x73 + x74 + x75 + x83 + x85 + x93 + x94 + x95 < 8;
4x85 + x74 + x75 + x76 + x84 + x86 + x94 + x95 + x96 < 8;
4x86 + x75 + x76 + x77 + x85 + x87 + x95 + x96 + x97 < 8;
4x87 + x76 + x77 + x78 + x86 + x88 + x96 + x97 + x98 < 8;
4x88 + x77 + x78 + x79 + x87 + x89 + x97 + x98 + x99 < 8;
4x89 + x78 + x79 + x710 + x88 + x810 + x98 + x99 + x910 < 8;
4x92 + x81 + x82 + x83 + x91 + x93 + x101 + x102 + x103 < 8;
4x93 + x82 + x83 + x84 + x92 + x94 + x102 + x103 + x104 < 8;
4x94 + x83 + x84 + x85 + x93 + x95 + x103 + x104 + x105 < 8;
4x95 + x84 + x85 + x86 + x94 + x96 + x104 + x105 + x106 < 8;
4x96 + x85 + x86 + x87 + x95 + x97 + x105 + x106 + x107 < 8;
4x97 + x86 + x87 + x88 + x96 + x98 + x106 + x107 + x108 < 8;
4x98 + x87 + x88 + x89 + x97 + x99 + x107 + x108 + x109 < 8;
4x99 + x88 + x89 + x810 + x98 + x910 + x108 + x109 + x1010 < 8;
x11 < 1; x12 < 1; x13 < 1; x14 < 1; x15 < 1; x16 < 1; x17 < 1; x18 < 1; x19 < 1; x110 < 1;
x21 < 1; x22 < 1; x23 < 1; x24 < 1; x25 < 1; x26 < 1; x27 < 1; x28 < 1; x29 < 1; x210 < 1;
x31 < 1; x32 < 1; x33 < 1; x34 < 1; x35 < 1; x36 < 1; x37 < 1; x38 < 1; x39 < 1; x310 < 1;
x41 < 1; x42 < 1; x43 < 1; x44 < 1; x45 < 1; x46 < 1; x47 < 1; x48 < 1; x49 < 1; x410 < 1;
x51 < 1; x52 < 1; x53 < 1; x54 < 1; x55 < 1; x56 < 1; x57 < 1; x58 < 1; x59 < 1; x510 < 1;
x61 < 1; x62 < 1; x63 < 1; x64 < 1; x65 < 1; x66 < 1; x67 < 1; x68 < 1; x69 < 1; x610 < 1;
x71 < 1; x72 < 1; x73 < 1; x74 < 1; x75 < 1; x76 < 1; x77 < 1; x78 < 1; x79 < 1; x710 < 1;
x81 < 1; x82 < 1; x83 < 1; x84 < 1; x85 < 1; x86 < 1; x87 < 1; x88 < 1; x89 < 1; x810 < 1;
x91 < 1; x92 < 1; x93 < 1; x94 < 1; x95 < 1; x96 < 1; x97 < 1; x98 < 1; x99 < 1; x910 < 1;
x101 < 1; x102 < 1; x103 < 1; x104 < 1; x105 < 1; x106 < 1; x107 < 1; x108 < 1; x109 < 1; x1010 < 1;
int x11, x12, x13, x14, x15, x16, x17, x18, x19, x110,
x21, x22, x23, x24, x25, x26, x27, x28, x29, x210,
x31, x32, x33, x34, x35, x36, x37, x38, x39, x310,
x41, x42, x43, x44, x45, x46, x47, x48, x49, x410,
x51, x52, x53, x54, x55, x56, x57, x58, x59, x510,
x61, x62, x63, x64, x65, x66, x67, x68, x69, x610,
x71, x72, x73, x74, x75, x76, x77, x78, x79, x710,
x81, x82, x83, x84, x85, x86, x87, x88, x89, x810,
x91, x92, x93, x94, x95, x96, x97, x98, x99, x910,
x101, x102, x103, x104, x105, x106, x107, x108, x109, x1010;
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Eugen J. Ionascu, Aug 12 2008
STATUS
approved