|
%I #15 Sep 29 2017 15:45:46
%S 0,2,5,9,15,21,28,37,47,60,71,84
%N Maximal number of kings in the toroidal king's graph on an n X n board such that each king is attacking no more than four other kings.
%C 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.
%H E. J. Ionascu, D. Pritkin and S. E. Wright, <a href="https://www.jstor.org/stable/27642610">k-Dependence and Domination in Kings Graphs</a>, Amer. Math. Monthly, vol. 115, no. 9, (2008), pp. 820-836.
%F a(n) is approximately 3n^2/5 (conjecture).
%e 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.
%o (LpSolveIDE) /* Objective function n=10*/
%o max: x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x19 + x110
%o + x21 + x22 + x23 + x24 + x25 + x26 + x27 + x28 + x29 + x210
%o + x31 + x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 + x310
%o + x41 + x42 + x43 + x44 + x45 + x46 + x47 + x48 + x49 + x410
%o + x51 + x52 + x53 + x54 + x55 + x56 + x57 + x58 + x59 + x510
%o + x61 + x62 + x63 + x64 + x65 + x66 + x67 + x68 + x69 + x610
%o + x71 + x72 + x73 + x74 + x75 + x76 + x77 + x78 + x79 + x710
%o + x81 + x82 + x83 + x84 + x85 + x86 + x87 + x88 + x89 + x810
%o + x91 + x92 + x93 + x94 + x95 + x96 + x97 + x98 + x99 + x910
%o + x101 + x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 + x1010;
%o /* Variable bounds */
%o 2x11 + x12 + x22 + x21 < 3;
%o 2x110 + x19 + x29 + x210 < 3;
%o 2x101 + x91 + x92 + x102 < 3;
%o 2x1010 + x109 + x99 + x910 < 3;
%o 3x12 + x11 + x21 + x22 + x23 + x13 < 5;
%o 3x13 + x12 + x22 + x23 + x24 + x14 < 5;
%o 3x14 + x13 + x23 + x24 + x25 + x15 < 5;
%o 3x15 + x14 + x24 + x25 + x26 + x16 < 5;
%o 3x16 + x15 + x25 + x26 + x27 + x17 < 5;
%o 3x17 + x16 + x26 + x27 + x28 + x18 < 5;
%o 3x18 + x17 + x27 + x28 + x29 + x19 < 5;
%o 3x19 + x18 + x28 + x29 + x210 + x110 < 5;
%o 3x21 + x11 + x12 + x22 + x32 + x31 < 5;
%o 3x31 + x21 + x22 + x32 + x42 + x41 < 5;
%o 3x41 + x31 + x32 + x42 + x52 + x51 < 5;
%o 3x51 + x41 + x42 + x52 + x62 + x61 < 5;
%o 3x61 + x51 + x52 + x62 + x72 + x71 < 5;
%o 3x71 + x61 + x62 + x72 + x82 + x81 < 5;
%o 3x81 + x71 + x72 + x82 + x92 + x91 < 5;
%o 3x91 + x81 + x82 + x92 + x102 + x101 < 5;
%o 3x210 + x110 + x19 + x29 + x39 + x310 < 5;
%o 3x310 + x210 + x29 + x39 + x49 + x410 < 5;
%o 3x410 + x310 + x39 + x49 + x59 + x510 < 5;
%o 3x510 + x410 + x49 + x59 + x69 + x610 < 5;
%o 3x610 + x510 + x59 + x69 + x79 + x710 < 5;
%o 3x710 + x610 + x69 + x79 + x89 + x810 < 5;
%o 3x810 + x710 + x79 + x89 + x99 + x910 < 5;
%o 3x910 + x810 + x89 + x99 + x109 + x1010 < 5;
%o 3x102 + x101 + x91 + x92 + x93 + x103 < 5;
%o 3x103 + x102 + x92 + x93 + x94 + x104 < 5;
%o 3x104 + x103 + x93 + x94 + x95 + x105 < 5;
%o 3x105 + x104 + x94 + x95 + x96 + x106 < 5;
%o 3x106 + x105 + x95 + x96 + x97 + x107 < 5;
%o 3x107 + x106 + x96 + x97 + x98 + x108 < 5;
%o 3x108 + x107 + x97 + x98 + x99 + x109 < 5;
%o 3x109 + x108 + x98 + x99 + x910 + x1010 < 5;
%o 4x22 + x11 + x12 + x13 + x21 + x23 + x31 + x32 + x33 < 8;
%o 4x23 + x12 + x13 + x14 + x22 + x24 + x32 + x33 + x34 < 8;
%o 4x24 + x13 + x14 + x15 + x23 + x25 + x33 + x34 + x35 < 8;
%o 4x25 + x14 + x15 + x16 + x24 + x26 + x34 + x35 + x36 < 8;
%o 4x26 + x15 + x16 + x17 + x25 + x27 + x35 + x36 + x37 < 8;
%o 4x27 + x16 + x17 + x18 + x26 + x28 + x36 + x37 + x38 < 8;
%o 4x28 + x17 + x18 + x19 + x27 + x29 + x37 + x38 + x39 < 8;
%o 4x29 + x18 + x19 + x110 + x28 + x210 + x38 + x39 + x310 < 8;
%o 4x32 + x21 + x22 + x23 + x31 + x33 + x41 + x42 + x43 < 8;
%o 4x33 + x22 + x23 + x24 + x32 + x34 + x42 + x43 + x44 < 8;
%o 4x34 + x23 + x24 + x25 + x33 + x35 + x43 + x44 + x45 < 8;
%o 4x35 + x24 + x25 + x26 + x34 + x36 + x44 + x45 + x46 < 8;
%o 4x36 + x25 + x26 + x27 + x35 + x37 + x45 + x46 + x47 < 8;
%o 4x37 + x26 + x27 + x28 + x36 + x38 + x46 + x47 + x48 < 8;
%o 4x38 + x27 + x28 + x29 + x37 + x39 + x47 + x48 + x49 < 8;
%o 4x39 + x28 + x29 + x210 + x38 + x310 + x48 + x49 + x410 < 8;
%o 4x42 + x31 + x32 + x33 + x41 + x43 + x51 + x52 + x53 < 8;
%o 4x43 + x32 + x33 + x34 + x42 + x44 + x52 + x53 + x54 < 8;
%o 4x44 + x33 + x34 + x35 + x43 + x45 + x53 + x54 + x55 < 8;
%o 4x45 + x34 + x35 + x36 + x44 + x46 + x54 + x55 + x56 < 8;
%o 4x46 + x35 + x36 + x37 + x45 + x47 + x55 + x56 + x57 < 8;
%o 4x47 + x36 + x37 + x38 + x46 + x48 + x56 + x57 + x58 < 8;
%o 4x48 + x37 + x38 + x39 + x47 + x49 + x57 + x58 + x59 < 8;
%o 4x49 + x38 + x39 + x310 + x48 + x410 + x58 + x59 + x510 < 8;
%o 4x52 + x41 + x42 + x43 + x51 + x53 + x61 + x62 + x63 < 8;
%o 4x53 + x42 + x43 + x44 + x52 + x54 + x62 + x63 + x64 < 8;
%o 4x54 + x43 + x44 + x45 + x53 + x55 + x63 + x64 + x65 < 8;
%o 4x55 + x44 + x45 + x46 + x54 + x56 + x64 + x65 + x66 < 8;
%o 4x56 + x45 + x46 + x47 + x55 + x57 + x65 + x66 + x67 < 8;
%o 4x57 + x46 + x47 + x48 + x56 + x58 + x66 + x67 + x68 < 8;
%o 4x58 + x47 + x48 + x49 + x57 + x59 + x67 + x68 + x69 < 8;
%o 4x59 + x48 + x49 + x410 + x58 + x510 + x68 + x69 + x610 < 8;
%o 4x62 + x51 + x52 + x53 + x61 + x63 + x71 + x72 + x73 < 8;
%o 4x63 + x52 + x53 + x54 + x62 + x64 + x72 + x73 + x74 < 8;
%o 4x64 + x53 + x54 + x55 + x63 + x65 + x73 + x74 + x75 < 8;
%o 4x65 + x54 + x55 + x56 + x64 + x66 + x74 + x75 + x76 < 8;
%o 4x66 + x55 + x56 + x57 + x65 + x67 + x75 + x76 + x77 < 8;
%o 4x67 + x56 + x57 + x58 + x66 + x68 + x76 + x77 + x78 < 8;
%o 4x68 + x57 + x58 + x59 + x67 + x69 + x77 + x78 + x79 < 8;
%o 4x69 + x58 + x59 + x510 + x68 + x610 + x78 + x79 + x710 < 8;
%o 4x72 + x61 + x62 + x63 + x71 + x73 + x81 + x82 + x83 < 8;
%o 4x73 + x62 + x63 + x64 + x72 + x74 + x82 + x83 + x84 < 8;
%o 4x74 + x63 + x64 + x65 + x73 + x75 + x83 + x84 + x85 < 8;
%o 4x75 + x64 + x65 + x66 + x74 + x76 + x84 + x85 + x86 < 8;
%o 4x76 + x65 + x66 + x67 + x75 + x77 + x85 + x86 + x87 < 8;
%o 4x77 + x66 + x67 + x68 + x76 + x78 + x86 + x87 + x88 < 8;
%o 4x78 + x67 + x68 + x69 + x77 + x79 + x87 + x88 + x89 < 8;
%o 4x79 + x68 + x69 + x610 + x78 + x710 + x88 + x89 + x810 < 8;
%o 4x82 + x71 + x72 + x73 + x81 + x83 + x91 + x92 + x93 < 8;
%o 4x83 + x72 + x73 + x74 + x82 + x84 + x92 + x93 + x94 < 8;
%o 4x84 + x73 + x74 + x75 + x83 + x85 + x93 + x94 + x95 < 8;
%o 4x85 + x74 + x75 + x76 + x84 + x86 + x94 + x95 + x96 < 8;
%o 4x86 + x75 + x76 + x77 + x85 + x87 + x95 + x96 + x97 < 8;
%o 4x87 + x76 + x77 + x78 + x86 + x88 + x96 + x97 + x98 < 8;
%o 4x88 + x77 + x78 + x79 + x87 + x89 + x97 + x98 + x99 < 8;
%o 4x89 + x78 + x79 + x710 + x88 + x810 + x98 + x99 + x910 < 8;
%o 4x92 + x81 + x82 + x83 + x91 + x93 + x101 + x102 + x103 < 8;
%o 4x93 + x82 + x83 + x84 + x92 + x94 + x102 + x103 + x104 < 8;
%o 4x94 + x83 + x84 + x85 + x93 + x95 + x103 + x104 + x105 < 8;
%o 4x95 + x84 + x85 + x86 + x94 + x96 + x104 + x105 + x106 < 8;
%o 4x96 + x85 + x86 + x87 + x95 + x97 + x105 + x106 + x107 < 8;
%o 4x97 + x86 + x87 + x88 + x96 + x98 + x106 + x107 + x108 < 8;
%o 4x98 + x87 + x88 + x89 + x97 + x99 + x107 + x108 + x109 < 8;
%o 4x99 + x88 + x89 + x810 + x98 + x910 + x108 + x109 + x1010 < 8;
%o x11 < 1;x12 < 1;x13 < 1;x14 < 1;x15 < 1;x16 < 1;x17 < 1;x18 < 1;x19 < 1;x110 < 1;
%o x21 < 1;x22 < 1;x23 < 1;x24 < 1;x25 < 1;x26 < 1;x27 < 1;x28 < 1;x29 < 1;x210 < 1;
%o x31 < 1;x32 < 1;x33 < 1;x34 < 1;x35 < 1;x36 < 1;x37 < 1;x38 < 1;x39 < 1;x310 < 1;
%o x41 < 1;x42 < 1;x43 < 1;x44 < 1;x45 < 1;x46 < 1;x47 < 1;x48 < 1;x49 < 1;x410 < 1;
%o x51 < 1;x52 < 1;x53 < 1;x54 < 1;x55 < 1;x56 < 1;x57 < 1;x58 < 1;x59 < 1;x510 < 1;
%o x61 < 1;x62 < 1;x63 < 1;x64 < 1;x65 < 1;x66 < 1;x67 < 1;x68 < 1;x69 < 1;x610 < 1;
%o x71 < 1;x72 < 1;x73 < 1;x74 < 1;x75 < 1;x76 < 1;x77 < 1;x78 < 1;x79 < 1;x710 < 1;
%o x81 < 1;x82 < 1;x83 < 1;x84 < 1;x85 < 1;x86 < 1;x87 < 1;x88 < 1;x89 < 1;x810 < 1;
%o x91 < 1;x92 < 1;x93 < 1;x94 < 1;x95 < 1;x96 < 1;x97 < 1;x98 < 1;x99 < 1;x910 < 1;
%o x101 < 1;x102 < 1;x103 < 1;x104 < 1;x105 < 1;x106 < 1;x107 < 1;x108 < 1;x109 < 1;x1010 < 1;
%o int x11,x12,x13,x14,x15,x16,x17,x18,x19,x110,
%o x21,x22,x23,x24,x25,x26,x27,x28,x29,x210,
%o x31,x32,x33,x34,x35,x36,x37,x38,x39,x310,
%o x41,x42,x43,x44,x45,x46,x47,x48,x49,x410,
%o x51,x52,x53,x54,x55,x56,x57,x58,x59,x510,
%o x61,x62,x63,x64,x65,x66,x67,x68,x69,x610,
%o x71,x72,x73,x74,x75,x76,x77,x78,x79,x710,
%o x81,x82,x83,x84,x85,x86,x87,x88,x89,x810,
%o x91,x92,x93,x94,x95,x96,x97,x98,x99,x910,
%o x101,x102,x103,x104,x105,x106,x107,x108,x109,x1010;
%Y Cf. A103139, A189889.
%K nonn,more
%O 1,2
%A _Eugen J. Ionascu_, Aug 12 2008
| 