December 2013
<<November December January>>
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%.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com