Egy n lakosú városban klubokat szerveznek úgy, hogy bármely két klubnak legyen, és bármely három klubnak már ne legyen közös tagja. Legfeljebb hány klubot lehet így szervezni?

Az előző válasz sajnos nem jó, ezt egy ellenpéldával könnyű bemutatni: legyen n 6, a klubok száma pedig négy: a hat lehetséges klub-pár legyen egy-egy ember klubjai. Ekkor persze bármely két klubnak van közös tagja (így definiáltuk az emberek klubtagságát), viszont 3-nak nincs közös.

A megoldáshoz próbálj karakterisztikus-vektorral dolgozni. Ha nem jön ki, később lesz időm leírni a teljes megoldást.

Szerintem ez egy sima másodfokú egyenlettel leírható...

Ha minden ember potosan két klub tagja, akkor teljesül a feltétel. Így gondolkodva 3 klub létrehozásához 3, 4 klub létrehozásához 6, 5 klub létrehozásához 10, 6 klub létrehozásához 15 ... stb. lakos szükséges a városban. Tehát x db klubhoz (x * (x-1)) / 2 lakosra van szükség.

Azaz:

(x * (x-1)) / 2 = n

megoldva:

x2 - x - 2n = 0

x = (1 + négyzetgyök allatt (1+8n)) / 2

(A megoldóképletből elhagyható a +- -ból a "-"-os, hiszen negatív db. klubot fizikailag nem lehet létrehozni.)

Szemléltetve példával. Nem tudom, mennyire látszik a táblázat, de hátha. :-)

A számok az emberek "sorszámát" jelentik, mindegyik azoknak a kluboknak a tagja, ami alatt szerepel.

1. klub 2. klub 3. klub 4. klub 5. klub 6. klub 7. klub

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

10 10

11 11

12 12

13 13

14 14

15 15

16 16

17 17

18 18

19 19

20 20

21 21

Grrr nem látszik, bocs, megpróbálom megfordítani:

1. klub 1 2 4 7 11 16

2. klub 1 3 5 8 12 17

3. klub 2 3 6 9 13 18

4. klub 4 5 6 10 14 19

5. klub 7 8 9 10 15 20

6. klub 11 12 13 14 15 21

7. klub 16 17 18 19 20 21

Lényegében ugyanazt írom le, mint Eszter76, de mivel még nem fogadtad el a válaszát (megköszönés és/vagy hasznosnak jelölés), ezért talán érdemes lehet megpróbálni picit másképp leírni / elmagyarázni ugyanazt.

Ha t darab klub van, akkor a feltételek szerint legalább (t alatta 2) lakos kell, hogy legyen, hiszen:

- bármely két klubhoz (továbbiakban: klub-párhoz) tartozik legalább egy közös tag,

- és két különböző klub-párhoz különböző közös tag tartozik.

Tehát n >= t(t-1)/2.

Azt kell még belátni, hogy ha a fenti felső becslés teljesül t-re, akkor valóban lehet úgy választani a klubokat, hogy teljesüljenek a megadott feltételek.

Első észrevétel az, hogy elég ezt arra az esetre belátni, ha n=t(t-1)/2, hiszen ellenkező esetben legyen n' = t(t-1)/2, válasszunk ki n' embert, a többiről meg tegyük fel, hogy semmilyen klubnak nem tagjai.

Ekkor az összes lehetséges klub-párt felírjuk egy-egy kártyára (tehát lesz t(t-1)/2 kártyánk), azt pedig tetszőlegesen kiosztjuk a lakosoknak. Ha egy lakos mondjuk azt a kártyát kapja, hogy (A klub, B klub), akkor ő az A és B klubnak lesz a tagja.

Ez egy olyan konstrukció, ahol bármely két klubnak van közös tagja (hiszen valamelyik lakos megkapta azt a kártyát, amin pont ez a két klub szerepel), és nincs olyan 3 klub, akinek van közös tagja (hiszen minden lakos csak 2 klubnak a tagja).

De a feladat nem azt mondja, hogy hogy pl. 4 klubnak akkor van közös tagja, hogyha 1 ember mind a 4-ben benne van... például, ha vesszük ezeket a halmazokat:

{a,b,c,d,e,f}

{f;g;h;i}

{a;g;j}

{b;i;j}

Itt nemcsak bármely kettőnek, hanem bármely háromnak van közös tagja (de nem ugyanaz a személy).

Előző: de, a feladat ezt tiltja. Ha 3 klubnak van közös tagja, akkor az a közös tag mind a három klubnak a tagja.

Valszeg a páronkénti közös taggal kevered, de az meg a feladat szövege szerint mindig van.

Az általad leírt példán nincs olyan 3 klub, aminek lenne közös tagja.