Problem B. 5084. (February 2020)

B. 5084. Let \(\displaystyle n\) be a positive integer, and let \(\displaystyle \mathcal{S}\) denote the set of \(\displaystyle 0-1-2\) sequences of length \(\displaystyle n\). Determine which sets \(\displaystyle \emptyset\ne A\subseteq\mathcal{S}\) have the following property: no matter how a vector

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

is selected, the probabilities that the sum of products \(\displaystyle c_1a_1+c_2a_2+\dots+c_na_n\) formed with a randomly chosen element \(\displaystyle (a_1,a_2,\ldots,a_n)\) of set \(\displaystyle A\) will leave a remainder of \(\displaystyle 0\), \(\displaystyle 1\), or \(\displaystyle 2\) are \(\displaystyle 1/3\) each.

Based on a problem of Kürschák competition

(6 pont)

Deadline expired on March 10, 2020.

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

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.

Statistics:

19 students sent a solution.
6 points:	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 points:	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 points:	2 students.
1 point:	1 student.

Problems in Mathematics of KöMaL, February 2020