Problema de división de tierras de Hill-Beck

El problema de reparto de tierras de Hill-Beck es una variante del problema de corte de torta justo propuesto por Tad Hill en 1983 [1] .

Planteamiento del problema

Hay un territorio D adyacente a n países. Cada país estima (a su manera) subconjuntos del territorio D . Los países quieren dividir el territorio D equitativamente entre ellos, donde "equidad" significa división proporcional . Además, las partes asignadas a cada país deben estar conectadas y adyacentes al país asignado . Estas limitaciones geográficas distinguen el problema del clásico problema de corte de torta justo .

Formalmente, cualquier país C i debe recibir partes separadas del territorio D , que denotamos por D i , de modo que las porciones de la frontera entre C i y D estén contenidas dentro de . $C_{i}\taza D_{i}$

Imposibilidad y posibilidad

Hay casos en los que el problema no se puede resolver:

Si hay un punto en el que se concentra todo el valor de la tierra (por ejemplo, un "lugar santo"), entonces es obvio que el territorio no se puede dividir proporcionalmente. Para evitar tales situaciones, asumimos que todos los países asignan un valor de 0 a todos los puntos individuales.
Si D es un cuadrado, hay 4 países que tocan 4 lados de ese cuadrado, y cada país ve todo el valor de la tierra en el límite del lado opuesto del cuadrado, entonces cualquier distribución que conecte, digamos, un país del norte con el deseado el lado sur hace imposible conectar el país oriental con el deseado lado occidental del cuadrado (si estamos hablando de un plano bidimensional). Para evitar tales situaciones, asumimos que todos los países asumen un precio de frontera cero D .

Hill demostró en 1983 que si cada punto en D tiene un valor de 0 para todos los países, y el límite de D tiene un valor de 0 para todos los países, existe una división proporcional sujeta a restricciones de adyacencia. Su prueba se refería solo a la existencia, no presentó ningún algoritmo [1] .

Algoritmo

Cuatro años más tarde, Anatole Beck describió un protocolo para lograr tal división [2] . Esencialmente, el protocolo es una evolución del protocolo " último mínimo ". El protocolo permite que los países soliciten partes del territorio D , entrega la parte con la solicitud más pequeña al solicitante y divide el resto entre los países restantes. Se necesita alguna variación para garantizar que se cumplan las restricciones de adyacencia. $n-1$

Territorio Único Conectado

Si el territorio D es simplemente conectado , se utiliza el siguiente algoritmo:

Encuentre el mapeo de Riemann h que mapea D al círculo unitario , de modo que para todos los países el valor de cualquier círculo centrado en el origen sea 0 y el valor de cualquier radio desde el origen sea 0 (la existencia de tal mapeo h está probada contando argumentos).
Pedimos a cada país que dibuje en el círculo de visualización de la unidad h ( D ) un disco centrado en el origen (centro del disco h ( D )) y un valor de . Esto es posible debido al hecho de que todos los círculos centrados en el origen tienen un valor de 0. ${\tfrac{1}{n))$
Encuentre el disco D 1 con el radio más pequeño r 1 .

Hay dos casos.

Ganador individual

4. Si D 1 es dibujado por un solo país, digamos C i , entonces le damos el disco al país C i . Su valor para otros países es estrictamente menor que , por lo que podemos darle al país C i un pequeño fragmento adicional junto al disco asignado. ${\tfrac{1}{n))$

Para hacer esto, dibujemos un sector que conecte D 1 con el borde del círculo D . Deje que cada país (que no sea C i ) se separe de este sector para que los valores de agrupación del disco y del sector juntos no excedan . Esto es posible debido a la condición de que los valores de todos los radios desde el origen sean 0. Demos al país C i la unión de D 1 y el sector truncado. ${\tfrac{1}{n))$

El territorio restante simplemente está conectado y tiene un valor al menos para los países restantes , por lo que la división se puede continuar recursivamente desde el paso 1. ${\ estilo de visualización {\ tfrac {n-1} {n}}}$ $n-1$

Varios ganadores

Si la parte D 1 ha sido solicitada por k > 1 países, entonces se requieren algunas subastas más sofisticadas para encontrar un país al que podamos dar el disco y el sector de enlace.

5. Elijamos un país ganador arbitrario y llamémoslo el declarante , C 1 . Pídale que agregue un sector que conecte D 1 con su territorio actual y que deje que otros países se aíslen de este sector, de modo que:

Para cualquier país perdedor, el valor de D 1 más el sector cortado no tiene prioridad (esto es posible, ya que el valor de D 1 para ellos es menor que ). ${\tfrac{1}{n))$ ${\tfrac{1}{n))$
Para cualquier país ganador, el valor del sector truncado es menor que . ${\tfrac{1}{n))$

6. Que cada uno de los países ganadores proponga un nuevo radio r (menor que su propuesta inicial), de manera que el valor de la parte cortada del sector más el disco de radio r se valore exactamente en . Elegimos el disco D 2 más pequeño . De nuevo hay dos casos: ${\tfrac{1}{n))$

Si C 1 es uno de los países que solicitó D 2 , simplemente le asignamos el área D 2 (que es un poco más pequeña que la solicitud original D 1 ) y el sector de conexión. C 1 está de acuerdo en que el valor es , y otros países están de acuerdo en que el valor no es mayor que , por lo que podemos continuar recursivamente desde el paso 1. ${\tfrac{1}{n))$ ${\tfrac{1}{n))$

De lo contrario, C 1 acepta que el valor total de D 2 y el sector de conexión es menor que . Todos los perdedores también deben estar de acuerdo con esto, ya que D 2 es menor que D 1 . Por lo tanto, C 1 y todos los demás países que estén de acuerdo con esto quedan eliminados del conjunto de ganadores. ${\tfrac{1}{n))$

7. Entre los ganadores restantes, elegiremos un nuevo solicitante C 2 . Que agregue otro sector que conecte D 2 con el territorio actual, y que otros países trunquen este sector como en el paso 5.

Tenga en cuenta que ahora el territorio D 2 está conectado con dos territorios: C 1 y C 2 . Esto es un problema ya que hace que el resto del área sea incoherente. Para resolver este problema, se permite que C 2 elija otro sector cuya longitud sea menor que 1, para que no rompa la conectividad [2] . Este tercer sector es nuevamente truncado por todos los países, como en el paso 5. En respuesta, se requiere que C 2 devuelva una parte del sector que conecta D 2 a C 1 , cuyo valor es igual al valor del tercero recibido. sector.

El corte propuesto por el país C 2 ahora contiene las siguientes partes: D 2 , un sector de longitud 1 que conecta D 2 con C 2 , y dos sectores cortos que no llegan al límite de D . El valor de esta construcción para C 2 es igual a , para los perdedores el valor es menor que , y el valor para otros ganadores no excede . ${\tfrac{1}{n))$ ${\tfrac{1}{n))$ ${\tfrac{1}{n))$

Este proceso continúa con los ganadores restantes hasta que solo quede un ganador.

Territorio ciertamente conectado

Si el territorio D es k -conectado con k finito , la división se puede hacer por inducción en k .

Si D es conexo y se puede dividir usando el protocolo del apartado anterior. ${\ estilo de visualización k = 1,}$

De lo contrario , indique el límite exterior de D como B 1 y los límites interiores como . ${\ estilo de visualización (k> 1)}$ ${\displaystyle B_{2},\puntos,B_{k))$

Encontramos la línea L que conecta la frontera exterior B 1 con la frontera interna B k , tal que para todos los países el valor de esta línea L es igual a 0. Esto se puede hacer en vista del siguiente argumento. Hay un número incontable de líneas que no se cortan por pares que conectan B 1 y B k contenidas en D . Pero su medida en D es finita, por lo que el número de líneas con medida positiva debe ser contable, y luego hay una línea con medida cero.

El conjunto es -conexo. Desglosémoslo recursivamente, luego asignemos L arbitrariamente a cualquier país con el que limita esta área. Esto no viola la equidad de la división, ya que el valor de L para todos los países es 0. $D\setminus L$ $(k-1)$

Véase también

Desafío de corte de pastel justo

Notas

↑ 12 Hill , 1983 , pág. 438–442.
↑ 12 Beck , 1987 , pág. 157–162.

Literatura

Hill TP Determinación de una frontera justa // The American Mathematical Monthly. - 1983. - T. 90 , núm. 7 . -doi : 10.2307/ 2975720 . — .
Beck A. Construyendo una frontera justa // The American Mathematical Monthly. - 1987. - T. 94 , núm. 2 . -doi : 10.2307/ 2322417 . — .
Para conocer otras soluciones al problema, consulte Webb WA Un algoritmo combinatorio para establecer una frontera justa // European Journal of Combinatorics. - 1990. - T. 11 , núm. 3 . — Pág. 301–304 . - doi : 10.1016/s0195-6698(13)80129-1 .