 |
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