Motto: Lipsa talentului se observă atunci când încerci să dovedeşti că îl ai. (Mihai Pauliuc)

C. Sfere pe Marte  (a se citi si comentariile)

Aţi coborât pe Marte în prima misiune cu echipaj uman. Acolo aţi găsit 7 sfere care arată identic pe dinafară. De la bază vi s-au dat următoarele indicaţii:

1. Fiecare sferă are în interior o anumită culoare.

2. Una din culori apare majoritar (în cel puţin 4 sfere).

3. Când se ating două sfere cu aceeaşi culoare în interior, incep sa straluceasca (evdeint, stralucirea dispare odata ce ele se departeaza).

          Vi s-a cerut ca în final să aveţi în mână o sferă care cu siguranţă are în interior culoarea cea mai frecvent întâlnită.

1. Care este numărul minim de comparaţii care să garanteze reuşita ? (10 puncte)

2. O comparatie poate insemna si atingerea simultana a n sfere, fiecare sfera fiind in contact cu celelalte n-1 (pentru cazul n=2 se obtine punctul 1).

Care este numarul minim de comparatii in acest caz ? (15 puncte)

 

Sursă: dupa Macalester  POTW 836

Vezi comentarii
Logheaza-te in site pentru a trimite solutii si comentarii
aatanasiu

Nu am putut gasi o solutie la aceasta problema. Deci astept cu interes orice sugestie de rezolvare.

Pentru a fi sigur, dau si textul originar:

You have just landed on Mars where you find 7 identical-looking spheres.  From prior missions, you know the following:

Each sphere is colored on the inside.

One of the colors occurs for a strict majority of the spheres (4 or more).

When two spheres of the same color touch each other, they both glow.

Your job is to carry out as few comparisons as possible, with the goal of  holding in your hand a sphere that you are certain has the majority color.

What is the smallest number of comparisons that is guaranteed to work? 


Ady

Cred ca este vorba de o greseala de traducere. "Glow" se poate traduce si prin "a straluci". Deci sferele nu explodeaza...

Numai bine!

Ady Nicolae


aatanasiu

Este foarte posibil ca aceasta sa fie traducerea corecta

(eu am fost indus in eroare de faptul ca in final raman in mana cu o sfera).

Fac modificarile in text si adaug un punct suplimentar la problema - nu este obligatoriu ca o comparatie sa insemne atingerea a doua sfere.

Se pot atinge simultan pana la 4 sfere.
 


Ady

Intrebare:

La punctul 2 (suplimentar) ati spus ca putem atinge simultan n sfere, iar in comentarii ati spus ca putem atinge maxim 4 sfere simultan. Inseamna ca n=max 4?


aatanasiu

Da, cred ca n_max=4 (4 sfere asezate in forma de piramida).

Nu stiu deocamdata o constructie geometrica cu 5 sfere, in care fiecare sa fie tangenta la toate celelalte patru.


xipehudu_xifoforu_2004

Hmmm ... in cazul al doilea, in care pot compara 3 sau 4 sfere deodata, casre din ele o sa strraluceasca? doar cele implicate, sau toate?

De ex.

A) daca compar 4 sfere avind culorile C1, C2, C3, C1, care o sa strealuceasca? doar cele cu C1, pentru ca numai ele sint implicate? sau toate patru, pentru ca exista cel putin o potrivire?

B) daca compar 4 sfere avind culorile C1, C1, C2, C2, e clar ca toate o sa straluceasca (indiferent de raspunsul la prima mea intrebare), dar vor straluci oare in acelasi fel? sau sferele C1 stralucesc "mai altfel" decit cele C2, permitind astfel o separare?

 


aatanasiu

Cred ca deja v-ati clarificat nedumerile.

A. Evident, vor straluci numai sferele care au aceasi culoare.

La trei sfere A,B,C avand culorile A - x,, B - y, C - x vor straluci numai A si C care se afla in atingere si au aceeasi culoare x.

B - desi se atinge de celelalte, nu va straluci pentru ca nu coincide culoarea.

 

B. Nu exista diferente de stralucire.

Deci daca aveti 4 sfere care se ating intre el si stralucesc toate, atunci

- toate patru au aceeasi culoare, sau

- doua au o culoare, iar alte doua au alta culoare.


szabozoltan

Am trimis o rezolvare in care am considerat, ca exista strict 4 sfere majoritare.

Am considerat, ca n-1 sfere se pot atinge doua cate doua intr-un spatiu n-dimensional (3 sfere in plan, 4 sfere in spatiu, 5 sfere in spatiu 4D, etc).