Problem about the G50 summit and handshake
My friend received a letter from the recruiter, leading to the site with such a problem:
As it turned out, the problem has the only solution.
You can easily find the link to the site in Google.
Leaving aside the discussion of “alternative” recruiting methods (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 some even succeeded in this).
')
So, we have a total of 100 participants. Possible values ​​for handshakes are in the range from 0 (obviously) to 98 (since nobody shakes hands with themselves and PR and PM of one country do not shake hands with each other). A total of 99 values.
According to the Dirichlet principle, at least one value of handshakes is repeated twice. However, according to the condition, all participants reported different numbers to the Anchuria PR. Trusting in their honesty and accuracy of calculation, we come to the first conclusion : the PR 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 all-all, except himself and his compatriot (since PR does not shake hands with its PM). Without loss of generality, assume that this PR Then it is clear that his PM is the participant with the number 0 (because our PR shook hands with everyone except him, that is, everyone has at least 1 handshake).
Let's call these comrades PR98 and PM0 (remember, they are from the same country).
Continue the argument by examining PR97. He did not shake the hand of his PM, himself, as well as PM0 (everyone deprived him of his 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 PM from the same country as PR97. Of course, let's call it PM1.
Continuing in this way the chain of reasoning, we find that the PR and PM from one country are always called a total of 98 handshakes (this is our second conclusion ).
Now we will inevitably find that the only possible number that is 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 upwards from 0, and all the elements are also unequivocally filled. The only possible repetition is the coincidence of numbers when the chains converge (naturally, they will converge in the middle of 98, that is, on the number 49):
And since from the first conclusion it follows that the PR of Anchuria has the number of handshakes the same as that of the other participant, then we get that he is PR49. From the second conclusion it follows that PM Anchurii also shook hands (98-49 = 49) to the summit participants.
PS The author of the problem, Maria Fedotova, maashaa , in a private correspondence expressed a claim that I copied the material from the site, without indicating the link to it. Correcting: the task is taken from here .
The summit of the Big 50 brought together representatives of fifty states. From each state attended the president and prime minister. During the break between [the discussions], the participants exchanged diplomatic handshakes, while, as the handshakes were performed for diplomatic purposes, not a single president shook hands with his prime minister.
At the dinner party dedicated to the closing of the summit, the President of Anchurii interviewed all participants who had done so many handshakes and did not receive a single repetitive answer. How many handshakes did Anchuria’s prime minister have?
As it turned out, the problem has the only solution.
You can easily find the link to the site in Google.
Leaving aside the discussion of “alternative” recruiting methods (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 some even succeeded in this).
')
So, we have a total of 100 participants. Possible values ​​for handshakes are in the range from 0 (obviously) to 98 (since nobody shakes hands with themselves and PR and PM of one country do not shake hands with each other). A total of 99 values.
According to the Dirichlet principle, at least one value of handshakes is repeated twice. However, according to the condition, all participants reported different numbers to the Anchuria PR. Trusting in their honesty and accuracy of calculation, we come to the first conclusion : the PR 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 all-all, except himself and his compatriot (since PR does not shake hands with its PM). Without loss of generality, assume that this PR Then it is clear that his PM is the participant with the number 0 (because our PR shook hands with everyone except him, that is, everyone has at least 1 handshake).
Let's call these comrades PR98 and PM0 (remember, they are from the same country).
Continue the argument by examining PR97. He did not shake the hand of his PM, himself, as well as PM0 (everyone deprived him of his 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 PM from the same country as PR97. Of course, let's call it PM1.
Continuing in this way the chain of reasoning, we find that the PR and PM from one country are always called a total of 98 handshakes (this is our second conclusion ).
Now we will inevitably find that the only possible number that is 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 upwards from 0, and all the elements are also unequivocally filled. The only possible repetition is the coincidence of numbers when the chains converge (naturally, they will converge in the middle of 98, that is, on the number 49):
[0, 1, 2, ... 48, 49] and[98, 97, 96, ... 50, 49]And since from the first conclusion it follows that the PR of Anchuria has the number of handshakes the same as that of the other participant, then we get that he is PR49. From the second conclusion it follows that PM Anchurii also shook hands (98-49 = 49) to the summit participants.
PS The author of the problem, Maria Fedotova, maashaa , in a private correspondence expressed a claim that I copied the material from the site, without indicating the link to it. Correcting: the task is taken from here .
Source: https://habr.com/ru/post/163927/
All Articles