7. Zadatak

Prvo rješenje:

Broj parova klubova je

$$\frac{20\cdot19}{2}=190.$$

Za svaki par $(i,j)$ takav da je $1\le i<j\le20$ odaberimo i označimo sa $A_{ij}$ jednog stanovnika koji je član $i$-tog i $j$-tog kluba.

Stanovnici $A_{ij}$ su svi različiti zbog uvjeta da svaki stanovnik može biti član najviše dva kluba. To pokazuje da na otoku mora biti barem 190 stanovnika.

S druge strane, ako se na otoku nalaze samo stanovnici $A_{ij}$, $1\le i<j\le20$, uvjeti zadatka su zadovoljeni. Zato je najmanji mogući broj stanovnika točno 190 (a ne veći).

Za fiksan $i$, u $i$-tom klubu se nalazi barem 19 stanovnika $A_{ij}$ za $1\le j\le20$, $j\ne i$. Zbog toga se u svakom klubu može nalaziti još najviše 6 stanovnika.

To pokazuje da ukupan broj stanovnika ne može biti veći od $190+20\cdot6=310$.

No, ako u svaki klub uz stanovnike $A_{ij}$ stavimo po 6 stanovnika koji se nalaze samo u jednom klubu, uvjeti zadatka su zadovoljeni. Zato je najveći mogući broj stanovnika točno 310 (a ne manji).

Drugo rješenje:

Prema uvjetu zadatka mora postojati stanovnik koji je član prvog i drugog kluba. Označimo tu osobu sa $A$ i naznačimo da je $A$ član tih klubova u tablici u kojoj po retcima redom zapisujemo članove klubova.

Budući da osoba $A$ može biti član najviše dva kluba, ta osoba se ne može pojavljivati ni na kojem drugom mjestu u tablici. Slično možemo naznačiti da je osoba $B$ član prvog i trećeg kluba, da je osoba $C$ član prvog i četvrtog kluba, da je osoba $D$ član drugog i trećeg kluba itd.

	1	2	3	$\ldots$
1. klub	$A$	$B$	$C$	$\ldots$
2. klub	$A$	$D$	$\ldots$
3. klub	$B$	$D$	$\ldots$
4. klub	$C$	$\ldots$
$\vdots$

Nastavimo li ovako razmišljati u tablicu ćemo upisati jednu osobu na dva mjesta za svaki par klubova.

Broj parova klubova je

$$\frac{20\cdot19}{2}=190.$$

Iz toga zaključujemo da na otoku ne može biti manje od 190 stanovnika.

Iz načina na koji smo formirali tablicu je vidljivo da ne moramo dodati nijednog drugog stanovnika, tj. 190 stanovnika možemo rasporediti po klubovima tako da svi uvjeti zadatka budu zadovoljeni.

Prvi klub mora imati zajedničkog člana sa svakim od klubova 2, 3, $\ldots$, 20, pa zaključujemo da prvi klub ima barem 19 članova. Na isti način zaključujemo da svaki klub ima barem 19 članova. Budući da svaki klub može imati najviše 25 članova, u svakom klubu se može nalaziti još najviše 6 stanovnika.

To pokazuje da ukupan broj stanovnika ne može biti veći od $190+20\cdot6=310$.

Ako u svaki klub, uz 19 stanovnika za koje znamo da moraju biti članovi tog kluba, stavimo po 6 stanovnika koji će biti članovi samo tog kluba, svi uvjeti zadatka će biti zadovoljeni. Zato je najveći mogući broj stanovnika točno 310 (a ne manji).