Feladat: C.1466 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Markó Gábor ,  Szeszlér Dávid 
Füzet: 2018/december, 536 - 538. oldal  PDF  |  MathML 
Témakör(ök): C gyakorlat, Logikai feladatok
Hivatkozás(ok):Feladatok: 2018/február: C.1466

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Először megmutatjuk, hogy 58 ember elegendő. Ehhez először olyan konstrukciót mutatunk, amely 66 embert használ, viszont minden hónapban 11-en vesznek részt az ülésen; utána ezt fogjuk alkalmasan módosítani.
Tekintsük az {1,2,...,12} halmaz összes 2 elemű részhalmazát és mindegyiket feleltessük meg a bizottság egy tagjának: az {i,j} párnak megfeleltetett ember az i-edik és a j-edik hónapban menjen el az ülésre. Ekkor összesen (122)=66 embert használtunk és minden hónapban 11-en vannak jelen az ülésen (hiszen minden 1≤i≤12 esetén 11 olyan pár van, ami i-t tartalmazza). Továbbá bármely két ember legföljebb egyszer találkozik: ha az {i,j} és {k,ℓ} párok diszjunktak, akkor a megfelelő két ember egyáltalán nem találkozik, ha pedig {i,j}∩{k,ℓ}={m}, akkor pontosan az m-edik hónapban találkoznak.
Helyettesítsük most az {1,2}, {1,3} és {2,3} pároknak megfelelő bizottsági tagokat egyetlen emberrel; őt tekinthetjük úgy, hogy az {1,2,3} részhalmaznak felel meg. Hasonlóan, keletkezzen a {4,5}, {4,6}, {5,6} párokból a {4,5,6} hármas, a {7,8}, {7,9}, {8,9} párokból a {7,8,9} hármas, végül a {10,11}, {10,12} és {11,12} párokból a {10,11,12} hármas. Ezzel az emberek számát 4⋅2=8-cal csökkentettük, vagyis 58 embert használunk. Minden hónapban 1-gyel csökkentettük a megjelenő tagok számát (hiszen minden 1≤i≤12 esetén két, i-t tartalmazó párból egyetlen i-t tartalmazó hármast csináltunk), így mostmár minden hónapban 10-en jelennek meg az ülésen. Végül pedig továbbra is igaz, hogy bármely két ember legföljebb egyszer találkozik: mivel a három elemű részhalmazok páronként diszjunktak, ezért az ezeknek megfelelő emberek egyáltalán nem találkoznak; továbbá mivel egy két és egy három elemű részhalmaznak is legföljebb csak egy közös eleme lehet (mert a három elemű részhalmazok két elemű részhalmazait megszüntettük), ezért az ilyeneknek megfelelő emberek is legföljebb egyszer találkoznak.
Most megmutatjuk, hogy legalább 58 emberre van szükség. Először tegyük fel, hogy van olyan ember, aki legalább 4 bizottsági ülésen jelen van: például Kovács úr az első 4 hónapban elmegy. Ekkor Kovács úron kívül az első 4 bizottsági ülés közül már semelyik kettőnek nem lehet közös résztvevője, vagyis eddig 1+4⋅9=37 embert használtunk. Az ötödik hónapban legalább 6 új emberre van szükség, hiszen az első négy hónapból csak egyet-egyet vehetünk. Hasonlóan, minden 5≤i≤10 esetén igaz, hogy az i-edik hónapban legalább 11-i új emberre van szükség, hiszen az első i-1 hónap mindegyikéből csak egyet-egyet vehetünk. Ezzel összesen valóban legalább 1+4⋅9+6+5+...+1=37+21=58 embert használtunk.
A továbbiakban tehát feltehetjük, hogy minden bizottsági tag legföljebb 3 ülésen jelenik meg. Jelölje z1, z2, illetve z3 azon tagok számát, akik (pontosan) 1, 2, illetve 3 ülésre mennek el. Célunk tehát megmutatni, hogy z1+z2+z3≥58.
Mivel a 12 hónapban összesen 12⋅10=120 ember jelenik meg, ezért

z1+2z2+3z3=120.(*)

Bárhogyan választunk ki két hónapot, ezekben együttesen legalább 19 ember jelenik meg (hiszen a két ülésnek csak egy közös résztvevője lehet). Adjuk most össze az összes hónappárra az azokban megjelenő bizottsági tagok együttes számát; mivel a 12 hónapból (122)=66 pár készíthető és minden pár esetében az együttes létszám legalább 19, ezért ez az összeg legalább 66⋅19=1254. Hányszor számoltunk meg ezzel egy-egy embert? Ha valaki összesen csak 1 bizottsági ülésre ment el, akkor 11-szer: ennyi hónappár tartalmazza azt az egy hónapot, amikor elment. Ha valaki pontosan 2 hónapban ment el, akkor 21-szer számoltuk meg: valóban, ha az i-edik és j-edik hónapokban volt ott, akkor i-t és j-t is 11 hónappár tartalmazza, de az így kapott 2⋅11-ből egyet le kell vonni, mert az {i,j} hónappárt duplán számoltuk. Ha pedig valaki pontosan 3 ülésen volt ott, akkor 30-szor számoltuk meg: ha az i-edik, j-edik és k-adik hónapokban volt ott, akkor 3⋅11-3 hónappár tartalmaz i, j és k közül legalább egyet (és azért 3-at vontunk le, mert a 3⋅11-ben az {i,j}, {i,k} és {j,k} párokat is duplán számoltuk). Mindebből tehát az alábbi következik:
11z1+21z2+30z3≥1254.(**)

Vonjuk most le az (**) egyenlőtlenség egyharmadából az (*) egyenlet háromszorosát: 23z1+z2+z3≥58. Ebből pedig (z1≥0 miatt) z1+z2+z3≥58 valóban következik.
 

Megjegyzés. A fentiekből az is következik, hogy z1+z2+z3=58 csak úgy valósulhat meg, ha z1=0 ‐ vagyis 58 emberrel csak úgy készíthető helyes konstrukció, ha mindenki legalább 2-szer elmegy. A fenti bizonyítás nem zárja ki olyan, 58 embert használó konstrukció létezését, amelyben van olyan tag, aki legalább 4-szer elmegy; valójában azonban ez is lehetetlen. Először is, a gondolatmenet apró módosításával könnyű megmutatni, hogy ha van olyan bizottsági tag, aki legalább 5-ször elmegy, akkor már legalább 61 emberre van szükség. Ha pedig a bizonyítást kiegészítjük azzal, hogy bevezetjük a pontosan 4-szer megjelenő emberek számára a z4 jelölést is és ezt is bevesszük a (*) egyenletbe és a (**) egyenlőtlenségbe, akkor végül a 23z1+z2+z3+23z4≥58 egyenlőtlenséget kapjuk. Ebből pedig valóban következik, hogy z1+z2+z3+z4=58 csak a z1=z4=0 esetben lehetséges. Továbbá, mivel a z2+z3=58 és 2z2+3z3=120 egyenletekből z2=54 és z3=4 adódik, ezért 58 emberrel csak úgy lehet helyes megoldást kapni, ha pontosan 4 ember megy el háromszor és a maradék 54 kétszer. Ennek végiggondolása után a megoldás elején leírt konstrukció már sokkal könnyebben megtalálható.
Szeszlér Dávid, BME

 

Megjegyzések. 1. A feladat sajnos túl nehéz volt. A megoldók közül sokan csak egy adott konstrukciót adtak a becslésükre, ám abból nem következett, hogy nincs jobb konstrukció. Egyetlen 5 pontos megoldás született, a fentitől különbözik, és a honlapon olvasható. A 2 pontos megoldás adott egy jó konstrukciót 58 főre, de nem látta be, hogy kevesebb nem elég. 1 pontot kaptak, akik 60 főre, vagy 55-57 főre adtak egy jó konstrukciót. Nem kaptak pontot a többiek, illetve akik rossz konstrukciót adtak (ezekben gyakran nem teljesült az a feltétel, hogy bármely két tag legfeljebb egyszer volt jelen azonos ülésen).
2. Sokan követték az alábbi gondolatmenetet, ám nem jutott eszükbe, hogy megpróbáljanak 34 főre megadni egy példát, így ‐ mivel a bizonyítás ugyan helyes, de maga a becslés nagyon alatta van a valódi értéknek ‐ ők is 0 pontot kaptak: ,,Egy ülésen 10-en vettek részt. 10 emberből (102)=45 pár alakítható ki. Ezek a párok már másik ülésen nem ismétlődhetnek és ez igaz a többi ülésre is. Ezért annyi tagnak kell lenni a bizottságban, akikből legalább 12⋅45=540 különböző pár alakítható ki: (n2)=n(n-1)2≥540, vagyis n2-n-1080≥0. A másodfokú egyenlet pozitív megoldása n≈33,37, így az egyenlőtlenségé, figyelembe véve, hogy n pozitív egész szám, n≥34. Tehát legalább 34 tagból áll a bizottság.''
3. Sokan érveltek a következőképpen: ,,Az első alkalommal 10 emberrel számolhatunk. A második alkalommal a legkedvezőbb, ha egy ember eljön az első gyűlésről (így többen onnan már nem jöhetnek), azaz a második gyűlésen 9 új ember jelenik meg. A harmadik gyűlésen 2 olyan ember tud megjelenni, aki még nem voltak azonos alkalommal (egyik az első, másik a második gyűlésről; aki mindkettőn részt vett, az a harmadikon már nem vehet részt) ‐ így 8 új ember jelenik majd meg. És így tovább: a negyediken 7, az ötödiken 6, a hatodikon 5, a hetediken 4, a nyolcadikon 3, a kilencediken 2, a tizediken 1, új ember lesz jelen, a tizenegyedik ülésre pedig minden előző ülésről pontosan 1 olyan embert választunk, akik még csak egy gyűlésen voltak, így azon egy új ember sem lesz. A tizenkettedik gyűlésre bárki jön el, aki már volt gyűlésen, az két gyűlés összes tagjának teszi lehetetlenné a részvételt, így összesen maximum 5 olyan ember tud a tizenkettedik gyűlésen részt venni, akik még nem voltak ugyanazon a gyűlésen ‐ ez 5 új embert jelent. Ez összesen 60 fő.'' Ezzel az érveléssel az a probléma, hogy nem biztos, hogy a legkevesebb embert ilyen módon találhatjuk meg.
 

 Szeszlér Dávid, (BME)