7. Zadatak

Prvo rješenje.

Među istaknutim pravcima nazovimo $5$ međusobno paralelnih pravaca redom $p_1,p_2,p_3,p_4$ i $p_5$. Analogno, pravce u drugom smjeru imenujemo s $q_1,q_2,q_3,q_4$ i $q_5$. Četiri točke koje se nalaze na točno jednom pravcu nazvat ćemo kutnima. Osam točaka koje se nalaze na pravcima $p_1,p_5,q_1$ i $q_5$ nazvat ćemo rubnima. Ostale četiri točke nazvat ćemo središnjima.

Promotrimo pravce $p_1,p_2,p_3,p_4$ i $p_5$. Na njima smije biti odabrano najviše $5$ točaka, jer bi u suprotnom postojale barem dvije odabrane točke na istom pravcu. Na tih $5$ pravaca ne nalaze se $2$ (kutne) točke, no te dvije kutne točke nalaze se na istom pravcu $q_3$, pa od te dvije točke možemo odabrati najviše jednu. Zato je najveći broj točaka među kojima nema vezanih manji ili jednak $6$.

Dokazat ćemo da je taj broj jednak $6$ i odredit ćemo broj odabira takvih točaka. Primijetimo da kako bi među šest odabranih točaka ne bi bilo vezanih, poštujući argumente s početka, po jedna se mora nalaziti na svakom od $5$ paralelnih pravaca $p_1,p_2,p_3,p_4$ i $p_5$, te jedna od tih točaka mora biti kutna.

Kutnu točku koja se ne nalazi ni na jednom od pravaca $p_i$ možemo odabrati na dva načina.

Pogledajmo pravce $p_1$ i $p_5$. Imamo dva odabira za točku na pravcu $p_1$. Svaka od tih točaka koju možemo odabrati pravcu leži na istom pravcu kao neka od dvije točke na pravcu $p_5$. Zato nakon odabira te točke na pravcu $p_1$, na jednoznačan način odabiremo točku na pravcu $p_5$.

Pogledajmo pravce $p_2$ i $p_4$. Odabrana kutna točka nalazi se na pravcu $q_3$, pa zato ne smijemo odabrati središnje točke na tim pravcima.

Zato opet zapravo imamo samo dva odabira točke na pravcu $p_2$. Analogno kao u prošlom slučaju, ovisno o odabiru te točke, jednoznačno će biti određena točka na pravcu $p_4$.

Konačno, na pravcu $p_3$ ne možemo odabrati središnju točku jer bi bila vezana s onim točkama koje smo odabrali na pravcima $p_1$ i $p_5$.

Zato možemo odabrati samo neku od dviju kutnih točaka (na dva načina).

Ukupan broj podskupova umnožak je svih mogućnosti odabira, i iznosi $2^4=16$.

Drugo rješenje.

Nazovimo točke i pravce kao u prošlom rješenju.

Obojimo točke na pravcima $p_1,p_3$ i $p_5$ u crno, a ostale točke u bijelo. Primijetimo da nikoje dvije točke različite boje ne pripadaju istom pravcu. Nadalje, primijetimo da su crne i bijele točke međusobno simetrične (os simetrije je pravac paralelan sa stranicama kvadrata koji čine tih $16$ točaka i prolazi središtem tog kvadrata). Zato je u ovom zadatku dovoljno gledati točke samo jedne boje.

Najveći broj točaka koji možemo odabrati jednak je dvostrukom broju crnih točaka koje možemo odabrati. Nadalje, ukupan broj podskupova s najvećim brojem elemenata jednak je kvadratu broja podskupova s najvećim brojem crnih elemenata.

Kako se sve crne točke nalaze na tri pravca. Zato možemo odabrati najviše $3$ crne točke koje nisu vezane, a onda to znači da možemo odabrati ukupno najviše $6$ točaka tako da nikoje dvije nisu vezane.

Prebrojimo sada sve moguće odabire $3$ vezane crne točke. Nužno je da na svakom od pravaca $p_1,p_3$ i $p_5$ odaberemo točno jednu točku.

Pogledajmo pravce $p_1$ i $p_5$. Imamo dva odabira za točku na pravcu $p_1$. Svaka od tih točaka koju možemo odabrati pravcu leži na istom pravcu kao neka od dvije točke na pravcu $p_5$. Zato nakon odabira te točke na pravcu $p_1$, na jednoznačan način odabiremo točku na pravcu $p_5$.

Promotrimo sada pravac $p_3$. Na njemu ne možemo odabrati središnje točke jer bi one bile vezane s onim točkama koje smo odabrali na pravcima $p_1$ i $p_5$.

Zato na pravcu $p_3$ možemo odabrati samo jednu od dviju kutnih točaka (na dva načina).

Ukupan broj odabira crnih točaka među kojima nema vezanih zato je jednak $2^2=4$, a onda ukupan odabir šest točaka među kojima nema vezanih jednak je $4^2=16$.