|
|
Am mai asteptat o vreme cu solutia, problema este deosebita,
cei ce mai au de-a face cu o olimpiada sau alta sunt rugati sa se opreasca aici din citit si sa incerce o rezolvare pe cont propriu.
Trec la rezolvare, asa cum mi-a venit idea de a rezolva, nu in forma finala, cizelata.
In primul rand trebuie sa vedem ce structura este cea in care traieste normal problema. Desigur ca avem de-a face cu un graf.
In cazul nostru, a da relatia de prietenie intr-o clasa cu N elevi revine la a da:
- cele N varfuri, este bine sa le numerotam, notam cu V multimea lor,
V = {1,2,...,N}
- si dintre cele N(N-1)/2 laturi (segmente) {i,j} pe care le putem forma cu doua varfuri (diferite) trebuie sa alegem o submultime, o notam cu L.
Plecam de la idea ca mai sus avem mereu i diferit de j.
Valentele unui astfel de graf (neorientat) (V,L),
mai exact lista valentelor,
se defineste a fi lista (ordonata) [ val(j) pentru j in V ],
unde val(j) este numarul de laturi din L care contine j-ul .
Pentru un N dat ce fel de grafuri (neorientate) G = (V,L) cu |V| = N varfuri putem avea,
astfel incat in lista valentelor sa avem cel mult o repetare?
Sa notam cu Vlad(N) lista acestor grafuri.
Deci daca
G = (V,L) este in Vlad(N)
atunci G are valentele printre cele N numere
0, 1, 2, 3, ... , (N-1)
(nimeni nu este prieten cu sine insusi...)
si desigur ca valentele 0 si (N-1) nu se pot atinge simultan.
Sa spargem atunci "clasa" Vlad(N) in doua subclase:
Vlad(N, 0) este multimea G-urilor de mai sus care au valenta 0 pentru cel putin un varf.
Vlad(N, *) este multimea G-urilor de mai sus care au valenta (N-1) pentru cel putin un varf.
Sa observam ca avem urmatoarele operatii importante care leaga aceste multimi diferite.
In primul rand avem o operatie de "luare a complementarei", este un fel de dualizare.
Daca ne dam un G = (V,L) atunci G' = (V, L') definit prin
L' = complementara lui L in multimea laturilor {i,j} cu i,j diferite
este o operatie care duce bijectiv
Vlad(N,0) in Vlad(N,*)
si invers. Sensul este usor de explicat, daca ne gandim ca doi elevi care nu sunt prieteni sunt dusmani (ca sa fie clar, in lumea asta nu exista indiferenta),
si schimbam locul celor doua relatii de prietenie si dusmanie.
Deoarece numarul "celorlalti elevi" este mereu (N-1), valentele de prietenie fiind diferite, si cele de dusmanie sunt diferite.
Si invers.
Aceasta trecere la complementara ne poate ajuta deja.
Daca exercitiul ar fi fost un exercitiu cu alegere multipla (multiple choice)
si daca singurele raspunsuri posibile ar fi fost:
Vlad are 0 prieteni,
Vlad are un prieten,
Vlad are doi prieteni,
:::
Vlad are 24 de prieteni,
si daca am sti ca problema *are* raspuns *unic*,
atunci daca raspunsul este R, aceasta trecere de la prietenie la dusmanie ne arata ca un raspuns la fel de bun este
24-R, dar fiind unic raspunsul, dam de R = 24-R ...
Simpla percepere a dualitatii ne da o informatie asupra solutiei.
Desigur ca trebuie sa aratam ca exista o constelatie care realizeaza acest raspuns.
Si trebuie sa aratam ca orice alta constelatie conduce la acelasi raspuns.
Pentru aceasta, incercam sa folosim un argument inductiv de reducere a gradului N.
Observam de exemplu ca daca plecam cu un graf G = (V,L) din Vlad(N,0)
si asociem graful G(-1) (asa il notez) din Vlad(N-1) care are
- varfurile obtinute din V prin indepartarea varfului v(0) cu 0 prieteni
- laturile din L
atunci G(-1) se afla in Vlad(N-1,*).
Reciproc, daca plecam cu un graf G = (V,L) din Vlad(N,*)
si asociem graful G(-1) (tot asa il notez) din Vlad(N-1) care are
- varfurile obtinute din V prin indepartarea varfului v(*) cu (N-1) prieteni
- laturile obtinute din L prin indepartarea celor (N-1) din varful v(*)
atunci G(-1) se afla in Vlad(N-1,0).
In acest mod ne putem reduce inductiv de la Vlad(25) pe rand Vlad(24), Vlad(23), ... , Vlad(3), Vlad(2) .
Anume in mod bijectiv!
Deci trebuie sa intelegem doar Vlad(2) .
Desigur ca la un asa mic numar de elemente din clasa putem sa desenam.
Eu nu pot aici chiarasausor, dar incerc...
Vlad(2) are doua elemente,
- graful cu doua varfuri si nici o prietenie,
- graful cu doua varfuri si singura prietenie posibila,
Deci lista valentzelor (scrisa fara virgule) este
00 si respectiv 11 .
Deoarece valentzele le clasifica suficient de bine (pana la o denumire a varfurilor),
propun sa notam cele doua grafuri cu
G(00), care este graful din Vlad(2,0),
si
G(11), care este graful din Vlad(2,*).
Vlad(3) are tot doua elemente.
Daca (a,b,2) este lista ordonata a valentelor elementului din Vlad(3,*), atunci aplicand operatia de taiere a varfului cu toti prietenii dam de
(a-1,b-1) care este fie (0,0), fie (1,1) . Ultimul trebuie sa-l excludem, altfel am fi plecat cu (2,2,2). Nu se poate.
Deci (a,b,2) este de fapt (1,1,2), desenat ca un triunghi cu doua laturi ingrosate poate.
Daca (0,a,b) este lista ordonata a valentelor elementului din Vlad(3,0), atunci aplicand operatia de taiere a varfului fara prieteni dam de
(a,b) care este fie (0,0), fie (1,1) . Primul trebuie sa-l excludem, altfel am fi plecat cu (0,0,0). Nu se poate. Ce clasa e asta? Dam deci de
(0,a,b) = (0,1,1). Putem desena un triunghi cu o singura latura ingrosata poate.
Pe scurt, daca notam cu G(112) si G(011) cele doua configuratii, unic determinate de valente, am vazut ca
G(112) (-1) = G(00) si
G(011) (-1) = G(11) .
Putem sa scriem aceste relatii in mod formal in sirag:
00 --- 112 si
11 --- 011
si eu le-as scrie de fapt incat liniile sa se incruciseze, dar nu pot aici.
daca trecem la nivelul urmator, putem completa cu
00 --- 112 --- 0112
11 --- 011 --- 1223
si apoi la nivelul urmator
00 --- 112 --- 0112 --- 12234
11 --- 011 --- 1223 --- 01223
si apoi la nivelul urmator
00 --- 112 --- 0112 --- 12234 --- 012234
11 --- 011 --- 1223 --- 01223 --- 123345
si apoi la nivelul urmator
00 --- 112 --- 0112 --- 12234 --- 012234 --- 1233456
11 --- 011 --- 1223 --- 01223 --- 123345 --- 0123345
si tot asa mai departe.
In clasele cu un numar impar N = 2K+1 de elevi,
vedem ca avem o repetare a lui K in ambele configuratii.
In clasele cu numar par de elevi...
La noi avem de-a face cu o clasa cu N=25 de elevi in care prieteniile stau ca in Vlad(25).
Numarul K corespunzator este 12.
Deoarece (elevul, varful din graf) Vlad este unul din cei doi cu valenta repetata, rezulta ca Vlad are 12 prieteni in clasa.
---
df (gauss)
|
Access general
Conţine mesaje necitite
