Problem B. 5246. (May 2022)

B. 5246. There are 14 people sitting around a table. Each of them is wearing either a blue shirt or a yellow shirt. What is the maximum possible number of people who have adjacent neighbors with shirts of different color?

(3 pont)

Deadline expired on June 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

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\).

Statistics:

81 students sent a solution.
3 points:	67 students.
2 points:	6 students.
1 point:	5 students.
0 point:	2 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, May 2022