Sākums

LV.SOL.1999.11.5   lv

Apspriedē piedalās \(9\) dalībnieki. Neviens nepārvalda vairāk nekā trīs valodas. Starp katriem trim dalībniekiem var atrast divus, kas zina kopīgu valodu. Pierādīt, ka ir tāda valoda, kuru prot vismaz \(3\) apspriedes dalībnieki.

Hide solution

Atrisinājums

Pieņemsim pretējo, ka nevienu valodu nezina vairāk par \(2\) dalībniekiem. Tad dalībniekam \(A\) ir kopīga valoda ar augstākais \(3\) citiem dalībniekiem; tātad var atrast \(5\) dalībniekus \(B\), \(C\), \(D\), \(E\), \(F\), kam nav kopīgas valodas ar \(A\). Apskatot trijnieku \((A,B,C)\) redzam, ka \(B\) un \(C\) ir kopīga valoda. Līdzīgi iegūstam, ka \(B\) ir kopīga valoda arī ar \(D\), \(E\), \(F\). Tātad \(B\) ir kopīga valoda ar četriem citiem dalībniekiem. Tā kā \(B\) zina ne vairāk kā \(3\) valodas, tad ar kādiem diviem no šiem četriem viņš zina vienu un to pašu valodu, un šo valodu zina vismaz \(3\) dalībnieki. Iegūta pretruna.