Školjka

%V0 $7 \cdot 8 \cdot 14$ je kvadrat. a i inace, $2$ je u ovom zadatku "jednak" broju $8$, a i malo je klimavo reci da je nesto "optimalan razlog" bez nekog jakog argumenta. takoder, fali ti $(7, 8, 14)$ medu onim trojkama. rjesenje koje imam je daleko od nekog elegantnog i sumnjam da postoji neko super elegantno, ali evo mozda nekad nekom dobro dode: gledam rastav svakog broja na proste faktore i bitna nam je samo parnost potencije. tj $8 = 2^3$ nam igra istu ulogo kao $2$. zapisimo sada brojeve u tablicu gdje nam $1$ oznacava neparnu potenciju na doticnom prostom faktoru a $0$ parnu $\begin{tabular}{ l | l l l l } - & 2 & 3 & 5 & 7 \\ \hline 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 1 & 0 \\ 6 & 1 & 1 & 0 & 0 \\ 7 & 0 & 0 & 0 & 1 \\ 8 & 1 & 0 & 0 & 0 \\ 9 & 0 & 0 & 0 & 0 \\ 10 & 1 & 0 & 1 & 0 \\ 12 & 0 & 1 & 0 & 0 \\ 14 & 1 & 0 & 0 & 1 \\ 15 & 0 & 1 & 1 & 0 \\ \end{tabular}$ $11$ i $13$ namjerno nisam dodao jer je jasno da njih smijemo "besplatno" dodati u skup $M$. kad sad pogledamo koliko ima kojih uredenih cetvorki dobivamo sljedecu tablicu: $\begin{tabular}{ l | l l l l } 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ \end{tabular}$ gdje nam sada broj lijevo oznacavo koliko imamo doticnih cetvorki. dokazat cemo da je max broj elemenata od $M$ bas $10$. buduci smo rekli da smo $11$ i $13$ vec uzeli, treba odabrati $8$ elemenata iz $M$. zapravo zelimo odabrati neke redove iz tablice tako da ne postoje $3$ reda koja bi zbrojena po stupcima davala $0$ (tj "parno") na svakom mjestu. to mozemo npr uzimajuci $2$ elementa $(0, 0, 0, 0)$, te $6$ najnizih u tablici. dokazimo sada da je nemoguce odabrati $9$ elemenata iz tablice s trazenim svojstvom. $(A)$ ako ne uzmemo $(0, 0, 0, 0)$, od preostalih $10$ moramo uzeti $9$. primjetimo da nesmijemo istovremeno uzeti niti $(1, 0, 0, 0), (0, 0, 0, 1), (1, 0, 0, 1)$ niti $(0, 1, 0, 0), (0, 0, 1, 0), (0, 1, 1, 0)$, dakle iz obje trojke moramo izostaviti bar jednoga a kako su trojke disjunktne necemo moci uzeti $9$ elemenata. $(B)$ ako uzmemo $(0, 0, 0, 0)$, mozemo "besplatno" uzeti jos jedan takav ali nesmijemo ih uzeti sva tri. takoder, od preostalih elemenata nesmijemu uzeti nijedan dupli bas jer smo uzeli $(0, 0, 0, 0)$. sada moramo uzeti $7$ od donjih $8$ ali to necemo moci po potpuno istom argumentu kao u prethodnom slucaju. evo, nije posebno elegantno i iskreno ne vjerujem da postoji neki pametan nacin za rjesiti al nadam se da ce nekome pomoci nekada :)