Rješenja zadatka "skakavac 2012 drugo kolo ss2 2" korisnika "leonstaresinic"

Netočno

28. svibnja 2014. 20:53 (10 godine, 9 mjeseci)

Korisnik: leonstaresinic
Zadatak: skakavac 2012 drugo kolo ss2 2 (Sakrij tekst zadatka)

Neka je $M$ podskup skupa $\{1, 2, ..., 15\}$ koji ne sadrži $3$ elementa čiji je umnožak potpun kvadrat. Odredi maksimalan broj elemenata skupa $M$ .

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Primjetimo da je najveci kvadrat koji mozemo dobiti jednak 15*12*5 ili 12* 10 * 6 = 30^2.
Provjerom svih kvadrata do 30 (uz elemininaciju slucajeva u kojima se radi o kvadratima prostih brojeva i nekih drugih) dobiju se sljedeci skupovi brojeva ciji umnosci daju potpun kvadrat :

(1,2,8) (1,3,12) (1,4,9) (2,3,6) (2,4,8) (2,5,10) (2,6,12) (2,8,9) (3,4,12) (3,6,8) (2,7,14) (3,5,15) (3,9,12) (5,8,10) (12,8,6) (15,10,6) (15,12,5)

Sada se treba odabrati minimalan broj razlicitih brojeva , tako da presjek tog skupa i bilo kojeg od navedenih nije prazan skup.
Primjetimo da se u skupovima najcesce pojavljuju 2 , 3 , 12 i 8.

Razlog zasto je optimalno maknuti npr. 2 umjesto drugih brojeva iz skupova u kojima se on nalazi je taj da bi morali maknuti vise razlicitih brojeva da bi se rijesili svih skupova u kojima se nalazi 2 , sto na kraju dovodi do manjeg rijesenja za velicinu skupa M.

Rijesavanjem slucaja ne stavljanja pojedinog od ovih brojeva u skup M dobije se da M moze imati najvise 10 elemenata , pa zakljucujemo da je 10 rijesenje.

Primjer : {1 , 7 , 8 , 9 ,10 , 11, 12, 13, 14 ,15}

(ako moje rijesnje nije tocno ili ako postoji neko elegantnije molio bih da ga ispravljatelj napise ili da hint za taj nacin rijesavanja , hvala)

Ocjene: (1)

Komentari:

grga, 31. kolovoza 2015. 02:03

$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 :)

%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 :)

Školjka

Ocjene: (1)

Komentari: