Problema familiilor bine împerecheate

Problema familiilor bine împerecheate, prezentată săptămâna trecută, admite mai multe soluții, în funcție de modul în care este interpretată enunțul.

Să presupunem că în ambele familii există bărbați și femei, așa cum sugerează contextul, și că atunci când doi bărbați se îmbrățișează este o singură îmbrățișare (pare cel mai rezonabil, deoarece spunem că Fulano și Mengano s-au îmbrățișat, nu două). Cu toate acestea, pentru ca sărutul pe care x îl dă lui y să fie același cu cel pe care y îl dă lui x, ar trebui să fie un sărut pe gură, ceea ce nu este de obicei cazul în salutările inter-familiale, mai ales dacă se dau două săruturi de persoană de fiecare dată.

Astfel, dacă considerăm că în fiecare întâlnire pupăcioasă se dau patru săruturi și numim A numărul de bărbați Hernández, B numărul de femei Hernández, E numărul de bărbați Fernández și C numărul de femei Fernández, vom avea: A x E = 24 A x C + E x B + B x C = 132/4 = 33

Abordarea «fermiană» a problemei ar consta în a porni de la descompunerile verosimile ale lui 24 în doi factori: 2 x 12, 3 x 8 și 4 x 6, ceea ce dă naștere la câte soluții? Dar, insist, alte interpretări sunt posibile (vezi comentariile de săptămâna trecută).

Există o versiune mai simplă a acestui clasic în care îmbrățișările sunt 21, cu care, pe de o parte, se exclude posibilitatea ca fiecare îmbrățișare să valoreze dublu, și, pe de altă parte, există doar o descompunere verosimilă în doi factori: 21 = 3 x 7.

În ceea ce privește problema salutărilor formale, este foarte simplă dacă ne dăm seama că în fiecare strângere de mână - chiar dacă este una, ca îmbrățișarea - converg două acțiuni manuale individuale (pe care, pentru simplificare, le vom numi «palme»), adică 66 x 2 = 132.

Dacă sunt n persoane la întâlnire și fiecare dă mâna cu toate celelalte, se vor produce n(n-1) «palme», deci n(n-1) = 132. Și nu este nevoie să rezolvăm ecuația de gradul al doilea pentru a vedea că n = 12.

Și în ceea ce privește numărul de persoane care de-a lungul vieții au strâns un număr impar de mâini, Bretos Bursó oferă o soluție ingenioasă foarte în linia CVA (Calculul Vechii Avansate): «Să presupunem că la fiecare strângere de mână cineva separă cele două bețe ale unei cruci pe care o ia din sacul crucilor și dă câte unul fiecărei persoane parte a strângerii. Toate crucile și toate bețele sunt egale. Imediat ce o persoană reunește două bețe formează o cruce și o aruncă în puțul crucilor. Într-un moment oarecare, fiecare persoană este fără bețe (dacă a dat un număr par de strângeri) sau cu un băț (dacă a dat un număr impar). Dar până în acel moment a ieșit un număr par de bețe din sac, un alt număr par a căzut în puț, iar diferența, care este pară, este numărul de persoane care au un băț».

Tabloul rectangular

Rămăseseră restante, de acum două săptămâni, câteva chestiuni relative la problema parcursului calului pe table rectangulare (abordată la vremea sa de însuși Euler), concret în cea de 3x4.

Iată analiza detaliată a lui Salva Fuster: «Desenând graful asociat problemei parcursului calului pentru tabloul 3x4, se obțin două cicluri (1-7-9-2-8-10-1 și 3-5-11-4-6-12-3) cu o pereche de muchii suplimentare care le conectează: 2-11 și 3-10.

Dacă se începe din colțul superior stânga (căsuța 1) și nu se restricționează căsuța de sosire, vom avea două posibilități: 1-7-9-2-8-10-3-5-11-4-6-12 1-7-9-2-8-10-3-12-6-4-11-5

Dacă alegem ca și căsuță de început prima sau ultima din al doilea rând, vom avea diverse posibilități.

De exemplu, dacă alegem căsuța 5, parcursurile complete vor fi: 5-11-4-6-12-3-10-8-2-9-7-1 (coincide cu 1-7-9-2-8-10-3-12-6-4-11-5 dar parcursă în sens invers) 5-11-4-6-12-3-10-1-7-9-2-8 5-3-12-6-4-11-2-9-7-1-10-8 (simetrică cu cea anterioară) 5-3-12-6-4-11-2-8-10-1-7-9 (inversată și simetrică cu 1-7-9-2-8-10-3-12-6-4-11-5)

Dacă alegem ca și căsuță de început oricare care nu este un colț sau oricare extremă a celui de-al doilea rând, nu vom putea face un parcurs complet.

Prin urmare, dacă nu mă înșel, vor fi doar 3 soluții distincte dacă descontăm simetriile, rotirile sau parcursurile în sens invers.

Carlo Frabetti