![]() |
A 2002 februári A-jelű matematika feladatok megoldása |
A közöltek csak megoldásvázlatok, esetleg csak végeredmények. A maximális pontszám eléréséhez általában ennél részletesebb megoldás szükséges. A részletes megoldásokat a beküldött dolgozatok alapján a KöMaL-ban folyamatosan közöljük.
A. 284. Legyen f a véges S halmaz részhalmazain értelmezett függvény. Igazoljuk, hogy ha S tetszőleges A, B részhalmazaira
f(S\A)=f(A) és max(f(A),f(B))gef(AcupB),
akkor f legfeljebb |S| különböző értéket vesz fel.
Schweitzer Miklós Emlékverseny, 2001
1. megoldás. Az S=emptyset esetben az állítás nem igaz; a továbbiakban feltételezzük, hogy S nem üres.
Teljes indukciót alkalmazunk; |S|=1 és |S|=2 esetén éppen 1, illetve 2 komplementer részhalmaz pár van, ezért nem is lehet több függvényérték. Legyen tehát |S|>2, és tegyük fel, hogy kisebb elemszám esetén az állítás igaz.
Legyen f legnagyobb értéke m. Először megmutatjuk,
hogy van olyan X={x} egyelemű részhalmaza S-nek,
amelyre f(X)=m. Tekintsük azokat a
részhalmazokat, amelyekhez f az m számot rendeli. Ezek
között a komplementer tulajdonság miatt van nem üres is. Vegyük tehát
a legkisebb olyan nemüres X részhalmazt, amire
f(X)=m. Ha X legalább kételemű lenne,
akkor felbomlana két kisebb nem üres halmaz uniójára:
X=X1cupX2, de ekkor
max(f(X1),f(X2))f(X1cupX2)=f(X)=m miatt
f(X1) és f(X2)
valamelyike is m. Az X halmaz tehát egyelemű.
Legyen R=S\X, és definiáljuk a g:P(R)toR függvényt a következőképpen: tetszőleges AsubsetR esetén legyen
g(A)=min(f(A),f(AX))=min(f(A),f(R\A)).
Megjegyezzük, hogy tetszőleges AsubsetR esetén max(f(A),f(AcupX))=m. Ugyanis
m=f(X)=f(S\X)=f(A(R\A))lemax(f(A),f(R\A))=
=max(f(A),f(S\(R\A)))=max(f(A),f(AX)).
A továbbiakban megmutatjuk, hogy a g függvényre teljesül az
indukciós feltétel, azaz tetszőleges A,BR esetén
g(R\A)=g(A) és g(A
B)
max(g(A),g(B)). Az indukciós
feltevés szerint tehát g-nek legfeljebb (|S|-1)-féle
értéke lehet. Mivel tetszőleges AsubsetT halmazra f(A) és
f(A+X) egyike m, másika
g(A), ebből következik, hogy f értékkészlete
legfeljebb csak az m számmal lehet bővebb g
értékkészleténél.
A g(R\A)=g(A) tulajdonság g definíciójából leolvasható.
Ha g(A) és g(B) valamelyike m,
akkor a g(AcupB)lemax(g(A),g(B)) triviálisan
teljesül. Tegyük tehát fel, hogy g(A) és
g(B) kisebb, mint m, azaz f(A) és
f(AcupX), illetve f(B) és f(BX) valamelyike
kisebb m-nél. Ha f(A)<m, akkor legyen
C=A, ellenkező esetben legyen C=A
X. Hasonlóképpen legyen
f(B)<m esetén D=B, egyébként
D=BcupX. Ekkor f(C)=g(A) és
f(D)=g(B), a C
D halmaz pedig
vagy AcupB, vagy pedig AcupBcupX. Ezért
max(g(A),g(B))=max(f(C),f(D))f(C
D)
gemin(f(AcupB),f(AB
X))=g(AcupB).
A g függvényre tehát teljesülnek a feltételek.
2. megoldás (Csóka Endre megoldása). A megoldás alapja a következő lemma:
Lemma. Legyen v tetszőleges valós szám, és legyen Sv az S azon részhalmazainak a halmaza, amelyekhez az f függvény v-nél nem nagyobb értéket rendel:
Sv={XS: f(X)lev}.
Ekkor |Sv| vagy 0, vagy pedig egy 1-től különböző kettőhatvány.
A lemma bizonyítása. Először megállapítjuk, hogy
Sv zárt a komplementer-, unió-, metszet- és
különbségképzére, azaz tetszőleges Sv-beli
X,Y halmazok esetén S\X, XY, X
Y és
X\Y is Sv-beli. Az első kettő
azért igaz, mert f(S\X)=f(X)
v, illetve
f(XcupY)lemax(f(X),f(Y))
max(v,v)=v; a metszet és a különbség
pedig kifejezhető a komplementer és unió műveletekkel.
Az unióra és komplementerképzésre zártság egyik következménye, hogy
ha Sv nem üres, akkor SSv.
A komplementerképzésre zártságból következik, hogy ha Sv-nek van legalább egy eleme, akkor az elem komplementere is elem, ezért Sv elemei párokba állíthatók; Sv tehát nem lehet egyelemű.
Nevezzük Sv atomjainak a nem üres
elemei közül a minimálisakat. Egy nem üres ASv halmaz tehát akkor atom, ha X
A,
XinSv esetén X=
vagy
X=A.
Az atomok definíciójából két nagyon fontos dolog következik. Az
első, hogy ha AinSv egy atom és XSv tetszőleges halmaz, akkor A
vagy X-nek, vagy (S\X)-nek részhalmaza. Ellenkező
esetben ugyanis A\X egy nem üres, valódi részhalmaza
lenne A-nak, ami ellentmond annak, hogy A atom. A másik
fontos következmény, hogy az atomok páronként diszjunktak. Ha ugyanis
valamelyik két atom nem diszjunkt, akkor az előbbiek szerint
tartalmazzák egymást, vagyis a két atom ugyanaz.
Megmutatjuk, hogy az S halmaz minden elemét Sv-nek pontosan egy atomja tartalmazza. Mivel az atomok páronként diszjunktak, x legfeljebb egy atomnak lehet eleme; csak azt kell tehát igazolnunk, hogy létezik ilyen atom. Legyen xinS egy tetszőleges elem. Tekintsünk az x-et tartalmazó Sv-beli halmazok közül egy minimálisat; legyen ez A. Ha A nem atom, akkor nem minimális, tehát van egy XsubsetA részhalmaza, ami nem üres, de nem is egyenlő A-val. Ekkor X és A\X is Sv-beli, valódi részhalmaza A-nak, és egyikük tartalmazza x-et. Ez pedig ellentmond annak, hogy A minimális az x-et tartalazó Sv-beli halmazok közül. A tehát atom.
Az eddigiekből következik, hogy tetszőleges XSv halmaz egyértelműen írható fel
Sv-beli atomok uniójaként. Tetszőleges
xinS
elemhez legyen Ax az az atom, amelyre
xinAx. Az X halmaz egyértelmű
felírása a következő:
X=⋃x∈XAx.
A jobboldalon ugyanis minden atom részhalmaza X-nek, tehát a
jobboldal részhalmaza X-nek; másrészt a jobboldal az
X-nek minden elemét tartalmazza, mert tetszőleges xX esetén az
x-et tartalmazó Ax szerepel a tagok
között. Már csak azt kell igazolnunk, hogy ez az egyetlen felírás. Ha
xinX, akkor
X egy tetszőleges felírásban mindenképpen szerepelnie kell az
Ax atomnak, mert csak ez az atom tartalmazza
x-et. Az X-szel diszjunkt atomok pedig nem
szerepelhetnek X felírásában.
Legyenek Sv atomjai A1,...,Ak. Az előbbiek szerint minden Sv-beli X halmazhoz egyértelműen létezik egy olyan Isubset{1,2,...,k} indexhalmaz, amelyre X=cupiinIAi. Megfordítva, tetszőleges I indexhalmaz esetén cupiinIAi egy Sv-beli halmaz. Az Sv-beli halmazok tehát kölcsönösen egyértelműen megfeleltethetők az {1,2,...,k} halmaz részhalmazainak. Az ilyen részhalmazok száma 2k, tehát |Sv|=2k. Ezzel a lemmát igazoltuk.
Már csak a feladat állításának igazolása van hátra. Legyenek az f függvény értékei v1<v2<...<vn. Tekintsük az Sv1,Sv2,...,Svn halmazokat. Ezek egy bővülő láncot alkotnak:
Sv1Sv2
...
Svn.
A halmazok nem üresek, és semelyik kettő nem egyezhet meg. Ezért a
lemma alapján
|Sv1|<|Sv2|<...<|Svn|
különböző, 1-nél nagyobb 2-haványok, és így
|Svn|2n. Másrészt
Svn az S halmaz
összes részhalmazából áll, tehát
|Svn|=2|S|. Ezzel
azt kaptuk, hogy nle|S|.
Megjegyzés. Olyan példát nem nehéz konstruálni, amikor
f értékkészlete éppen |S| elemű. Legyen
S={1,2,...,n}, f(S)=f()=0,
továbbá tetszőleges S-től és az üres halmaztól különböző
X részhalmaz esetén legyen f(X) a legnagyobb
olyan S-beli szám, amelyre f(X) és
f(X)-1 közül pontosan az egyik eleme
X-nek. Például n=6 esetén f({1,2,5})=5.
A. 285. Bizonyítsuk be, hogy ha az a>b>c>d>0 egész számokra
a2+ac-c2=b2+bd-d2,
akkor ab+cd összetett.
Megoldás. Tegyük fel, hogy
p=ab+cd prím. Ekkor ab-cd
(mod p), és
0=b2(b2+bd-d2)-b2(a2+ac-c2)=b2(b2+bd-d2)-a2b2-ab2c+b2c2
equivb2(b2+bd-d2)-c2d2+bc2d+b2c2=(b2+c2)(b2+bd-d2) (mod p).
A b2+c2 és b2+bd-d2 számok közül tehát valamelyik osztható p-vel.
Ha b2+c2 osztható p-vel, akkor 0<b2+c2<2(ab+cd)=2p miatt b2+c2=p. Ebben az esetben ab+cd=b2+c2. Ezt modulo b vizsgálva látjuk, hogy c(c-d) oszható b-vel. A b és a c relatív prímek (különben ab+cd nem lehetne prímszám), tehát c-d osztható b-vel. Ez viszont ellentmondás, mert 0<c-d<b.
Ha b2+bd-d2 osztható p-vel, akkor 0<b2+bd-d2<2(ab+cd)=p miatt b2+bd-d2=p. Ekkor ab+cd=b2+bd-d2=a2+ac-c2. Ezt modulo a és modulo b vizsgálva láthatjuk, hogy (c+d)c osztható a-val, illetve (c+d)d osztható b-vel. Mivel ab relatív prím cd-hez, ebből az következik, hogy c+d osztható a-val és b-vel is. Mivel azonban 0<c+d<2a és 0<c+d<2b, ez egyszerre nem lehetséges.
A. 286. Határozzuk meg mindazokat az f:RR folytonos
függvényeket, amelyekre 1+xyne0 esetén
f(x+y1+xy)=f(x)f(y)|1+xy|.
Győrfi Zoltán és Ligeti Gábor ötletéből
Megoldás. Legyen
g(u)=|1+u2|⋅f(u−1u+1),
vagy másképpen
f(x)=|1−x|⋅g(1+x1−x).
Egy kis számolással ellenőrizhető, hogy ezzel a helyettesítéssel g(uv)=g(u).g(v). Ez háromféleképpen lehetséges:
a) g(u)equiv0; ekkor f(x)0.
b) g(u)=|u|alpha, ahol valós
szám. Ekkor f(x)=|1+x|
.|1-x|1-
. A
folytonosság miatt 0le
1.
c) g(u)=sgnu.|u|. Ekkor
f(x)=sgn(1-|x|).|1+x|
.|1-x|1-
. Ezúttal
0<
<1.
Megjegyzés. Az tört a hiperbolikus tangens
addíciós képletére hasonlít:
A megoldásban látott helyettestés során a törtben e2a
helyére írtunk u-t.