Az A. 604. feladat (2013. december)

A. 604. Adott egy egészekből álló, (2ⁿ-1)×(2ⁿ⁺¹-1) méretű táblázat. Igazoljuk, hogy lehetséges a táblázatból 2ⁿ-1 oszlopot törölni úgy, hogy a megmaradó (2ⁿ-1)×2ⁿ-es résztáblázat minden sorában az elemek összege páros legyen.

(5 pont)

A beküldési határidő 2014. január 10-én LEJÁRT.

Megoldás. Jelölje a_ij az i-edik sor j-edik elemét. Tetszőleges $1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1$ indexekre legyen $T(j_1,\ldots,j_{2^n})$ a j₁-edik, ..., j_2ⁿ-edik oszlopokból álló résztáblázat, és legyen

$f(j_1,\ldots,j_{2^n}) = \prod_{i=1}^{2^n-1}\left(1+\sum_{\ell=1}^{2^n}a_{i,j_\ell}\right).$

A $T(j_1,\ldots,j_{2^n})$ résztáblázat i-edik sorában az elemek összege akkor és csak akkor páros, ha az $1+\sum\limits_{\ell=1}^{2^n}a_{i,j_\ell}$ összeg páratlan; következésképp, a $T(j_1,\ldots,j_{2^n})$ résztáblázat akkor teljesíti kívánt tulajdonságokat, ha $f(j_1,\ldots,j_{2^n})$ páratlan.

Tekintsük a következő összeget:

$S = \sum_{1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1} f(j_1,\ldots,j_{2^n}) = \sum_{1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1} \prod_{i=1}^{2^n-1}\left(1+\sum_{\ell=1}^{2^n}a_{i,j_\ell}\right).$

(1)

Megmutatjuk, hogy S mindig páratlan. Ez bizonyítja, hogy $f(j_1,\ldots,j_{2^n})$ felvesz páratlan értéket, és a kívánt résztáblázat valóban létezik.

Kibontva (1)-ben a zárójeleket, láthatjuk, hogy az S összeg $a_{u_1,v_1}\ldots a_{u_k,v_k}$ alakú szorzatok összege, ahol 0 $\le$ k $\le$ 2ⁿ⁺¹-1, $1\le u_1<\ldots<u_k\le 2^n-1$ , és 1 $\le$ v₁,...,v_k $\le$ 2ⁿ⁺¹-1. (A k=0 esetben a szorzat üres, értékét 1-nek definiáljuk.)

Most számláljuk össze, hogy az $a_{u_1,v_1}\ldots a_{u_k,v_k}$ tag hányszor fordul elő (1)-ben. Ez a tag pontosan pontosan akkor elő a $\prod\limits_{i=1}^{2^n-1}\left(1+\sum\limits_{\ell=1}^{2^n}a_{i,j_\ell}\right)$ szorzatban, mégpedig pontosan 1-szer, ha a v₁,...,v_k indexek szerepelnek j₁,...,j_2ⁿ között.

Tegyük fel, hogy összesen m különböző érték szerepel v₁,...,v_k között, ahol m=|{v₁,...,v_k}| $\le$ k. Ezzel már m darabot megadtunk a j₁,...,j_2ⁿ indexek közül; a többi 2ⁿ-m értéket a fel nem használt 2ⁿ⁺¹-1-m érték közül kell kiválasztanunk. Tehát, az $a_{u_1,v_1}\ldots a_{u_k,v_k}$ tag pontosan $\binom{2^{n+1}-1-m}{2^n-m}$ alkalommal fordul elő S-ben. Így hát

$S = \binom{2^{n+1}-1}{2^n} + \,\, \sum_{k=1}^{2^n-1}\sum_{1\le u_1<\ldots<u_k\le 2^n-1} \,\, \sum_{1\le v_1,\ldots,v_k\le 2^{n+1}-1} \binom{2^{n+1}-1-|\{v_1,\dots,v_k\}|}{2^n-|\{v_1,\dots,v_k\}|} a_{u_1,v_1}\ldots a_{u_k,v_k}.$

(2)

A megoldás befejezéséhez megmutatjuk, hogy $\binom{2^{n+1}-1-m}{2^n-m}$ csak m=0 esetén páratlan; 1 $\le$ m $\le$ 2ⁿ-1 esetén pedig páros. (Ez a binomiális együtthatók jól ismert tuajdonságaiból is következik, mint például a Lucas-lemma.)

Ha m=0, akkor

$\binom{2^{n+1}-1-m}{2^n-m} = \binom{2^{n+1}-1}{2^n} = \frac{2^{n+1}-1}{1} \cdot \frac{2^{n+1}-2}{2} \cdot \ldots \cdot \frac{2^n}{2^n}.$

A szorzat minden egyes tényezőjére igaz, hogy a számlákó és a nevező prímtényezős felbontásában a 2 kitevője ugyanaz, ezért a szorzat páratlan.

Ha 1 $\le$ m $\le$ 2ⁿ-1, akkor

$\binom{2^{n+1}-1-m}{2^n-m} = \frac{2^n}{2^n-m} \cdot \binom{2^{n+1}-m}{2^n-m}.$

A 2 kitevője (2ⁿ-m)-ben kisebb, mint n, így $\frac{2^n}{2^n-m} \cdot \binom{2^{n+1}-m}{2^n-m}$ páros.

Tehát, (2) jobboldalán minden tag páros, kivéve az $\binom{2^{n+1}-1}{2^n-1}$ kezdőtagot, ami páratlan. Az S szám tehát páratlan, ami bizonyítja az állítást.

Statisztika:

2 dolgozat érkezett.

0 pontot kapott: 2 versenyző.

A KöMaL 2013. decemberi matematika feladatai

Már regisztráltál?
Új vendég vagy?