Voracity and optimization

On his peninsular journey last week, if Santa Claus could go from Madrid to any other of the autonomous communities, he would have, on his first trip, 14 different possibilities, and from any of them he could go to any of the remaining 13, and so on. successively, so the possible itineraries would be 14 x 13 x 12… = 14!

= 87,178,291,200;

Too high a number, even for the super-powerful Santa Claus, to compare all the itineraries in search of the shortest.

The number of itineraries is drastically reduced if, as seems reasonable, the sled goes from each community to one of the neighboring communities, which means going from Madrid to one of the two Castiles, and if Santa Claus chooses Castilla-La Mancha then he has five possibilities, and then another two if I chose Andalusia ... The number of itineraries would be 2 x 5 x 2 ..., well below the indiscriminate 14 x 13 x 12 ...

But Santa Claus could reduce his options to one, very reasonable, if from each community he traveled to the nearest one (of those not yet visited): from Madrid to Toledo, from Toledo to Mérida, from Mérida to Seville ... In this way he would be applying a "greedy algorithm".

In computer science, a voracious algorithm (also known as gluttonous, greedy, devouring, or 

) is a search strategy that involves choosing the best option at each step of the process in hopes of obtaining the best overall solution. Voracious algorithms are generally used to solve optimization problems, and decisions are made based on the information - or the assessment - that is handled at all times. They are usually quick and easy to use, but they do not always lead to the optimal solution.

For example, in the present case, the voracious algorithm offers Santa Claus a good itinerary, but not the best (that is, the shortest), since the criterion of going from each community to the closest one would take him from Valencia to Zaragoza, when a better solution would be to go to Barcelona earlier to follow the circuit outlined in the figure.

By the way, my astute readers will not have escaped that the shortest circuit seems to be, paradoxically, the one that encloses a greater surface area.

Is it really so?

Why?

For this itinerary - or any other - the sled team can be formed, so that four heterosexual couples go behind Rudolph, in 9,216 different ways (4! X 4! X 2⁴).

A grasshopper and two sequences

And from flying reindeer to invisible grasshoppers, because last week's comment section mentioned an interesting problem that remains unsolved as of this writing:

There is an invisible grasshopper at a whole point on the real line.

The grasshopper jumps either to the right or to the left, an integer amount every second.

We can try to “hunt” the grasshopper by positioning ourselves every second at a whole point on the line.

Is there a strategy that allows us to hunt down the invisible grasshopper sooner or later?

And since we are launching the new year, it is worth taking a look at number 2022. Do my astute readers detect any interesting property in it?

And a couple of simple sequences to finish the year without trying too hard:

2000, 2002, 2020, 2022 ...

62, 138, 262, 446 ...

What are the following numbers?

Carlo Frabetti

You can follow