Pititci cu case colorate

[ver...@yahoo.com]

Salut,

Uite o problema pe care am auzit-o de curand. Tipul care mi-a zis-o o
stia de la un olimpic national la mate. Problema se vrea sa fie grea
dar solutia e foarte simpla.

---
Ai un sat cu N pitici. Ei au casele vopsite fie Verde fie Rosu. In
fiecare zi e ziua unui pitic (se considera ca anul are N zile).

De ziua lui pititcul isi vopseste casa. Culoarea aleasa e culoarea
majoritara printre casele prietenilor sai. Adica daca are 9 prieteni si
5 au casa Rosie iar 4 au casa Verde, atunci isi va vopsi casa Rosie.

Prieteniile nu se schimba de-a lungul timpului si nici nu sunt
tranzitive.
---

Enjoy,
Rares

[stra...@gmail.com]

Am inteles enuntul problemei dar nu am inteles cerinta ei. Vrei, te
rog, sa postezi si cerinta?

[Rares Vernica]

Scuze!

Cerinta este sa demonstrezi ca dupa un numar de zile toti piticii o sa
aiba case de aceeasi culoare.

Rares

[stra...@gmail.com]

Ok, am inteles si cerinta. Dupa parerea mea enuntul ar trebui sa mai
specifice si cazul in care un pitic are un nr par de prieteni si
jumatate au casa rosie iar alta jumatate casa verde. Personal cred ca
in cazul asta nu ar trebui sa-si schimbe culoarea casei.
As putea sa-ti dau un exemplu de grup de pitici prieteni care sa nu isi
schimbe culorile caselor niciodata. Sa presupunem ca avem asa:
V V V R R R
R
V=pitic cu casa verde
R=pitic cu casa rosie.
Presupunem ca R-ul de jos e prieten cu toti piticii iar restul nu sunt
prieteni decat cu cei de aceeasi culoare. Adica din grupa VVV nu exista
prietenie cu grupa RRR.
In cazul asta oricum ai pune-o, culorile caselor nu se schimba.
Un pitic din grupa VVV are majoritatea verzi, unul din RRR are
majoritatea rosii iar piticul singuratic (prieten cu toti) nu poate
gasi o majoritate. Deci tot sistemul este stabil.
Dupa parerea mea, daca n-am gresit in ipoteze si presupuneri, am reusit
sa demonstrez ca exista unele cazuri in care sistemul are ambele culori.

[stra...@gmail.com]

A, si inca ceva. Cred ca in general, daca reusesti sa imparti un grup
in cel putin doua subgrupuri astfel incat sa nu existe prietenii intre
membrii celor doua grupuri atunci problema e ca cele doua grupuri pot
ajunge sa aiba culori distincte.
Dar daca avem insa un grup in care toti sunt prieteni reciproci atunci
putem avea mai multe cazuri:

1) Numar par de prieteni
1.1) Jumate rosii jumate verzi. In cazul asta cel care va incepe
sa-si schimbe culoarea casei va face ca toti sa isi schimbe casa in
aceeasi culoare. La inceput sistemul ea simetric dar odata cu
schimbarea culorii a aparut o rupere de simetrie care da totul peste
cap. Se poate demonstra cazul asta prin inductie pornind de la N=2.
1.2) Cel putin 50%+1 au casa de o anumita culoare =>de la inceput
exista asimetrie=> sistemul ajunge in culoarea predominanta.

2) Numar impar de prieteni:
2.1) Exact 50%+1 au casa de o culoare iar restul de cealalta. E
clar ca cei care au casa in culoarea majoritara vor avea jumatate de
prieteni de o culoare si cealalta de alta culoare asa ca ei nu-si vor
putea schimba culaorea casei. In schimb, cei care sunt "in minoritate"
cor trebui sa se supuna regulii si is vor schimba culoarea. Rezulta ca
toti vor ajunge sa aiba culoarea majoritara.
2.2) Minim 50%+2 au o anume culoare iar restul alta culoare=>
Majoritatea invinge si toate casele ajung sa fie pictate in aceeasi
culoare.

In cazul in care exista doua astfel de grupuri de prieteni reciproci si
cel putin unul dintr-o grupa are un prieten in cealalta grupa atunci
treburile se complica. Si cred ca exista mai multe cazuri in care
culorile nu se schimba.

[Rares Vernica]

Nu stiu ce se intampla cand un pitic are numarul de prieteni cu care
verzi egal cu numarul de prieteni cu case rosi.

Oricum, exemplul nu prea functioneaza. Daca R-ul de jos e prieten cu
vre-un V de sus atunci si acel V e prieten cu R! Adica prietenia e
simetrice.

Rares

[Rares Vernica]

> A, si inca ceva. Cred ca in general, daca reusesti sa imparti un grup
> in cel putin doua subgrupuri astfel incat sa nu existe prietenii intre
> membrii celor doua grupuri atunci problema e ca cele doua grupuri pot
> ajunge sa aiba culori distincte.

Ar fi ciudat daca pitici s-ar imparti asa. As putea zice ca avem doua
sate in loc de unul singur. :)

> In cazul in care exista doua astfel de grupuri de prieteni reciproci si
> cel putin unul dintr-o grupa are un prieten in cealalta grupa atunci
> treburile se complica. Si cred ca exista mai multe cazuri in care
> culorile nu se schimba.

Cazul asta e cel mai probabil.

Rares

[stra...@gmail.com]

VVV RRR
R
Tu ai spus asa:
"Daca R-ul de jos e prieten cu vreun V de sus atunci si acel V e

prieten cu R! Adica prietenia e simetrice"

Si eu spun: "si ce daca?"
Oricare dintre cei trei V are 2 prieteni V si unul R. Deci majoritarea
este V. Deci nu-si schimba culoarea. R-ul de jos are egalitate printre
prieteni. Chiar daca-si schimba culoarea in vreun fel, problema ramane
quazi neschimbata. R-ul de jos sa zicem ca-si schimba totusi culoarea
in V. Atunci fiecare dintrei cei 3 V de sus va avea numai prieteni cu
casa verde. In caz ca R-ul singuratic devine V, atunci cei din grupul
RRR vor avea tot majoritatea de prieteni R (doi V si un R). Deci cei 3
R nu-si vor schimba culoarea. Problema ramane in picioare.
Gresesc?

[Rares Vernica]

Ok, am gresit!

Oricum, nu cred ca solutia e completa. Tot ce ai facut a fost sa iei
cateva cazuri particulare care iti conveneau si pentru ele ai demonstrat
ca satul se stabilizeaza. Ar fi fost mai interesant sa propui o solutie
generala care sa acopere toate cazurile.

Problema nu se preteaza la demonstrat de teoreme sau la demonstratie
prin inductie...

Numai bine,
Rares

[Catalin Porneala]

Mai cine e stracini asta?

Lapi

[Razvan Rotaru]

Un prieten. Eu l-am invitat. De ce?

[Catalin Porneala]

Pai macar sa-si puna si el numele sa stim cine este.

Lapi

[Cristian Ivan]

Scuze ca nu m-am prezentat. Sunt Cristi (Ivan) si am fost coleg de clasa si banca de-al lui Razvan.

[Cristian Ivan]

Mai, ce sa zic, nu stiu daca se poate face o demonstratie la problema respectiva. Un motiv ar fi faptul ca exista contraexemple la ceea ce se cere sa se demonstreze.

Solutia generala cred ca ar trebui sa cuprinda doua parti. Una in care sa se precizeze cazurile in care sistemul ajunge intr-o stare uniforma iar alta sa precizeze cazurile in care nu se poate ajunge la asta. Cred ca o parte a demonstratiei am facut-o deja (cea cu grupurile care duc sigur la uniformizare). In schimb la partea cealalata nu m-am mai gandit. Cred ca o metoda de abordare ar fi una cu grafuri neorientate in care nodurile sa fie piticii. Dar sincer sa fiu acum nu-mi pica nici o idee.

 

 

 

Cristi
 

[Rares Vernica]

OK, poate sa ramana asa.

Rares

______________________________________________________
Click here to donate to the Hurricane Katrina relief effort.
http://store.yahoo.com/redcross-donate3/

[Cristian Ivan]

Revin cu niste comentarii asupra problemei.
Sistemul nu numai ca este sensibil la conditiile initiale (distributia culorilor si  a prieteniilor) ci si la  punctul de start. Un acelasi sistem  poate sa ajunga la o singura culoare sau sa ramana stabil in doua culori si in functie de piticul care isi coloreaza primul casa.
Exemplu:

RRR      VVR
        R

Consideram grupul RRR ca avand prietenii reciproce plus prietenie cu piticul "singuratic" R de jos dar nu cu VVR. Acelasi lucru si cu grupul  VVR.
Daca primul care trebuie sa-si coloreze casa e vreunul din cei doi V atunci sistemul ajunge sa aiba culoarea rosie (fiecare din cei doi V are un prieten cu casa verde si doi cu rosu=> isi schimba culoare in rosu). Daca in schimb primul este piticul R din grupul VVR atunci el isi va schimba culoarea in verde (are doi cu casa verde si unul cu casa rosie). Mai departe sistemul ajunge in starea pe care am mai discutat-o deja si ramane stabil cu doua culori. Remarc faptul ca problema se complica si mai mult decat am spus la inceput.
Cred ca este ceva asemanator cu jocul life.


Cristi.