# The task of the G50 summit and handshakes

Representatives of fifty states gathered at the Big Fifties Summit. Each state was attended by a president and prime minister. In the interval between [discussions], the participants exchanged diplomatic handshakes, and since the handshakes were made for diplomatic purposes, not a single president shook hands with the prime minister of his country.

At a dinner party dedicated to the closing of the summit, the president of Anchuria interviewed all the participants who made many handshakes, and did not receive a single repeated answer. How many handshakes did the prime minister of Anchuria make?

As it turned out, the problem has a unique solution.

Leaving aside the discussion of “alternative” methods of recruiting (as well as the fact that the solution was “embedded” in the javascript page), we will try to solve the problem for real.

In the photo: a picture from Wikipedia on request G50

I hope that by this time everyone managed to try to solve it on their own (and someone even succeeded in this).

So, we have a total of 100 participants. Possible handshake values ​​range from 0 (obviously) to 98 (because no one shakes hands with himself and PR and PM of one country do not shake hands with each other). Only 99 values.
According to the Dirichlet principleat least one handshake value is repeated twice. However, according to the condition, all participants told PR Anchuria different numbers. Trusting their honesty and accuracy of the calculation, we come to the first conclusion : the PR of Anchuria itself has a number of handshakes equal to the number of handshakes of one of the participants (of course, we assume that the presidents do not suffer from schizophrenia and do not interrogate themselves; otherwise, the task condition is simply impossible to implement )

Further, we note that we still have 99 participants and 99 different numbers. This means that each number is present exactly once, i.e. there is a participant without handshakes, with 1 handshake, etc. up to 98.

Take a participant with 98 handshakes. Obviously, he shook hands with everyone, everything except himself and his compatriot (since PRs do not shake hands with their PM). Without loss of generality, let us assume that this is PR. Then it is clear that his PM is the participant with the number 0 (because our PR shook hands with everyone except him, i.e. everyone has at least 1 handshake).
We will call these comrades PR98 and ПМ0 (remember that they are from the same country).

We continue the argument by considering PR97. He did not shake hands with his PM, himself, as well as PM0 (everyone deprived him of attention). All the others already have at least two handshakes (from PR98 and PR97). As a result, it turns out that the only participant who received one handshake is only the PM from the same country as PR97. Of course, let's call it PM1.

Continuing the chain of reasoning in this way, we find that PR and PM from one country are always called 98 handshakes in total (this is our second conclusion ).

Now inevitably we find that the only possible number repeated here is the middle of our converging chain, i.e. 49. Half of the chain is built “from above” from 98 down, and each number can be present only once. The other half is constructed from the bottom up from 0, and also all the elements are filled unambiguously. The only possible repetition is the coincidence of numbers when the chains converge (naturally, they converge in the middle of 98, i.e., on the number 49):
`[0, 1, 2, ... 48, 49]`and
`[98, 97, 96, ... 50, 49]`
And since it follows from the first conclusion that the PR of Anchuria has the same number of handshakes as the other participant, we get that he is PR49. From the second conclusion it follows that the PM of Anchuria shook hands (98-49 = 49) with the participants of the summit.

PS The author of the task, Maria Fedotova maashaa , in a private correspondence expressed a claim that I copied the material from the site without indicating a link to it. Corrected: task taken from here .