Nyy gung erznvaf vf gb cebir zl nffhzcgvba gung gurer ner ab frcghcyl be jbefr ynaqybpxrq pbhagevrf, naq gung gurer vf bayl bar frkghcyl ynaqybpxrq pbhagel. Ohg V whfg ernyvfrq guvf vf boivbhf. Nal frcghcyl be jbefr ynaqybpxrq pbhagel pna or ghearq vagb n frkghcyl ynaqybpxrq bar naq gur fbyhgvba vf fgevpgyl vzcebirf. Yvxrjvfr nyy ohg bar frkghcyl ynaqybpxrq pbhagel pna or ghearq vagb n craghcyl ynaqybpxrq bar.
Work in your variable setup with a0 through a6. You were wondering how to handle countries that are more than sextuply-landlocked; I think the easiest way is to dump them into a6 regardless of how excessively landlocked they are. We want to prove that if a0,...,a6 >= 1 and a0+...+a6 ⇐ 12, then the sum of ai(a(i-1)+ai+a(i+1)-1) is smaller than 6*(a0+...+a6). A simple way to do that is to enumerate all possible tuples, which took a few minutes of programming for me and a few milliseconds of runtime on my computer.
You can also work out a proof without a computer using the technique of “smoothing” (or anti-smoothing, rather). Suppose we have fixed a0+...+a6 and want to maximize the sum of ai(a(i-1)+ai+a(i+1)-1); we do this in order to show this maximum isn’t large enough. You may as well have a0 = 1 because anything in a0 is more productive in a1; it is adjacent to strictly more things. (In other words, replace (a0,a1) with (1,a0+a1-1).) The symmetric logic applies to a6 = 1.
Now that we have a0 = 1, consider the effect of replacing (a1,a2) with (1,a1+a2-1). One may compute that this increases our sum by 2(a1-1)(a3-1), or in other words, doesn’t decrease it. The same logic applies when a0 = a1 = 1 and we continue to push stuff over. The final result is that for any given sum a0+...+a6, the maximum sum can be achieved with a0 = a1 = a2 = a3 = a4 = a6 = 1 and a5 free. (In fact, the maximum is achieved whenever there are one or two consecutive ais other than a0 and a6 that are not 1.) Finally, you just check that a0+..+a6 ⇐ 12 doesn’t work.
The same logic implies that when a0+...+a6 = 13, the only way you can have an average of at least 6 is if its exactly 6.
The question is, whether this 13 is the minimal number indeed. And the question is, whether there is a solution with an average number of neighbors greater than just 6.
I plan to output all the solutions up to some number. They will be conjectures like this one, open for an improvement, or for a proof.
Nyy gung erznvaf vf gb cebir zl nffhzcgvba gung gurer ner ab frcghcyl be jbefr ynaqybpxrq pbhagevrf, naq gung gurer vf bayl bar frkghcyl ynaqybpxrq pbhagel. Ohg V whfg ernyvfrq guvf vf boivbhf. Nal frcghcyl be jbefr ynaqybpxrq pbhagel pna or ghearq vagb n frkghcyl ynaqybpxrq bar naq gur fbyhgvba vf fgevpgyl vzcebirf. Yvxrjvfr nyy ohg bar frkghcyl ynaqybpxrq pbhagel pna or ghearq vagb n craghcyl ynaqybpxrq bar.
It’s less than that. There is something wrong with your assumptions.
Bxnl, abj V’ir sbhaq n fbyhgvba jvgu bayl guvegrra pbhagevrf. Gurer’f bayl bar a-ghcyl ynaqybpxrq pbhagel sbe rnpu a, rkprcg sbe fbzr inyhr bs a orgjrra bar naq svir sbe juvpu gurer ner frira a-ghcyl ynaqybpx pbhagevrf. V thrff gur fbyhgvba V sbhaq orsber jnf n fgngvbanel cbvag ohg abg n tybony bcgvzhz, bbcf. (Vg’f cebonoyl gur tybony crffvzhz tvira gung rnpu pbhagel obeqref fvk ba nirentr naq rnpu a-ghcyl ynaqybpxrq bar obeqref rnpu (a+1)-ghcyl ynaqybpxrq bar.)
V’z abg fher ubj gb cebir zl arj fbyhgvba vf bcgvzny.
EDIT: Image of new attempt: http://i157.photobucket.com/albums/t43/Macbi/sextuplylandlocked2.png
The image is in order.
Of 13 states, 9 states have 8 neighbours each. 2 have 2 neighbours each. And 2 have only 1 neighbour. 98+22+2*1=78.
And 78/13=6, which is the average number of neighbours at least required. Well done.
Do you have a proof that 13 is optimal? I can’t think of one.
Work in your variable setup with a0 through a6. You were wondering how to handle countries that are more than sextuply-landlocked; I think the easiest way is to dump them into a6 regardless of how excessively landlocked they are. We want to prove that if a0,...,a6 >= 1 and a0+...+a6 ⇐ 12, then the sum of ai(a(i-1)+ai+a(i+1)-1) is smaller than 6*(a0+...+a6). A simple way to do that is to enumerate all possible tuples, which took a few minutes of programming for me and a few milliseconds of runtime on my computer.
You can also work out a proof without a computer using the technique of “smoothing” (or anti-smoothing, rather). Suppose we have fixed a0+...+a6 and want to maximize the sum of ai(a(i-1)+ai+a(i+1)-1); we do this in order to show this maximum isn’t large enough. You may as well have a0 = 1 because anything in a0 is more productive in a1; it is adjacent to strictly more things. (In other words, replace (a0,a1) with (1,a0+a1-1).) The symmetric logic applies to a6 = 1.
Now that we have a0 = 1, consider the effect of replacing (a1,a2) with (1,a1+a2-1). One may compute that this increases our sum by 2(a1-1)(a3-1), or in other words, doesn’t decrease it. The same logic applies when a0 = a1 = 1 and we continue to push stuff over. The final result is that for any given sum a0+...+a6, the maximum sum can be achieved with a0 = a1 = a2 = a3 = a4 = a6 = 1 and a5 free. (In fact, the maximum is achieved whenever there are one or two consecutive ais other than a0 and a6 that are not 1.) Finally, you just check that a0+..+a6 ⇐ 12 doesn’t work.
The same logic implies that when a0+...+a6 = 13, the only way you can have an average of at least 6 is if its exactly 6.
The question is, whether this 13 is the minimal number indeed. And the question is, whether there is a solution with an average number of neighbors greater than just 6.
I plan to output all the solutions up to some number. They will be conjectures like this one, open for an improvement, or for a proof.
Something like this:
http://mathworld.wolfram.com/JohnsonSolid.html
Is your average 6 exactly?
Yeah.
Congratulations!
That’s better.