KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 16 June 2008.


Google Translation (Sorry, the solution is published in Hungarian only.)

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\subsetS halmazok esetén jelöljük MXYZW-vel az olyan (x,y,z,w) négyesek halmazát, amelyekre x\inX, y\inY, z\inZ, w\inW és x+y+z+w\equiv0 mod N, azaz legyen

MXYZW={(x,y,z,w)\inX×Y×Z×Wx+y+z+w\equiv0 mod N}.

Lemma. Tetszőleges X,Y,Z\subsetS halmazok esetén

|MXYZP|+|MXYZQ|+|MXYZR|=|MXYZS|=|X|.|Y|.|Z|.

Bizonyítás. Tetszőleges x\inX, y\inY és z\inZ-hez egyetlen olyan w\inS elem létezik, amire x+y+z+w osztható N-nel. Ezért |MXYZS|=|X|.|Y|.|Z|.

Az MXYZS 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 MXYZS az MXYZP, MXYZQ és MXYZR diszjunkt halmazok uniója.

A lemmát többször alkalmazva,

- |A| + |B| =

= - (|MPPPP|+|MQQQQ|+|MRRRR|) + (|MPPQQ|+|MPPRR|+|MQQPP|+MQQRR|+|MQQPP|+|MQQRR|) =

= - (p3-|MPPPQ|-|MPPPR|) - (q3-|MQQQP|-|MQQQR|) - (r3-|MRRRP|-|MRRRQ|) + 

     + (p2q-|MPPQP|-|MPPQR|) + (p2r-|MPPRP|-|MPPRQ|) + (q2p-|MQQPQ|-|MQQPR|) + 

     + (q2r-|MQQRP|-|MQQRQ|) + (r2p-|MRRPQ|-|MRRPR|) + (r2q-|MRRQP|-|MRRQR|) =

=-p3-q3-r3+p2q+p2r+q2p+q2r+r2p+r2q-2(|MPQRP|+|MPQRQ|+|MPQRR|)=

=-p3-q3-r3+p2q+p2r+q2p+q2r+r2p+r2q-2(|MPQRP|+|MPQRQ|+|MPQRR|)=

=-p3-q3-r3+p2q+p2r+q2p+q2r+r2p+r2q-2pqr=(-p+q+r)(p-q+r)(p+q-r)=

=(N-2p)(N-2q)(N-2r)\ge0.

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\subsetS 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|MPPQQ|+2|MPPRR|+2MQQRR|) - (|MPPPP|+|MQQQQ|+|MRRRR|) =

 = ~ \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|=(-fP(0)+fQ(0)+fR(0))(fP(0)-fQ(0)+fR(0))(fP(0)+fQ(0)-fR(0)))=(-p+q+r)(p-q+r)(p+q-r)\ge0.

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 on problem A. 448.
7 students sent a solution.
5 points:Lovász László Miklós, Nagy 648 Donát, Tomon István.
0 point:2 students.
Unfair, not evaluated:2 solutions.


  • Problems in Mathematics of KöMaL, May 2008

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley