A B. 5084. feladat (2020. február)

B. 5084. Legyen $\displaystyle n$ pozitív egész szám, és legyen $\displaystyle \mathcal{S}$ az $\displaystyle n$ hosszú $\displaystyle 0-1-2$ sorozatok halmaza. Határozzuk meg, hogy mely $\displaystyle \emptyset\ne A\subseteq \mathcal{S}$ halmazok rendelkeznek a következő tulajdonsággal: bárhogyan is választunk egy

$\displaystyle (c_1,c_2,\ldots,c_n)\in \mathcal{S}\setminus \big\{(0,0,\ldots,0)\big\}$

vektort, az $\displaystyle A$ halmaz egy véletlenszerűen választott $\displaystyle (a_1,a_2,\ldots,a_n)$ elemére a $\displaystyle c_1a_1+c_2a_2+\ldots+c_na_n$ szorzatösszegnek $\displaystyle 1/3$–$\displaystyle 1/3$ valószínűséggel lesz $\displaystyle 0$, $\displaystyle 1$, illetve $\displaystyle 2$ a hármas maradéka.

Kürschák feladat alapján

(6 pont)

A beküldési határidő 2020. március 10-én LEJÁRT.

Megoldás. Számoljuk meg kétféleképpen, hogy hány olyan $\displaystyle (a,b,c)$ rendezett hármas van, melyre $\displaystyle a=(a_1,a_2,\dots,a_n)$ és $\displaystyle b=(b_1,b_2,\dots,b_n)$ az $\displaystyle A$ halmaz két különböző eleme, $\displaystyle c=(c_1,c_2,\dots,c_n)$ pedig egy olyan 0-1-2 sorozat, melynek nem minden eleme 0, továbbá teljesül, hogy

$\displaystyle a_1c_1+a_2c_2+\dots+a_nc_n\equiv b_1c_1+b_2c_2+\dots+b_nc_n \pmod{3}.$

Legyen $\displaystyle |A|=t$. Először $\displaystyle a$ és $\displaystyle b$ megválasztásával kezdjük: $\displaystyle a$-ra $\displaystyle t$ lehetőség van, ezután $\displaystyle b$-re $\displaystyle t-1$, hiszen $\displaystyle a\ne b\in A$. Az a kérdés, hogy hány olyan nem-csupa-0 $\displaystyle c\in \mathcal{S}$ sorozat van, melyre $\displaystyle (a_1-b_1)c_1+(a_2-b_2)c_2+\dots+(a_n-b_n)c_n$ osztható 3-mal. Mivel $\displaystyle a\ne b$, ezért van olyan $\displaystyle 1\leq i\leq n$, melyre $\displaystyle a_i\ne b_i$. Ekkor az $\displaystyle (a_i-b_i)\cdot 0,(a_i-b_i)\cdot 1,(a_i-b_i)\cdot 2$ számok 3-as maradéka páronként különböző, így tetszőleges $\displaystyle c_1,c_2,\dots,c_{i-1},c_{i+1},\dots,c_n$ mellett a $\displaystyle (c_1,\dots,c_{i-1},0,c_{i+1},\dots,c_n),(c_1,\dots,c_{i-1},1,c_{i+1},\dots,c_n),(c_1,\dots,c_{i-1},2,c_{i+1},\dots,c_n)$ sorozatok közül pontosan az egyikre lesz az $\displaystyle (a_1-b_1)c_1+(a_2-b_2)c_2+\dots+(a_n-b_n)c_n$ szám 3-mal osztható. Vagyis az $\displaystyle \mathcal{S}$-beli sorozatoknak pontosan a harmadára teljesül a feltétel, közülük azonban a csupa-0 sorozatot kizártuk, így a megfelelő $\displaystyle c$ sorozatok száma $\displaystyle 3^{n-1}-1$. Tehát a megfelelő $\displaystyle (a,b,c)$ hármasok száma $\displaystyle t(t-1)(3^{n-1}-1)$.

Most ugyanezt másféleképpen is megszámoljuk: először $\displaystyle c$-t választjuk meg, erre ($\displaystyle 3^n-1$)-féle lehetőség van. Ezután az olyan $\displaystyle (a,b)$ párok lesznek megfelelők, melyekre az $\displaystyle a_1c_1+a_2c_2+\dots+a_nc_n$ és $\displaystyle b_1c_1+b_2c_2+\dots+b_nc_n$ összegek hármas maradéka egyforma. A feltétel szerint $\displaystyle |A|/3=t/3$ esetben lesz 0, $\displaystyle t/3$ esetben lesz 1 és szintén $\displaystyle t/3$ esetben lesz 2 az összeg 3-as maradéka. Így a megfelelő $\displaystyle (a,b)$ párok száma $\displaystyle 3(t/3)(t/3-1)=t(t/3-1)$. Így a hármasok száma $\displaystyle (3^n-1)t(t/3-1)$.

A $\displaystyle t(t-1)(3^{n-1}-1)=(3^n-1)t(t/3-1)$ ($\displaystyle t$-ben másodfokú) egyenlet megoldásai $\displaystyle t=0$ és $\displaystyle t=3^{n}$. Tehát ha $\displaystyle A$-ra teljesül a feltétel, akkor vagy $\displaystyle A=\emptyset$ vagy $\displaystyle A=\mathcal{S}$.

A kikötés szerint $\displaystyle A\ne\emptyset$, így csak $\displaystyle A=\mathcal{S}$ lehetséges. Legyen tehát $\displaystyle A=\mathcal{S}$, és vegyünk egy tetszőleges $\displaystyle c=(c_1,c_2,\dots,c_n)\in \mathcal{S}\setminus\{(0,0,\dots,0)\}$ sorozatot. Legyen például $\displaystyle c_i\ne 0$. A korábbiakhoz hasonlóan igazolható, hogy tetszőleges $\displaystyle a_1,a_2,\dots,a_{i-1},a_{i+1},\dots,a_n$ mellett az

$\displaystyle (a_1,\dots,a_{i-1},0,a_{i+1},\dots,a_n),(a_1,\dots,a_{i-1},1,a_{i+1},\dots,a_n),(a_1,\dots,a_{i-1},2,a_{i+1},\dots,a_n)$

sorozatok közül pontosan az egyikre lesz $\displaystyle c_1a_2+c_2a_2+\dots+c_na_n$ szám 3-mal osztható. Ebből pedig már következik, hogy $\displaystyle A=\mathcal{S}$ kielégíti a feltételeket.

Statisztika:

19 dolgozat érkezett.
6 pontot kapott:	Beke Csongor, Fekete Richárd, Fleiner Zsigmond, Füredi Erik Benjámin, Kercsó-Molnár Anita, Nádor Benedek, Nguyen Bich Diep, Seres-Szabó Márton, Szabó 991 Kornél, Sztranyák Gabriella, Velich Nóra.
5 pontot kapott:	Bognár 171 András Károly, Kovács 129 Tamás, Lengyel Ádám, Lovas Márton, Móra Márton Barnabás.
4 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2020. februári matematika feladatai