Gluttony and optimization | science game

Giant Gargantua, engraving by Gustave Doré.

On his peninsula trip last week, if Santa Claus could go from Madrid to any of the other Autonomous Communities, he would, on his first trip, have 14 different possibilities, and from which of them he could go to any of the remaining 13, and so on. respectively, so the possible flight paths would be 14 x 13 x 12… = 14! = 87178291200; Too many, even for the super-powerful Santa Claus, to compare all the itineraries in search of the shortest.

The number of itineraries is greatly reduced if, as it seems reasonable, the sleigh goes from each community to one of the neighboring ones, which means going from Madrid to one of two Castilians, and if Santa Claus chooses Castilla-La Mancha, then he has five possibilities, and then two more If you choose Andalusia… the number of itineraries will be 2 x 5 x 2…, much less than the random number 14 x 13 x 12…

But Santa Claus can reduce his options to one, very reasonable, if he travels from each community to the nearest community (from those not yet visited): from Madrid to Toledo, from Toledo to Merida, from Merida to Seville … In this The way he would implement a “greedy algorithm”.

in acomputer science, voracious algorithm (also known as gluttony, greed, devour, orGreed) is a research strategy consisting of choosing the best option at each step of the process in the hope of obtaining the best overall solution. Omnivorous algorithms are generally used to solve optimization problems, and decisions are made based on the information – or evaluation – that is handled at all times. They are usually quick and easy to use, but they do not always lead to an optimal solution.

See also  Insurance companies choose virtual health coaches and wellness apps -

For example, in the present case, the voracious algorithm of Santa Claus offers a good, but not the best (ie the shortest) path, since the criterion of moving from each community to the nearest community would take him from Valencia to Zaragoza, when the best solution would be to go to Barcelona early to follow The circuit shown in Fig.

By the way, my savvy readers will not escape that the shortest circuit seems to be, paradoxically, the one with the largest surface area. Is it really so? why?

For this itinerary – or any other – the sled team can be configured, with four heterosexual pairs trailing behind Rudolph, in 9216 different ways (4! X 4! X 2⁴).

Grasshopper and chained

And from reindeer to invisible grasshoppers, because last week’s comments section mentioned an interesting unresolved issue as of this writing:

There is an invisible grasshopper at a full point on the real line. The grasshopper jumps either to the right or to the left by an integer every second. We can try to “catch” the grasshopper by placing ourselves every second at a full point on the line. Is there a strategy that will allow us to hunt down the invisible grasshopper sooner or later?

And since we are starting the new year, it is worth taking a look at the number 2022. Do skilled readers discover any interesting properties in it?

And a few simple sequences to end the year without much effort:

2000, 2002, 2020, 2022…

62, 138, 262, 446…

What are the following numbers?

See also  With the cultivation of tilapia, they opened CONCIENTE 2021 at the Caracas Science Museum

Carlo Frappetti Writer, mathematician, and member of the New York Academy of Sciences. He has published more than 50 popular scientific works for adults, children, and youth, including “Damn physics”, “Damn mathematics” and “The great game”. He was the screenwriter of “La bola de cristal”.

You can follow Theme in a Facebook social networking siteAnd Twitter e Instagram, or sign up here to receive Our weekly newsletter.

Leave a Reply

Your email address will not be published. Required fields are marked *