# How much is USA - Brazil?

Given that:

France - China is 4
Morocco - USA is $$+\infty$$
And
Laos - India is 1

Preliminary question Can you give the value of USA - Brazil?

Puzzle question What is the highest finite value that you can achieve for two countries?

EDIT I am clarifying my question thanks to @Victor Stafusa's answer that I upvoted but cannot select as top answer (at least for the moment).

This edit is in spoiler as it would spoil, in particular, the preliminary question.

If I choose, France - Portugal, there is unique number, one, which is the minimum number of countries that I need to cross to go from France to Portugal (it's Spain). Can you give a pair of two countries such that this minimum value, the number of countries needed to go from the two selected countries, is maximized. For instance, France - South Korea seems quite interesting. And Portugal - South Korea, even more!

• puzzle question - do you mean what two countries vice the highest finite result, or is the answer "Fiji - anywhere" Commented Jul 1 at 7:19
• @Jasen, the answer is a pair of country (and its corresponding value which can not be infinity)
– JKHA
Commented Jul 1 at 7:52
• I think Morocco-USA would be better clued as "undefined" rather than "infinity". I don't see a way to frame the problem that makes infinity a suitable answer for any pair of countries - as far as I can see, the answer if it exists must be a whole number. Commented Jul 1 at 18:54
• Because of Russia, Portugal - South Korea is not as interesting as it could be on a first thought. The best is on my edited answer. Commented Jul 4 at 1:48

# First cases

France - China is 4

France, Germany, Poland, Ukraine, Russia and China. - You need to cross at least 4 other countries from France to reach China by land. Also works as France, Germany, Poland, Belarus, Russia and China.

A few notes on that:

Kaliningrad doesn't count because entering an exclave and proceeding as if you've reached the main landmass instead don't work. Otherwise the path would be France, Germany, Poland, Russia, China and the number be 3 instead of 4.

By the same reason, you can't enter mainland France and exit from French Guiana and go to Suriname or Brazil. Also, Ceuta and Melilla don't make you be able to use them to go from Morocco to mainland Spain. Further, you can't go from Singapore to Brunei through Malaysia because Malaysia is composed by two disjoint landmasses.

Hence:

Morroco - USA is +∞

They are completely disjoint landmasses, so there is no way to travel only by land from one to the other.

Laos - India is 1

Laos, Myanmar, India - 1 intermediate country. Also work by using China instead of Myanmar.

USA - Brazil

USA, Mexico, Guatemala, Honduras, Nicaragua, Costa Rica, Panama, Colombia, Brazil - 7 intermediate countries.

Hence, that answers the first question (the value).

# What is going on?

General rule:

The value is the minimum number of intermediate countries by traveling only by land between the two endpoints without visiting the same country twice. If there is no path between them, the value is infinite.

Hence, this is the problem of the shortest distance on a graph between two points. The distance between two points in two disconnected componentes is infinite. The largest value possible is the graph's diameter (by definition).

# Second question

The highest achievable value ever (any two countries) is:

All of Africa, Asia and Europe main landmass excluding island nations and enclaves.

Hence:

Lesotho, South Africa, Mozambique, Tanzania, Kenya, Ethiopia, Sudan, Egypt, Israel, Syria, Turquey, Georgia, Russia, Lithuania, Poland, Germany, France, Spain, Portugal

Counting:

17 intermediate countries.

Proof:

First step:

I used this site to create an undirected graph for Africa, Europe and Asia mainland.

What is that?

It is here (click it to see in full resolution):

So what?

Then I used the site to compute the diameter of the graph, and it outputed that number.

But this could be proven by hand: Note that Russia, Egypt and Israel are connection points, once you remove any of them, the graph becomes disconnected and those are far from its extremities. The graph is really in the form "Everything else on Europe's mainland" - Russia - "Everything else on Asia's mainland" - Israel - Egypt - "Everything else on Africa's mainland".

Hence, you just need to find out the furthest node one Europe from Russia (it is Portugal), the furthest point on Africa from Egypt (it is Lesotho) and the shortest path between Russia and Israel (that is Syria, Turkey and Georgia). There is nothing on Asia that makes it beat either Africa or Europe in graph's size because China and Russia connects to almost everything else on Asia.

Further, France is also one of those connection points, but this only becomes clear after you already know that Portugal is one of the endpoints.

It is two distinct landmasses, one in Europe and one in Asia, because they are separated by a sea strait. But even if we count it as just one thing, the result is the same number because the Balkans are too fragmented to give us a shortcut capable of providing a better number. In the best, it would tie with Turkey, Bulgaria, Serbia, Croatia, Slovenia, Italy and France instead of Turkey, Georgia, Russia, Lithuania, Poland, Germany and France.

# Bonus

The longest path is:

Lesotho, South Africa, Eswatini, Mozambique, Zimbabwe, Botswana, Namibia, Angola, Zambia, Malawi, Tanzania, Kenya, Somalia, Djibouti, Eritrea, Ethiopia, South Sudan, Uganda, Rwanda, Burundi, DRC, Congo, Gabon, Equatorial Guinea, Cameroon, Central African Republic, Sudan, Chad, Niger, Nigeria, Benin, Togo, Ghana, Burkina Faso, Côte d'Ivoire, Liberia, Sierra Leone, Guinea, Guinea-Bissau, Senegal, Mali, Mauritania, Western Sahara (if you consider that a country), Morocco, Algeria, Tunisia, Libya, Egypt, Gaza/Palestine (if you consider that), Israel, Lebanon, Syria, Jordan, Saudi Arabia, Kuwait, Iraq, Turkey, Armenia, Georgia, Azerbaijan, Iran, Turkmenistan, Uzbekistan, Kazakhstan, Kyrgyztan, Tajikistan, Afganisthan, Pakistan, India, Bangladesh, Myanmar, Thailand, Cambodia, Vietnam, Laos, China, Mongolia, Russia, Estonia, Latvia, Lithuania, Belarus, Poland, Czechia, Slovakia, Ukraine, Moldova, Romania, Bulgaria, Greece, Albania, North Macedonia, Kosovo (if you consider that), Serbia, Montenegro, Bosnia-Herzegovina, Croatia, Slovenia, Italy, Switzerland, Liechtenstein, Austria, Germany, Netherlands, Belgium, Luxembourg, France, Andorra, Spain and Portugal.

Counting:

108 to 111 countries (depending on if you count Western Sahara, Gaza/Palestine and Kosovo).

And it is curious because:

The endpoints are the same two countries as the case of the longest shortest path.

We only missed:

Gambia, Monaco, San Marino and Vatican, because they are enclaves or semi-enclaves.

North Korea, it is either that or Mongolia.

South Korea, Qatar and Denmark, they are dead-ends.

Nepal and Bhutan, they are shortcuts that force connection between India and China cutting out the longer middle path through Bangladesh, Myanmar, Thailand, Cambodia, Vietnam and Laos.

Malaysia and Singapore, which is a dead-end.

Finland, Sweden and Norway, which is a dead-end.

Yemen, Oman and United Arab Emirates, which is also a dead-end.

Countries that are isolated in islands.

And that is optimal because:

One endpoint must be in Africa because once you pass through the Egypt-Israel or Egypt-Gaza border, there is no way back around. By that very same reason, the other endpoint must not be in Africa.

The outside-of-Africa endpoint at Portugal, Spain and Andorra is a three countries dead-end and there is no four countries dead-ends, so it is a good choice for an endpoint.

The next possible outside-of-Africa three-country dead-end, Finland, Sweden and Norway, can't be choose because that would make Russia be taken next isolating the rest of the Europe from Asia.

The other outside-of-Africa three-country dead-end, Yemen, Oman and United Arab Emirates endpoint can't be choosen because once you enter Russia, you would split the Rest of Europe from the Rest of Africa-Asia, but you still need to go to Africa missing out the rest of Europe.

Choosing a two-country or one-country dead-end as an endpoint (or putting it on a country that isn't a dead-end) would leave out a three-country endpoint, so it wouldn't be optimal.

The Africa endpoint should be at either Lesotho or Gambia, because they are dead-ends. Choosing either one excludes the other. And we didn't miss any other country in Africa main landmass.

I'm considering that Turkey is composed by two distinct landmasses. But even if it wasn't, we still would at best be able to only choose one of the three-countries endpoints in Europe-Asia and forfeit the other two, so it would still be no better than what we've already got.

• I think the 'puzzle question' at the end is actually asking about any two countries, not just an upper bound for USA-Brazil. You can get an awful lot higher by considering the African, European and Asian countries...
– Stiv
Commented Jun 30 at 22:34
• @Sliv If that is the case, it is done. Commented Jun 30 at 23:01
• Fij - Greenland is this twice infinity? Commented Jul 1 at 7:20
• why are you changing the calculation rules for the second part? shouldn't you be looking for the pair of countries with the longest shortest path Commented Jul 2 at 13:54
• @JKHA I edited the question. Is it ok now? Commented Jul 4 at 1:01