A C. 1466. feladat (2018. február)

C. 1466. Egy bizottság az év folyamán tizenkét alkalommal ülésezett. A tagok közül minden ülésen 10-en vettek részt, és bármelyik két tag legfeljebb egyszer volt együtt jelen. Legalább hány tagból áll a bizottság?

(5 pont)

A beküldési határidő 2018. március 12-én LEJÁRT.

Megoldásvázlat. \(\displaystyle 58\) taggal lehetséges megvalósítani a feltételeknek megfelelő üléseket. Mivel a \(\displaystyle 12\) ülésen \(\displaystyle 12\cdot10=120\) megjelenés szükséges, és \(\displaystyle 4\cdot3+54\cdot2=120\), ezért érdemes megpróbálkozni azzal, hogy négyen háromszor, ötvennégyen pedig kétszer jelennek meg. Az alábbi táblázat egyes oszlopaiban az szerepel, hogy hányadik tag vesz azon az ülésen részt.

Be kell még azt is bizonyítani, hogy kevesebb tag nem lehetséges.

\(\displaystyle 1\). eset. Tegyük fel, hogy egy tag legalább négy ülésen vett részt. Ha egy tag pontosan négy ülésen vett részt, akkor azokon a napokon, amikor részt vett, még \(\displaystyle 9\)-\(\displaystyle 9\), azaz összesen \(\displaystyle 4\cdot9=36\) új tag, \(\displaystyle 4\) naphoz összesen \(\displaystyle 37\) tag kell. Az ötödik ülésre választhatunk egy-egy tagot az első \(\displaystyle 4\) ülés mindegyikéről, így \(\displaystyle 6\) új tag kell, egyébként több kéne. Hasonlóan gondolkodva a hatodikra \(\displaystyle 5\), aztán \(\displaystyle 4\), \(\displaystyle 3\), \(\displaystyle 2\), \(\displaystyle 1\) tag kell legalább. Ez összesen már minimum \(\displaystyle 37+6+5+4+3+2+1=58\) tag. Ha pontosan öt ülésen vett részt legalább egy tag, akkor \(\displaystyle 5\cdot9+1=46\) tag kell az első öt üléshez, és így a \(\displaystyle 6.\), \(\displaystyle 7.\), \(\displaystyle 8.\) ülésre szintén legalább \(\displaystyle 6+5+4\) új tag kell, ami összeadva több, mint \(\displaystyle 58\). A gondolatmenetet folytatva beláthatjuk, hogy a szükséges taglétszám akkor sem csökken \(\displaystyle 58\) alá, ha egy tag még több ülésen venne részt.

Tehát nem lehet \(\displaystyle 57\) vagy kevesebb tag, ha legalább egy tag legalább négy ülésen vesz részt.

\(\displaystyle 2\). eset. Minden tag legfeljebb háromszor szerepelhet.

Ha mindegyik tag kétszer szerepel, az összesen csak \(\displaystyle 114\) megjelenés. Ha \(\displaystyle 6\) tag háromszor, és \(\displaystyle 51\) tag kétszer szerepel, akkor lehetséges a \(\displaystyle 6\cdot3+51\cdot2=120\) megjelenés. Tehát legalább \(\displaystyle 6\) tag van, aki \(\displaystyle 3\) ülésen vett részt.

Tegyük fel tehát, hogy \(\displaystyle 6\) tag \(\displaystyle 3\)-szor szerepelt, és mindenki más \(\displaystyle 2\)-szer. Legyen a hat háromszor szereplő tag \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle a_3\), \(\displaystyle a_4\), \(\displaystyle a_5\), \(\displaystyle a_6\). Nézzük meg, hogy a felsoroltak közül hányan lehetnek egy közös ülésen.

Ha van olyan nap, amikor mind a hatan egy ülésen vannak, akkor a többi napon már közülük semelyik kettő nem lehet együtt, ezért mindegyiküknek \(\displaystyle 2\) olyan ülés kellene, ahol csak egyedül szerepelnek, azaz még legalább \(\displaystyle 6\cdot2=12\) ülés kellene, ez pedig nem lehet, mert \(\displaystyle 11\) ülésnap maradt. Tehát nincs olyan nap, amikor mind a hatan egy ülésen vannak.

Ha van olyan nap, amikor öten, \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle a_3\), \(\displaystyle a_4\) és \(\displaystyle a_5\) egy ülésen vannak, akkor arra az ülésre még \(\displaystyle 5\) ember kell. A többi ülésen \(\displaystyle a_1\),..., \(\displaystyle a_5\) közül semelyik kettő nem lehet együtt. Ezért a többi napra legalább \(\displaystyle 9+9+7+7+5+5+3+3+1+1=50\) tag kell. Igaz, hogy köztük lehet \(\displaystyle a_6\) háromszor, de így is kell biztosan \(\displaystyle 47\) új tag. A tagok száma így minimum: \(\displaystyle 47+5(\mathrm{első~ülés})+6(3\)-\(\displaystyle \mathrm{szor~szereplők})=58\).

Tehát nincs olyan nap, amikor a háromszor szereplő hat tagból öten egy ülésen vannak.

Ha van olyan nap, amikor négyen, \(\displaystyle a_1\),...,\(\displaystyle a_4\) egy ülésen szerepelnek, arra az ülésre még \(\displaystyle 6\) tag kell. Ezt a \(\displaystyle 6\) tagot az első \(\displaystyle 9\) napon többször nem szerepeltethetjük, így az utolsó \(\displaystyle 3\) napon kell még egyszer mind a \(\displaystyle 6\) tagnak részt vennie, ami nem lehet (minden ülésen csak egy vehet részt).

Tehát nincs olyan nap, amikor a háromszor szereplő hat tagból négyen egy ülésen vannak.

Ha csak \(\displaystyle a_1\), \(\displaystyle a_2\) és \(\displaystyle a_3\) szerepel az első ülésen, akkor az utolsó öt ülésen \(\displaystyle 7\) tagnak kell részt vennie az első ülésről, ami nem lehet, hiszen minden ülésen csak egy vehet részt közülük.

Tehát nincs olyan nap, amikor a háromszor szereplő hat tagból hárman egy ülésen vannak.

Ha csak \(\displaystyle a_1\), \(\displaystyle a_2\) szerepel az első napon egy ülésen, akkor arra a napra még \(\displaystyle 8\) tag kell. Az utolsó \(\displaystyle 7\) ülésen \(\displaystyle 8\) tagnak kell részt vennie az első ülésről, ami nem lehet, hiszen minden ülésen csak egy vehet részt közülük.

Tehát nincs olyan nap, amikor a háromszor szereplő hat tagból ketten egy ülésen vannak.

Olyan nyilván nem lehetséges, hogy \(\displaystyle 6\) ember háromszor szerepel, de közülük mindenki csak egyedül szerepel egy adott ülésen.

Tehát nem lehetséges, hogy \(\displaystyle 57\) tagból pontosan \(\displaystyle 6\) tag \(\displaystyle 3\)-szor szerepelt, és mindenki más \(\displaystyle 2\)- szer.

Ha ennél több, azaz pl. pontosan \(\displaystyle 7\) ember szerepel háromszor, akkor biztosan lesz, aki csak egyszer szerepel, mivel \(\displaystyle 7\cdot3=21\) páratlan szám (és mindenki legfeljebb háromszor szerepel). Tehát \(\displaystyle 7\) tag van, aki \(\displaystyle 3\)-szor ülésezik. Ekkor ha \(\displaystyle 1\) tag csak \(\displaystyle 1\)-szer ülésezik, a többi \(\displaystyle 2\)-szer, az \(\displaystyle 7\cdot3+49\cdot2+1\cdot1=120\) megjelenés. Ez 57 ember lenne, tehát ha \(\displaystyle 1\)-nél többen üléseznének csak \(\displaystyle 1\)-szer, akkor az már több, mint 58 tag lenne. Ekkor sem ülésezhetnek \(\displaystyle 6\)-an egy nap (lásd fent). Ha \(\displaystyle 5\)-en üléseznek, akkor az \(\displaystyle 5\) új ember közül legalább \(\displaystyle 4\)-en az utolsó ülésen vesznek részt másodjára, ami nem lehetséges. Ha négyen vagy hárman szerepelnek egy ülésen, akkor a fenti indoklás él. Ha ketten, akkor \(\displaystyle 8\) embert kellene \(\displaystyle 7\) napra berakni úgy, hogy egyet ki lehet hagyni. Ez elvileg lehetséges, hiszen van egy ember, aki csak egyszer ülésezik. De legalább még egy olyan nap van, amikor két ember a \(\displaystyle 7\)-ből egy napon ülésezik, így azon a napon is van valaki, aki csak egyszer, ami viszont már nem lehetséges.

A gondolatmenet tovább folytatható. Ha eggyel növeljük azon emberek számát, aki \(\displaystyle 3\)-szor ülésezik, akkor eggyel nő azok száma is, akik csak egyszer. De így legalább \(\displaystyle 1\)-gyel nő azoknak az ülésnapoknak a száma is, ahol közülük ketten vagy többen üléseznek, és az ilyen napokról mindig jön egy újabb ember, akit már nem rakhatunk le. Így az \(\displaystyle 57\) emberes lerakás nem valósulhat meg. Tehát \(\displaystyle 57\) ember nem elegendő akkor sem, ha egy tag legalább négy ülésen veszt részt, és akkor sem, ha egy tag legfeljebb három ülésen.

Legalább \(\displaystyle 58\) tagból áll a bizottság, \(\displaystyle 58\) pedig elegendő, erre adtunk egy megfelelő konstrukciót.

Markó Gábor (Győr, Révai Miklós Gimn., 10. o. t.)

Megjegyzés. A feladat sajnos túl nehéz volt. Egy másik, nagyon szép megoldás és elemzés ősszel jelenik majd meg a nyomtatott lapban.

Statisztika:

130 dolgozat érkezett.
5 pontot kapott:	Markó Gábor.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	54 versenyző.
0 pontot kapott:	74 versenyző.

A KöMaL 2018. februári matematika feladatai