A B. 5246. feladat (2022. május)

B. 5246. 14 ember ül egy asztal körül, mindenki kék vagy sárga pólóban. Legfeljebb hány emberre teljesülhet, hogy a két szomszédja különböző színű pólóban van?

(3 pont)

A beküldési határidő 2022. június 10-én LEJÁRT.

Megoldás. Megmutatjuk, hogy ez legfeljebb 12 emberre teljesülhet.

Ha például a pólók színe sorrendben: K, K, S, S, K, K, S, S, K, K, S, S, K, K (ahol K: kék, S: sárga), akkor a felsorolás szerinti 1. és 14. ember kivételével mindenkinek különböző színű pólóban ülnek a szomszédjai, az 1. és a 14. ember pólójának színe viszont egyforma (kék). (Az 1. és a 14. is szomszédosak.)

Tekintsük az előbbi felsorolás szerinti páratlan sorszámú helyeken ülőket. Az ő pólójuk színe határozza meg, hogy a páros sorszámúak közül kikre teljesül a feltétel. A \(\displaystyle (2k)\)-as sorszámú emberre pontosan akkor teljesül a feltétel, ha a \(\displaystyle (2k-1)\)-edik és a \(\displaystyle (2k+1)\)-edik pólójának színe különböző. (A sorszámozást ciklikusan értve: a 15. sorszám az 1.) Így, ha megszámoljuk, hogy az 1., 3., 5., 7., 9., 11., 13., 1. embereken végighaladva hány színváltás van, megkapjuk a feltételt teljesítő páros sorszámúak számát. Mivel ez egy 7 hosszú kör, ezért mind a 7 esetben nem lehet színváltás, tehát legfeljebb hat páros sorszámú emberre teljesülhet a feltétel. Ugyanez igaz fordítva is, a páratlan sorszámúak közül is legfeljebb hatra teljesülhet a feltétel.

Így legfeljebb \(\displaystyle 6+6=12\) emberre teljesülhet, hogy a két szomszédja különböző színű pólóban van.

Megjegyzés. A 12-es felső becslést a következő módon is indokolhatjuk. A pólók színét kódoljuk egy 14 hosszú 0-1-sorozattal, melynek \(\displaystyle i\)-edik eleme, \(\displaystyle a_i\) legyen 0 vagy 1 aszerint, hogy a megfelelő ember pólójának színe kék vagy piros. Ekkor a feltételt kielégítő emberek száma

\(\displaystyle S:=\sum\limits_{i=1}^{14} |a_{i-1}-a_{i+1}|,\)

ahol \(\displaystyle a_0:=a_{14}\) és \(\displaystyle a_{15}:=a_1\). Mivel

\(\displaystyle S_1:=|a_{14}-a_2|+|a_2-a_4|+|a_4-a_6|+|a_6-a_8|+|a_8-a_{10}|+|a_{10}-a_{12}|+|a_{12}-a_{14}|\leq 7\)

és

\(\displaystyle S_2:=|a_{1}-a_3|+|a_3-a_5|+|a_5-a_7|+|a_7-a_9|+|a_9-a_{11}|+|a_{11}-a_{13}|+|a_{13}-a_{1}|\leq 7\)

egyaránt párosak (az abszolút értékek elhagyása nem változtat az összeg paritásán, így viszont mindkét összeg 0-vá válik), ezért \(\displaystyle S= S_1+S_2\leq6+6=12\).

Statisztika:

81 dolgozat érkezett.
3 pontot kapott:	67 versenyző.
2 pontot kapott:	6 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2022. májusi matematika feladatai