Az A. 512. feladat (2010. szeptember)

A. 512. Van $n=\frac{3^k-3}2$ , látszólag egyforma pénzérménk, de közülük csak n-1 egyforma, az egyik ugyanis ,,hamis'', könnyebb vagy nehezebb a többinél. Egy kétkarú mérleg segítségével szeretnénk meghatározni, melyik a hamis érme. Mutassuk meg, hogy k alkalmasan kiválasztott mérés elvégzésével biztosan megtalálhatjuk a hamis érmét, azt is meg tudjuk határozni, hogy könnyebb avagy nehezebb, sőt, lehetséges a mérések sorozatát előre összeállítani, az egyes mérések eredményének ismerete nélkül.

(5 pont)

A beküldési határidő 2010. október 11-én LEJÁRT.

Megoldásvázlat. A méréseinket egy k×n-es táblázatban írjuk le. Minden érméhez tartozni fog egy oszlop, és minden sor egy mérés elrendezését definiálja. Az i-edik sor j-eleme a következő lesz:

+1, ha a i-edik mérésben a j-edik érmét a baloldali tányérba helyezzük;

-1, ha a i-edik mérésben a j-edik érmét a jobboldali tányérba helyezzük;

0, ha a i-edik mérésben a j-edik érmét nem tesszük rá a mérlegre.

A táblázat j-edik oszlopát jelölje v_j.

A mérések eredményét szintén egy k elemű r (oszlop-) vektorban gyűjtjük össze. Az r vektor i-edik koordinátája legyen

+1, ha az i-edik mérésben a baloldal nehezebb;

-1, ha az i-edik mérésben a jobboldal nehezebb;

0, ha az i-edik mérésben a mérleg egyensúlyban van.

Ha a h-adik érme hamis, és nehezebb a többi érménél, akkor r=v_h lesz. Ha pedig a h-adik érme könnyebb a többinél, akkor r=-v_h lesz.

A táblázat akkor ad megoldást a feladatra, ha a következő két tulajdonsággal rendelkezik:

(1) Minden sorban ugyanannyi +1 van, mint -1, mivel a mérleg két serpenyőjébe ugyanannyi érmét kell tennünk. Más szóval, v₁+v₂+...+v_n=0.

(2) A v₁,-v₁,v₂,-v₂,...,v_n,-v_n vektorok páronként különbözők.

Ilyen tulajdonságú táblázat többféleképpen kostruálható. Most egy rekurzív módszert mutatunk. A konstrukcióban nem szerepel a csupa +1-ből és a csupa -1-ből álló vektor.

Ha k=2 (és n=3), akkor legyen $v_1=\left(\matrix{-1\cr 1}\right)$ , $v_2=\left(\matrix{1\cr 0}\right)$ és $v_3=\left(\matrix{0\cr -1}\right)$ .

Ha valamilyen k-ra már megkonstruáltuk az v₁,...,v_n vektorokat, akkor (k+1)-re válasszuk a következőket:

$\left(\matrix{v_j\cr +1}\right)$ , $\left(\matrix{v_j\cr -1}\right)$ és $\left(\matrix{v_j\cr 0}\right)$ minden j=1,2,...,n-re, továbbá $\left(\matrix{-1\cr -1\cr \vdots\cr -1\cr +1}\right)$ , $\left(\matrix{+1\cr +1\cr \vdots\cr +1\cr 0}\right)$ és $\left(\matrix{0\cr 0\cr \vdots\cr 0\cr -1}\right)$ ,

Statisztika:

20 dolgozat érkezett.

5 pontot kapott: Ágoston Tamás, Damásdi Gábor, Frankl Nóra, Lenger Dániel, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Szabó 928 Attila, Viharos Andor.

4 pontot kapott: Gyarmati Máté, Zsakó András.

3 pontot kapott: 2 versenyző.

2 pontot kapott: 1 versenyző.

1 pontot kapott: 1 versenyző.

0 pontot kapott: 4 versenyző.

A KöMaL 2010. szeptemberi matematika feladatai

20 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Damásdi Gábor, Frankl Nóra, Lenger Dániel, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Szabó 928 Attila, Viharos Andor.
4 pontot kapott:	Gyarmati Máté, Zsakó András.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	4 versenyző.

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