Ponder This

December 2013 - Solution

<< November DecemberJanuary >>

December 2013 Challenge

December 2013 Solution:

The simplest solution is a star with four vertices:

1111
1100
1010
1001

This gives 9/16 = 56.25%

The best solution with up to eight vertices is structured like an Ethane molecule (C2H6), which gives 631/1120 =~ 56.339%

10010000
01010000
00110000
11111000
00001111
00001100
00001010
00001001

And there are slightly better solutions: a cycle of length 5 with 3 extra nodes connected to every one of its vertices:

11001111000000000000
11100000111000000000
01110000000111000000
00111000000000111000
10011000000000000111
10000100000000000000
10000010000000000000
10000001000000000000
01000000100000000000
01000000010000000000
01000000001000000000
00100000000100000000
00100000000010000000
00100000000001000000
00010000000000100000
00010000000000010000
00010000000000001000
00001000000000000100
00001000000000000010
00001000000000000001

which gives 81215/144144 = ~56.342%.