Uzdevums

LV.AMO.2022B.10.5 en lv

Restorānā ieradās pieci deputāti un pirms pusdienām daži no viņiem paspieda viens otram roku. Zināms, ka, ja kādi divi deputāti nepaspieda viens otram roku, tad abi kopā viņi izdarīja vismaz piecus rokasspiedienus. Pierādīt, ka deputātus var sasēdināt ap apaļu galdu tā, lai katrs būtu paspiedis roku abiem saviem blakussēdētājiem!

Hide solution

en lv

Solution-1

First, let us show that out of any three MPs there are at least two who have shaken hands. By contradiction, assume that there are three MPs who have not made any handshakes between them. Take any two of them - they have made at most four handshakes (each with two remaining MPs) - a contradiction. (1)

Secondly, show that each MP has made at least two handshakes. By contradiction, assume that some MP has only done one handshake (or none at all). Denote this MP by \(X\) and one of the MPs with whom he did not shake hands by \(Y\). The MP \(X\) has done at most one handshake, and MP \(Y\) has done at most three handshakes (since he did not shake hands with \(X\)). So together they have made at most \(4\) handshakes - a contradiction. (2)

Thirdly, note that if two Members did not shake hands with each other, then at least one of them shook hands with all the remaining three. Indeed, if both of them would do at most two handshakes, then the pair would made at most \(2+2=4\) handshakes together. (3)

Assume that two MPs did not shake hands with each other. (If they all did, then they can be seated any way.) Seat those two MPs in places \(A\) and \(C\) (see Fig.14). Let us seat in \(C\) the MP who shook hands with everyone else (according to (3) that is certainly the case). We will refer to these two Members as \(A\) and \(C\).

There are two possibilities:

If \(A\) has also shaken hands with all three others, then we'll put the remaining ones in places \(B\), \(D\) and \(E\) so that the two who have shaken hands with each other are sitting in places \(D\) and \(E\) (according to (1) such MPs can be found).
If \(A\) has not shaken hands with somebody else (besides \(C\)), then let us put that deputy in place \(E\) (we will call this deputy \(E\)). Deputy \(A\) has certainly shaken hands with the two remaining MPs (otherwise he would have done just one handshake). Deputy \(E\) has certainly shaken hands with at least one of the remaining two MPs (otherwise \(E\) would have done just one handshake), let's seat this MP in place \(D\). At this point the seating around the table is complete and satisfies the requirements.

Atrisinājums-1

Pirmkārt pamatosim, ka no jebkuriem trīs deputātiem vismaz kādi divi ir paspieduši viens otram roku. Pieņemsim pretējo, ka kādi trīs deputāti nav savā starpā izdarīuši nevienu rokasspiedienu. Paņemsim jebkurus divus no tiem, tad tie kopā ir izdarijuš̌i lielākais četrus rokasspiedienus (katrs ar diviem atlikušajiem deputātiem) - pretruna. (1)

Otrkārt pamatosim, ka katrs deputāts ir izdarijis vismaz divus rokasspiedienus. Pieņemsim pretējo, ka kāds deputāts ir izdarīijs tikai vienu (vai nevienu) rokasspiedienu. Apzīmēsim šo deputātu ar \(X\) un vienu no deputātiem, kam viņš nepaspieda roku, apzīmēsim ar Y. Deputāts \(X\) ir paspiedis roku ne vairāk kā vienu reizi, bet deputāts \(Y\) - ne vairāk kā trīs reizes (jo viņš nepaspieda roku deputātam \(X\)), tātad abi kopā viņi ir paspieduši roku ne vairāk kā 4 reizes - pretruna. (2)

Treškārt ievērosim, ka, ja kādi divi deputāti nepaspieda viens otram roku, tad vismaz viens no viniem paspieda roku visiem trim pārējiem (ja abiem būtu kāds "izlaists" rokasspiediens, tad abiem kopā būtu lielākais \(2+2=4\) rokasspiedieni). (3)

Pieņemsim, ka kādi divi deputāti nepaspieda viens otram roku (ja visi paspieda, tad tos var sēdināt patvalīgi) un nosēdināsim tos vietās \(A\) un \(C\) (skat. 14. att.), vietā \(C\) sēdināsim to, kurš paspieda roku visiem pārējiem (no (3) tāds noteikti ir). Turpmāk šos divus deputātus sauksim par \(A\) un \(C\).

Iespējami divi gadīumi:

ja arī \(A\) ir paspiedis roku visiem trim pārējiem, tad atlikušos nosēdināsim vietās \(B\), \(D\) un \(E\) tā, lai vietās \(D\) un \(E\) sēdētu kādi, kas ir paspieduši viens otram roku (no (1) tādi noteikti ir). Ar to prasītais būtu panākts.
ja \(A\) nav paspiedis roku vēl kādam deputātam, tad nosēdināsim to vietā \(E\) (un turpmāk sauksim par deputātu \(E\)). Deputāts \(A\) noteikti ir paspiedis roku abiem atlikušajiem deputātiem (citādi viņš būtu izdarījis tikai vienu rokasspiedienu). Deputāts \(E\) noteikti ir paspiedis roku vismaz vienam no atlikušajiem diviem deputātiem (citādi \(E\) būtu izdarīis tikai vienu rokasspiedienu), šo deputātu nosēdināsim vietā \(D\). Redzams, ka ar šo prasītais ir panākts.