Problem A. 448. (February 2008)

A. 448. The numbers 1,2,...,N are colored with 3 colors such that each color is used at most $\frac{N}{2}$ times. Let A be set of all (ordered) 4-tuples (x,y,z,w), consisting of such numbers, such that $x+y+z+w\equiv 0 \pmod{N}$ and x, y, z, w have the same color. Similarly, let B be the set of all (ordered) 4-tuples (x,y,z,w) such that $x+y+z+w\equiv 0 \pmod{N}$ , the numbers x, y have the same color, z and w have the same color, but these two colors are distinct. Prove that |A| $\le$ |B|.

(5 pont)

Deadline expired on June 16, 2008.

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

I. megoldás. Legyenek P,Q,R $\subset$ {1,2,...,N} az egyes színű elemek hamazai, |P|=p, |Q|=q, |R|=r ahol p+q+r=N és $p,q,r\le\frac{N}2$ , továbbá legyen S={1,2,...,N}.

Tetszőleges X,Y,Z,W $\subset$ S halmazok esetén jelöljük M_XYZW-vel az olyan (x,y,z,w) négyesek halmazát, amelyekre x $\in$ X, y $\in$ Y, z $\in$ Z, w $\in$ W és x+y+z+w $\equiv$ 0 mod N, azaz legyen

M_XYZW={(x,y,z,w) $\in$ X×Y×Z×W: x+y+z+w $\equiv$ 0 mod N}.

Lemma. Tetszőleges X,Y,Z $\subset$ S halmazok esetén

|M_XYZP|+|M_XYZQ|+|M_XYZR|=|M_XYZS|=|X|^.|Y|^.|Z|.

Bizonyítás. Tetszőleges x $\in$ X, y $\in$ Y és z $\in$ Z-hez egyetlen olyan w $\in$ S elem létezik, amire x+y+z+w osztható N-nel. Ezért |M_XYZS|=|X|^.|Y|^.|Z|.

Az M_XYZS halmazban szereplő (x,y,z,w) számnégyeseket aszerint osztályozva, hogy w milyen színű, azaz a P Q, vagy az R halmazban van, láthatjuk, hogy M_XYZS az M_XYZP, M_XYZQ és M_XYZR diszjunkt halmazok uniója.

A lemmát többször alkalmazva,

- |A| + |B| =

= - (|M_PPPP|+|M_QQQQ|+|M_RRRR|) + (|M_PPQQ|+|M_PPRR|+|M_QQPP|+M_QQRR|+|M_QQPP|+|M_QQRR|) =

= - (p³-|M_PPPQ|-|M_PPPR|) - (q³-|M_QQQP|-|M_QQQR|) - (r³-|M_RRRP|-|M_RRRQ|) +

+ (p²q-|M_PPQP|-|M_PPQR|) + (p²r-|M_PPRP|-|M_PPRQ|) + (q²p-|M_QQPQ|-|M_QQPR|) +

+ (q²r-|M_QQRP|-|M_QQRQ|) + (r²p-|M_RRPQ|-|M_RRPR|) + (r²q-|M_RRQP|-|M_RRQR|) =

=-p³-q³-r³+p²q+p²r+q²p+q²r+r²p+r²q-2(|M_PQRP|+|M_PQRQ|+|M_PQRR|)=

=-p³-q³-r³+p²q+p²r+q²p+q²r+r²p+r²q-2pqr=(-p+q+r)(p-q+r)(p+q-r)=

=(N-2p)(N-2q)(N-2r) $\ge$ 0.

II. megoldás. Vezessük még be a következő jelöléseket.

Tetszőleges k egész számra legyen $\chi$ (k)=1, ha k osztható N-nel, és legyen $\chi$ (k)=0, ha k nen osztható N-nel;

Legyen $\varepsilon = e^{2\pi/N} = \cos\frac{2\pi}N + i \sin\frac{2\pi}N$ ;

Tetszőges X $\subset$ {1,2,...,N} halmaz és k egész szám esetén legyen $f_X(k)=\sum_{x\in X}\varepsilon^{kx}$ ;

Legyen $\varepsilon=e^{2\pi i/N}$ . A mértani sorozat összegképletéből követezik, hogy tetszőleges k egész szám esetén

$\frac1N f_{S}(k) = \frac1N \sum_{j=0}^{N-1} \varepsilon^{jk} = \chi(k).$

Tetszőleges X,Y,Z,W $\subset$ S halmazok esetén

$|M_{XYZW}| = \sum_{x\in X} \sum_{y\in Y} \sum_{z\in Z} \sum_{w\in W} \chi(x+y+z+w) = \sum_{x\in X} \sum_{y\in Y} \sum_{z\in Z} \sum_{w\in W} \frac1N \sum_{j=0}^{N-1} \varepsilon^{(x+y+z+w)j} =$

$= \frac1N \sum_{j=0}^{N-1} \left( \sum_{x\in X} \varepsilon^{xj}\right) \left( \sum_{y\in Y} \varepsilon^{yj}\right) \left( \sum_{z\in Z} \varepsilon^{zj}\right) \left( \sum_{w\in W} \varepsilon^{wj}\right) = \frac1N \sum_{j=0}^{N-1} f_X(j) f_Y(j) f_Z(j) f_W(j).$

Tagonként alkalmazva,

|B| - |A| =

= (2|M_PPQQ|+2|M_PPRR|+2M_QQRR|) - (|M_PPPP|+|M_QQQQ|+|M_RRRR|) =

$= ~ \frac1N \sum_{j=0}^{N-1} \bigg( 2f_P^2(j)f_Q^2(j) + 2f_P^2(j)f_R^2(j) + 2f_Q^2(j)f_R^2(j) - f_P^4(j) - f_Q^4(j) - f_R^4(j) \bigg) =$

$= ~ \frac1N \sum_{j=0}^{N-1} \Big( \big(f_P(j)+f_Q(j)+f_R(j)\big) \big(-f_P(j)+f_Q(j)+f_R(j)\big) \big(f_P(j)-f_Q(j)+f_R(j)\big) \big(f_P(j)+f_Q(j)-f_R(j)\big)\Big) =$

$= ~ \sum_{j=0}^{N-1} \left( \frac1N f_S(j) \right) \big(-f_P(j)+f_Q(j)+f_R(j)\big) \big(f_P(j)-f_Q(j)+f_R(j)\big) \big(f_P(j)+f_Q(j)-f_R(j)\big)\Big) =$

$= ~ \sum_{j=0}^{N-1} \chi(j) \big(-f_P(j)+f_Q(j)+f_R(j)\big) \big(f_P(j)-f_Q(j)+f_R(j)\big) \big(f_P(j)+f_Q(j)-f_R(j)\big)\Big) .$

Mivel csak j=0 esetén kapunk 0-tól különböző értéket,

|B|-|A|=(-f_P(0)+f_Q(0)+f_R(0))(f_P(0)-f_Q(0)+f_R(0))(f_P(0)+f_Q(0)-f_R(0)))=(-p+q+r)(p-q+r)(p+q-r) $\ge$ 0.

Megjegyzés. Mint a megoldásokból is látható, az állításnál jóval több is igaz: |A|-|B| pontosan akkor pozitív, negatív, illetve nulla, ha valamelyik szín N/2-nél többször szeperel, mindegyik szín N/2-nél kevesebbszer szeperel, illetve ha valamelyik szín pontosan N/2-ször szeperel.

Statistics:

5 students sent a solution.

5 points: Lovász László Miklós, Nagy 648 Donát, Tomon István.

0 point: 2 students.

Problems in Mathematics of KöMaL, February 2008

5 students sent a solution.
5 points:	Lovász László Miklós, Nagy 648 Donát, Tomon István.
0 point:	2 students.

Already signed up?
New to KöMaL?