Az A. 569. feladat (2012. október)

A. 569. Nevezzünk egy $A\subset\mathbb{Z}$ halmazt érdekesnek, ha 2y-x $\in$ A minden olyan x,y $\in$ A pár esetén, amire x<y. Legyenek $a_1<a_2<\ldots<a_k$ olyan pozitív egészek (k $\ge$ 2), amelyek legnagyobb közös osztója 1. Bizonyítsuk be, hogy ha A érdekes halmaz, és $\{0,a_1,\ldots,a_k\}\subset A$ , akkor a₁+a_k-3 $\in$ A.

Javasolta: Carlos Gustavo T. A. Moreira (Gugu) (Rio de Janeiro)

(5 pont)

A beküldési határidő 2012. november 12-én LEJÁRT.

Megoldás. Általánosabb állítást bizonyítunk:

Lemma. Ha a₀<a₁<...<a_k (k $\ge$ 2) elemei egy A érdekes halmaznak, az (a₁-a₀), (a₂-a₀), ..., (a_k-a₀) számok legnagyobb közös osztója 1, és s=a_k+a₁-a₀-3, akkor {s,s+1,s+2,...} $\subset$ A.

A feladat azt állítja, hogy az a₀=0 speciális esetben s $\in$ A. Ez a lemmából következik.

A Lemmát (a_k-a₀) szerinti indukcióval bizonyítjuk.

Mivel k $\ge$ 2, csak a_k-a₀ $\ge$ 2 lehetséges. Ha a_k-a₀=2, akkor k=2, a₁=a₀+1 és a₂=a₀+2, tehát s=a₂+a₁-a₀-3=a₀. Ebben az esetben tehát s=a₀ $\in$ A, s+1=a₁ $\in$ A, és s+2=a₂ $\in$ A. Mivel az A halmaz érdekes, ha valamilyen x egész számra x $\in$ A és x+1 $\in$ A, akkor x+2=2(x+1)-x $\in$ A. Mivel például s $\in$ A és s+1 $\in$ A, ebből indukcióval következik, hogy s,s+1,s+2,... mind eleme A-nak. Ezzel az a_k-a₀=2 esetet elintéztük.

Tegyük most fel, hogy a_k-a₀>2, és tekintsük a a₁,a₂,...,a_k és 2a₁-a₀ számokat. Az indukciós feltevést ezekre a számokra fogjuk alkalmazni, de a számok sorrendjétől függően többéle esetet kell vizsgálnunk, és azt az esetet is külön kell kezelnünk, amikor a számok között csak két különböző van.

Mivel az A halmaz érdekes, 2a₁-a₀ $\in$ A. Az 2a₁-a₀,a₁,a₂,...,a_k számok közül az a₁ a legkisebb, és az (a₂-a₁),...,(a_k-a₁) és (2a₁-a₀)-a₁) számok legnagyobb közös osztója is 1, mert (a_i-a₁,(2a₁-a₀)-a₁)=(a_i-a₁,a₁-a₀)=(a_i-a₀,a₁-a₀).

1. eset: Az 2a₁-a₀,a₁,a₂,...,a_k számok között legfeljebb 2 különböző van.

Mivel a₂,...,a_k és 2a₁-a₀ mindegyike nagyobb mint a₁, ez az eset csak úgy lehetséges, ha k=2 és 2a₁-a₀=a₂. Ekkor tehát a₂-a₀=2(a₁-a₀). Az a₂-a₀ és a₁-a₀ számok csak úgy lehetnek relatív prímek, ha a₁-a₀=1 és a₂-a₀=2; de ez nem lehetséges a a_k-a₀>2 feltevés miatt.

2. eset: Az 2a₁-a₀,a₁,a₂,...,a_k számok között legalább 3 különböző van, és 2a₁-a₀<a₂.

Alkalmazzuk az indukciós feltevést a b₀=a₁<b₁=2a₁-a₀<b₂=a₂<...<b_k=a_k számokra. (Ezt megtehetjük, mert b_k-b₀=a_k-a₁<a_k-a₀.) Legyen t=b_k+b₁-b₀-3. Az indukciós feltevés szerint t,t+1... mind eleme A-nak. Mivel t=a_k+(2a₁-a₀)-a₁-3=s, éppen az állíttást kapjuk.

3. eset: Az 2a₁-a₀,a₁,a₂,...,a_k számok között legalább 3 különböző van, és 2a₁-a₀>a_k.

Alkalmazzuk az indukciós feltevést a b₀=a₁,b₁=a₂,...,b_k-1=a_k,b_k=2a₁-a₀ számokra. (Ezt megtehetjük, mert b_k-b₀=a₁-a₀<a_k-a₀.) Legyen t=b_k+b₁-b₀-3. Az indukciós feltevés szerint t,t+1... mind eleme A-nak. Mivel t=(2a₁-a₀)+a₂-a₁-3=a₂+a₁-a₀-3 $\le$ s, ebből következik, hogy {s,s+1,...} $\subset$ {t,t+1,...} $\subset$ A.

4. eset: Az 2a₁-a₀,a₁,a₂,...,a_k számok között legalább 3 különböző van, és a₂ $\le$ 2a₁-a₀ $\le$ a_k.

Rendezzük nagyság szerint az a₁,...,a_k és 2a₁-a₀ számokat; a rendezett sorozat legyen $b_0<b_1<...<b_\ell$ , ahol $\ell$ =k vagy $\ell$ =k-1 attól függően, hogy 2a₁-a₀ szerepel-e a₁,...,a_k között, továbbá b₀=a₁, b₁=a₂ és $b_\ell=a_k$ .

Legyen $t=b_\ell+b_1-b_0-3$ . Ismét alkalmazhatjuk az indukciós feltevést, mert b $\ell$ -b₀=a_k-a₁<a_k-a₀; az indukciós feltevés szerint {t,t+1,...} $\subset$ A. Mivel t=a_k+a₂-a₁-3 $\le$ a_k+(2a₁-a₀)-a₁-3=s, azt kaptuk, hogy {s,s+1,...} $\subset$ {t,t+1,...} $\subset$ A.

Statisztika:

8 dolgozat érkezett.

5 pontot kapott: Janzer Olivér, Nagy Róbert, Omer Cerrahoglu, Szabó 789 Barnabás.

1 pontot kapott: 1 versenyző.

0 pontot kapott: 3 versenyző.

A KöMaL 2012. októberi matematika feladatai

8 dolgozat érkezett.
5 pontot kapott:	Janzer Olivér, Nagy Róbert, Omer Cerrahoglu, Szabó 789 Barnabás.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.

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