Az A. 890. feladat (2024. november)

A. 890. Bart, Lisa és Maggie a következő játékot játsszák: Bart véges sok pontot kiszínez egy körön kékre vagy pirosra olyan módon, hogy nem lehet találni a színezett pontok között négyet úgy, hogy a színük egymás után felváltva kék-piros-kék-piros (a kiválasztott pontoknak nem kell szomszédosnak lenniük), Lisa pedig kiválaszt néhány pontot a színezettek közül. Ezután Maggie megkapja a kört és a Lisa által kiválasztott pontokat Barttól (esetleg elforgatva), de szín nélkül. Végül Maggie a kör összes pontját kiszínezi kékre vagy pirosra. Lisa és Maggie megnyeri a játékot, ha Maggie eltalálja a Bart által eredetileg választott pontok színét. Egy Lisa és Maggie által megbeszélt stratégiát nyerő stratégiának nevezünk, ha Bart tetszőleges színezése esetén megnyeri a játékot.

Bizonyítsuk be, hogy létezik olyan nyerő stratégiája Lisának és Maggienek, ahol Lisa minden esetben legfeljebb \(\displaystyle c\) darab pontot választ ki, és keressük meg \(\displaystyle c\) legkisebb lehetséges értékét.

Javasolta: Pálvölgyi Dömötör (Budapest)

(7 pont)

A beküldési határidő 2024. december 10-én LEJÁRT.

Azt állítjuk, hogy a legkisebb megfelelő szám a \(\displaystyle c=3\).

Először megmutatjuk, hogy \(\displaystyle c=2\) még nem elég. Bart egy szabályos háromszög csúcsait négyféle módon tudja kiszínezni a megadott feltételeknek megfelelően, azonban Lisa csak háromféle módon tud közülük legfeljebb két pontot választani, ami nem elegendő a négyféle információ átadására.

Most megmutatjuk, hogy \(\displaystyle c=3\) elég. Az elinduláshoz figyeljük meg, hogy a feladat feltételéből következik, hogy a kört két körívre lehet osztani úgy (az egyik lehet akár az üres halmaz is), hogy az egyik csak kék, a másik csak piros pontot tartalmazzon. Lisa stratégiája legyen a következő:

• Ha Bart csak a kék színt használja, akkor Lisa nem választ pontot.
• Ha Bart csak egy pontot színez pirosra, akkor Lisa ezt az egy pontot választja ki.
• Ha Bart legalább két pontot színez pirosra, és a piros pontok lefedhetők egy nyílt félkörívvel, akkor Lisa a két szélső piros pontot választja.
• Ha a fentiek nem teljesülnek, és nincs kék pont sem, akkor Lisa úgy választ két vagy három pontot, hogy ne lehessen őket lefedni egy nyílt félkörívvel (azaz ne alkossanak tompaszögű háromszöget). Az, hogy ez mindig lehetséges, megmutatjuk majd a gondolatmenet végén.
• Végül ha kék pont is van, akkor Lisa választ egy kék pontot és azt a két pirosat, melyek szomszédosak kék ponttal. Figyeljük meg, hogy a három választott pont lefedhető egy zárt félkörívvel (azaz tompa- vagy derékszögű háromszöget alkotnak), mert ellenkező esetben a piros pontokat lehetne lefedni egy nyílt félkörívvel.

Maggie stratégiája pedig ez legyen:

• Ha Maggie nem kap pontot, akkor az egész kört kékre színezi.
• Ha Maggie egy pontot kap, akkor azt pirosra, minden mást kékre színez.
• Ha Maggie két pontot kap, melyek nem átellenesek, akkor ezeket és az általul definiált rövidebb körívet pirosra, minden mást kékre színez.
• Ha Maggie két átellenes pontot vagy három olyan pontot kap, amelyek nem fedhetők le egy nyílt félkörívvel (azaz nem alkotnak tomapszögű háromszöget), akkor az egész kört pirosra színezi.
• Végül ha Maggie három olyan pontot kap, melyek lefedhetők egy zárt félkörívvel (azaz derék- vagy tompaszögű háromszöget alkotnak), akkor az általuk definiált félkörnél nem hosszabb körív belsejét kékre, minden mást pirosra színez.

Egy dolgot kell még meggondolni: a felsorolás negyedik pontjánál Lisa mindig tud jól választani pontokat, azaz ha a piros pontok nem fedhetők le egy nyílt félkörívvel, akkor lehet közülük választani legfeljebb hármat, amit szintén nem lehet lefedni egy nyílt félkörívvel. Ha csak két piros pont van, az állítás magától értetődő, mert átellenesnek kell lenniük. Ha legalább három piros pont van, tekintsük a piros pontok konvex burkát: ennek tartalmaznia kell a kör középpontját a belsejében vagy a határán, mert különben lehet a kör középpontján keresztül húzni egy egyenest, amely nem találkozik a konvex sokszöggel, és így kapnánk egy nyílt félkörívet, amely tartalmazza az összes piros pontot. Ha most a konvex sokszöget feloszjuk háromszögekre, valamelyik háromszög tartalmazza a kör középpontját a belsejében vagy a határán, és ennek a három csúcsa nem fedhető le egy nyílt félkörívvel.

Ezzel a bizonyítást befejeztük.

Statisztika:

Az A. 890. feladat értékelése még nem fejeződött be.

A KöMaL 2024. novemberi matematika feladatai