amb el suport de    
Marató de problemes. 2015
Problema 9. Problema especial
(primera part, resposta numèrica a) i b): 3 punts;
segona part, explicació i  apartat c): 3 punts;
qüestió suplementària: 1 punt.)



No dubteu en demanar aclariments a través del pseudo-fòrum de l'activitat.  Com s'ha fet fins ara, si escau es posaran en comú a la web  les qüestions plantejades i les respostes donades.


En l'estudi dels grafs, conjunts de punts connectats per línies o segments,  sovint interessa considerar el problema de seleccionar alguns segments del graf de manera que aquests segments ens permetin connectar  tots els punts i que la magnitud total dels segments considerats sigui la més petita possible.
En aquest problema en direm "connexió minimal".
El gràfic que s'adjunta a la dreta dóna un exemple de la recerca d'una "connexió minimal".

En poden ser exemples el disseny de camins per connectar poblacions, o el desplegament de cables que han d'unir nodes de connexió. 

 En el problema següent considerarem com a magnitud de cada segment que uneix dos punts, la seva longitud..




En un sistema de coordenades cartesianes (*) es consideren els punts  A=(0,0), B=(5,–1), C=(3,3), D=(1,3), E=(7,10) i F=(0,9).
 
(*) eixos perpendiculars; la mateixa graduació en els dos eixos
a) Quin és el mínim nombre de segments que permeten definir una connexió minimal en aquest conjunt de punts?
b) Quina és la distància total més petita que pot tenir, per als punts donats, el conjunt de segments de la connexió minimal?    
(es demana arrodonida amb 2 decimals)

Nota: en els grafs, si volem connectar tres punts, diem-ne M, N, P i és possible anar de M a P passant per N, encara que es pugui dibuixar  "tot recte",
en realitat s'han de considerar dues connexions. 
 
Tindreu a la web un formulari per enviar la resposta numèrica a aquests dos apartats


Com a segona part de l'activitat haureu d'enviar un document .PDF  amb el raonament que us ha fet arribar al disseny de la connexió minial entre els sis punts donats i també una explicació de l'apartat següent.

c) Expliqueu amb detall en quina zona (o en quines zones) pot estar situat un setè punt G perquè la connexió minimal en el conjunt dels set punts A, B, C, D, E, F i G estigui formada pels segments que ja teníem en la connexió minimal dels sis punts A, B, C, D, E i F i un altre segment, que naturalment unirà el punt nou amb un dels sis punts del conjunt inicial.
Tindreu a la web un formulari per enviar un document PDF amb l'explicació
raonada de les solucions als 
apartats a) b) i c)


En altres circumstàncies es tracta de connectar punts però sense que, necessàriament s'hagin de fer servir els segments que uneixen dos dels punts del conjunt i de manera que es poden introduir nous punts per a algunes connexions.

En el cas d'un triangle el punt que té la propietat que la suma de distàncies d'aquest punt als tres vèrtexs del triangle és mínima es coneix com a punt de Fermat. En concret aquesta distància és sempre més petita que la suma de dos costats del triangle i, per tant en problemes de distància mínima s'ha de tenir molt en compte.

d) Dissenyeu un conjunt de segments (que poden tenir extrems en punts que no siguin del conjunt)  que permeti connectar els sis punts A, B, C, D, E, F,  donats com a dades en aquest problema,  de manera que la suma de distàncies sigui mínima.

Tindreu a la web un formulari per enviar, independentment d el'anterior,  un document PDF
amb l'explicació d'aquest apartat del punt de Fermat