Oh! You count countries that are only adjacent at corners as neighbours? That changes things a lot. (And surely isn’t the usual definition.) I think you should make that explicit in the statement of the problem.
It doesn’t count in the discussions of coloring graphs, such as in the four color map theorem, and that’s the kind of math this is most similar to. So you really need to specify.
Tvira gung pbhagevrf ner nyybjrq gb zrrg ng gurve pbearef V oryvrir gur fbyhgvba vf avargrra pbhagevrf, naq V pna cebir vg ba bar fznyy pbaqvgvba.
Yrg gur ahzore bs a-ghcyl ynaqybpxrq pbhagevrf or nv sbe v terngre guna be rdhny gb mreb, n0 orvat gur ahzore bs pbhagevrf ba gur pbnfg. Fvapr pbhagevrf ner nyybjrq gb zrrg ng gurve pbearef vg’f rnfl gb znxr n znc jurer nyy a-ghcyl ynaqybpxrq pbhagevrf zrrg nyy gur (a+1)-ghcyl ynaqybpxrq pbhagevrf (sbe rknzcyr unir nyy pbhagevrf orvat pbapragevp evatf, naq gura sbe rnpu a unir n “cvapu” jurer nyy gur a-ghcyl naq (a+1)-ghcyl ynaqybpxrq pbhagevrf zrrg ng n fvatyr cbvag). Pyrneyl ab fbyhgvba pna or znqr jbefr ol nqqvat fhpu obeqref, naq urapr jr pna nffhzr gur fbyhgvba unf guvf sbez. Fb vg erznvaf gb svaq ahzoref nv fhpu gung gur pbaqvgvbaf va gur ceboyrz ner fngvfsvrq.
Yrg hf nffhzr gung n6=1 naq gung nv=0 sbe v>6 (guvf vf gur fznyy pbaqvgvba gung V pnaabg cebir). Gur gbgny ahzore bs pbhagevrf vf gur fhz bs gur nv, naq gur gbgny ahzore bs arvtuobhef vf gur fhz bire v bs nv(n(v-1)+nv+n(v+1)-1). Jr unir fvk ahzoref (anzryl gur nv sbe v orgjrra mreb naq svir) gung jr jvfu gb bcgvzvfr. Yrg hf gel gb svaq gur bcgvzny inyhrf bs gurfr nv nzbat gur erny ahzoref. Guvf jvyy tvir hf n ybjre obhaq ba gur ahzore bs pbhagevrf arrqrq, fvapr nal vagrtre fbyhgvba jvyy nyfb or n erny fbyhgvba. Jr pna nffhzr gur nirentr ahzore bs arvtuobhef vf pbafgenvarq gb or rknpgyl fvk, fvapr nal fbyhgvba jvgu gur nirentr terngre guna guvf pna or vzcebirq ol erqhpvat nal bs gur nv.
Fbyivat gur ceboyrz hfvat Yntenatr zhygvcyvref tvirf gung gur fhz bs gur nv vf ng yrnfg 18.53. Urapr gur zvavzhz cbffvoyr vagrtre fbyhgvba vf avargrra. Va snpg guvf vf npuvrinoyr, sbe rknzcyr gnxvat gur nv gb or (va beqre bs vapernfvat v) svir, gjb, guerr, gjb, gjb, sbhe, bar. Guvf fbyhgvba (naq fbzr bgure fbyhgvbaf) pna or sbhaq arne gur erny ahzore fbyhgvba.
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.
A math problem which a child can understand. But who can solve it?
https://protokol2020.wordpress.com/2017/01/29/a-topological-problem/
My immediate reaction, without actually doing any calculation or diagram-drawing or whatever, is:
Jnvg, jung?, qbrfa’g gur nirentr ahzore bs arvtuobhef unir gb or fgevpgyl yrff guna 6 sbe ernfbaf qrevivat sebz Rhyre’f sbezhyn? Vs fb, gur nafjre vf gung gur fvghngvba qrfpevorq vf vzcbffvoyr, ertneqyrff bs ubj znal ynlref bs ynaqybpx lbh unir.
But the fuzzy combination of intuition and hazy memory that tells me that may be all wrong.
Well, imagine the chessboard. There are 36 fields with 8 neighbours, 24 with 5 neighbours, and 4 with 3 neighbours.
Which gives you an average greater than 6.
There is a quadripoint between Botswana, Namibia, Zambia and Zimbabwe, for example.
Oh! You count countries that are only adjacent at corners as neighbours? That changes things a lot. (And surely isn’t the usual definition.) I think you should make that explicit in the statement of the problem.
Perhaps, but it follows.
It happens also at the Game of Life by Conway, at the game of chess and at many related games, as well as in real life geography.
It doesn’t count in the discussions of coloring graphs, such as in the four color map theorem, and that’s the kind of math this is most similar to. So you really need to specify.
Okay. The next time I’ll be more careful to eliminate any possible ambiguity in advance.
Tvira gung pbhagevrf ner nyybjrq gb zrrg ng gurve pbearef V oryvrir gur fbyhgvba vf avargrra pbhagevrf, naq V pna cebir vg ba bar fznyy pbaqvgvba.
Yrg gur ahzore bs a-ghcyl ynaqybpxrq pbhagevrf or nv sbe v terngre guna be rdhny gb mreb, n0 orvat gur ahzore bs pbhagevrf ba gur pbnfg. Fvapr pbhagevrf ner nyybjrq gb zrrg ng gurve pbearef vg’f rnfl gb znxr n znc jurer nyy a-ghcyl ynaqybpxrq pbhagevrf zrrg nyy gur (a+1)-ghcyl ynaqybpxrq pbhagevrf (sbe rknzcyr unir nyy pbhagevrf orvat pbapragevp evatf, naq gura sbe rnpu a unir n “cvapu” jurer nyy gur a-ghcyl naq (a+1)-ghcyl ynaqybpxrq pbhagevrf zrrg ng n fvatyr cbvag). Pyrneyl ab fbyhgvba pna or znqr jbefr ol nqqvat fhpu obeqref, naq urapr jr pna nffhzr gur fbyhgvba unf guvf sbez. Fb vg erznvaf gb svaq ahzoref nv fhpu gung gur pbaqvgvbaf va gur ceboyrz ner fngvfsvrq.
Yrg hf nffhzr gung n6=1 naq gung nv=0 sbe v>6 (guvf vf gur fznyy pbaqvgvba gung V pnaabg cebir). Gur gbgny ahzore bs pbhagevrf vf gur fhz bs gur nv, naq gur gbgny ahzore bs arvtuobhef vf gur fhz bire v bs nv(n(v-1)+nv+n(v+1)-1). Jr unir fvk ahzoref (anzryl gur nv sbe v orgjrra mreb naq svir) gung jr jvfu gb bcgvzvfr. Yrg hf gel gb svaq gur bcgvzny inyhrf bs gurfr nv nzbat gur erny ahzoref. Guvf jvyy tvir hf n ybjre obhaq ba gur ahzore bs pbhagevrf arrqrq, fvapr nal vagrtre fbyhgvba jvyy nyfb or n erny fbyhgvba. Jr pna nffhzr gur nirentr ahzore bs arvtuobhef vf pbafgenvarq gb or rknpgyl fvk, fvapr nal fbyhgvba jvgu gur nirentr terngre guna guvf pna or vzcebirq ol erqhpvat nal bs gur nv.
Fbyivat gur ceboyrz hfvat Yntenatr zhygvcyvref tvirf gung gur fhz bs gur nv vf ng yrnfg 18.53. Urapr gur zvavzhz cbffvoyr vagrtre fbyhgvba vf avargrra. Va snpg guvf vf npuvrinoyr, sbe rknzcyr gnxvat gur nv gb or (va beqre bs vapernfvat v) svir, gjb, guerr, gjb, gjb, sbhe, bar. Guvf fbyhgvba (naq fbzr bgure fbyhgvbaf) pna or sbhaq arne gur erny ahzore fbyhgvba.
EDIT: Here’s a picture of such an island: http://i157.photobucket.com/albums/t43/Macbi/sextuplylandlocked.png?t=1485712658
Can you do even better?
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.