Blog d’en Xavi

Una variació del problema del mínim de moviments per obtenir un conjunt apinyat al reticle amb aplicació:

Sigui A un conjunt de . Volem trobar el mínim de moviments pels quals cada element de A pot transformar-se en un únic punt a. O sigui, per a cada A conjunt de , trobar un punt (no té perquè ser únic ni estar a A) tal que sigui mínima.

Noteu que almenys un d’aquests sempre existirà. Si denotem la suma mínima com (i.e., ), aleshores és el nombre mínim de moviments (entesos com simplement els passos discrets per anar de qualsevol element de A a , aquí no compt res d’espais en blanc com en anteriors problemes) necessaris per a què tots els punts de A “convergeixin” a

Això té una aplicació òbvia: si tenim n persones (i identifiquem cada persona amb les seves coordenades cartesianes al Pla), aleshores és un punt on és més fàcil trobar-se (en conjunt la distància que ha de recorre cada persona per arribar-hi és menor (o igual) que per a qualsevol altre punt).

Quina seria la fórmula de e(A)?. Crec que es podria provar que si A i B són disjunts, (algú s’atreveix?; d’aquesta no n’estic tan segur com les anteriors). I llavors obtenir que