Problema a fost propusa de Zoltan Szabo, care a primit punctajul aferent acesteia (15 puncte). Multumim pentru propunere!

SoluĊ£ii corecte:  Traian Dajma, Jean Henry Berevoescu, Mihaela Voinescu. Ioan Scutaru si Stefan Gatachiu dau solutii corecte pentru cel mai lung lant, si solutii aproape optime pentru cel mai scurt lant.

 

Traian Dajma:

Pentru cel mai lung traseu avem:

Longest: 53 noduri, 52 segmente = 1 - 2 - 4 - 3 - 6 - 7 - 3 - 2 - 5 - 4 - 7 - 8 - 13 - 7 - 12 - 6 - 11 - 17 - 12 - 18 - 13 - 19 - 8 - 9 - 4 - 8 - 14 - 9 - 10 - 5 - 9 - 15 - 10 - 16 - 21 - 20 - 14 - 19 - 20 - 15 - 21 - 24 - 20 - 23 - 24 - 25 - 22 - 23 - 18 - 17 - 22 - 18 - 19.

Cel mai scurt ramane tot 25 noduri, 24 segmente: 1 - 11 - 25 - 16 - 2 - 4 - 3 - 22 - 24 - 5 - 4 - 12 - 23 - 15 - 4 - 19 - 17 - 6 - 10 - 21 - 19 - 13 - 8 - 14 - 19

 

Jean Henry Berevoescu:

Numarul de muchii fara simplificari in desen este: 52

Considerind toate segmentele coliniare (i.e. simplificabile), numarul total de muchii simplificate este: 21

Decti teoretic, lungimea minima ar fi 21 si lungimea maxima 52.

Practic, lungimea minima va fi mai mare de 21, pentru ca trecerile intre traversarile figurilor cu segmente simplificabile maxim (romburile si dreptunghiurile) nu pot fi facute fara “pierderi” in eficienta simplificarii. Cel mai scurt lant eulerian pe care l-am gasit parcurge romburile cu laturi simplificate la maxim, in detrimentul segmentarii liniei (2, 19) in doua segmente: (2, 4), (4, 19) si dreptungiurile cu cite o latura segmentata: (3, 4) si (4, 5), respectiv (17, 19) si (19, 21) – cu lungimea rezultanta de 24.

Lantul eulerian cu lungime 24 descris mai sus este:

(1, 11, 25, 16, 2, 4, 12, 23, 15, 4, 3, 22, 24, 5, 4, 19, 21, 10, 6, 17, 19, 14, 8, 13, 19)

Un lant eulerian cu lungime maxima (52) este:

(1, 2, 4, 3, 2, 5, 4, 7, 8, 4, 9, 8, 14, 9, 15, 10, 5, 9, 10, 16, 21, 20, 24, 21, 15, 20, 14, 19, 20, 23, 24, 25, 22, 23, 18, 17, 22, 18, 19, 13, 18, 12, 17, 11, 6, 7, 12, 6, 3, 7, 13, 8, 19)

 

Mihaela Voinescu:

Pas1. Imaginea este formata din 52 de muchii.

Pas2. De asemenea este fromata din 21 de segmente care nu mai pot fi prelungite (care nu fac parte din alt segment) astfel:

6 segmente oblice spre dreapta (1,11); (4,12); (8,13); (14,19); (15,23); (16,25)

6 segmente oblice spre stanga (2,16); (4,15); (8,14); (13,19); (12,23); (11,25)

5 segmente verticale (6,17); (3,22); (2,19); (5,24); (10,21)

4 segmente orizontale (3,5); (6,10); (17, 21); (22, 24)

Notam cu A multimea acestor 21 de segmente.

=> 21 <= Lungimea oricarui lant eulerian simplificat <= 52.

Pas3. Graful are 2 varfuri de grad impar (varf 1 si varf 19), restul fiind de grad par. => admite un lant eulerian si acesta va porni din unul din varfurile de grad impar si se va termina in celalalt varf de grad impar.

Pas4Lant eulerian simplificat de lungime maxima se obtine schimband in fiecare nod directia si toate segmentele sale sunt muchii. Are lungimea 52 (cat numarul total de muchii):

1, 2, 5, 4, 2, 3, 4, 7, 3, 6, 7, 12, 6, 11, 17, 12, 18, 17, 22, 18, 23, 22, 25, 24, 23, 20, 24, 21, 20, 15, 21, 16, 10, 15, 9, 10, 5, 9, 4, 8, 9, 14, 8, 19, 14, 20, 19, 13, 7, 8, 13, 18, 19

Pas5.

Multimea A este formata din 4 cicluri “izolate” intre ele si fata de restul segmentelor din A (in sensul ca din orice varf al fiecarui ciclu nu pornesc decat segmente din multimea A apartinand acelui ciclu):

4,12,23,15,4,

3,5,24,22,3

6,10,21,17,6

1,11,25,16,2,19,13,8,14,19

Ca sa le conectam trebuie sa avem noduri intermediare (ele ar avea cel putin gradul 4 in noul lant format).

- Ca sa obtinem un lant eulerian simplificat de lungime 21, ar trebui sa nu divizam nici unul din segmentele din multimea A (0 puncte de intersectie intermediare). Contradictie cu propozitia anterioara.

- Ca sa obtinem un lant eulerian simplificat de lungime 22, ar trebui sa divizam in 2 sub-segmente un singur segment din multimea A (1 punct de intersectie intermediar si el ar trebui sa fie varf pentru celelalte 3 cicluri din A). - nu e cazul imaginii noastre

- Ca sa obtinem un lant eulerian simplificat de lungime 23, ar trebui

sau sa divizam in 3 sub-segmente un singur segment din multimea A (2 puncte de intersectie intermediare coliniare si cele 2 puncte intermediare ar trebui sa fie varfuri in celelalte 3 cicluri din A distincte => 2 cicluri din A au acelasi varf) – nu e cazul imaginii noastre

sau sa divizam doua din segmentele din multimea A in cate 2 sub-segmente (2 puncte de intersectie intermediare necoliniare si 2 cicluri din A ar avea acelasi varf ) – nu e cazul imaginii noastre


Un lant eulerian simplificat de lungime minima (24) este:

1, 3, 5, 24, 22, 3, 6, 10, 21, 17, 6, 11, 25, 16, 2, 4, 12, 23, 15, 4, 19, 13, 8, 14, 19