Rompecabezas de cruce de río

Un rompecabezas de cruce de río es un tipo de rompecabezas cuyo objetivo es transportar objetos de una orilla a otra, generalmente en el menor número de viajes. La dificultad del rompecabezas puede deberse a restricciones sobre qué objetos o cuántos se pueden transportar al mismo tiempo, o qué objetos o cuántos se pueden dejar juntos de forma segura. ^{[ 1 ] [ 2 ]} El escenario puede variar estéticamente, por ejemplo, sustituyendo el río por un puente. ^{[ 2 ]} Los problemas de cruce de río más antiguos que se conocen aparecen en el manuscrito Propositiones ad Acuendos Juvenes ( Problemas para agudizar a los jóvenes ), tradicionalmente atribuido a Alcuino . Las copias más antiguas de este manuscrito datan del siglo IX; contiene tres problemas de cruce de río, incluyendo el problema del lobo, la cabra y la col, y el problema de los misioneros y los caníbales . ^{[ 3 ]}

El problema del lobo, la cabra y la col

El problema del puente y la antorcha

Soluciones a algunos rompecabezas representadas como líneas de tiempo

Entre los rompecabezas más conocidos que implican cruzar ríos se incluyen:

• El problema del lobo, la cabra y la col , en el que un lobo, una cabra y una col deben cruzar el río en un bote, pero ni la cabra y la col, ni el lobo y la cabra pueden estar solos juntos. El acertijo también puede formularse como el del zorro, el ganso y la bolsa de frijoles.
• El problema de los misioneros y los caníbales , en el que tres misioneros y tres caníbales deben cruzar el río, con la restricción de que en cualquier momento en que tanto misioneros como caníbales se encuentren en una orilla, los caníbales en esa orilla no pueden ser más numerosos que los misioneros. También se formula como el problema de los maridos celosos.
• El problema del puente y la linterna : cuatro personas llegan a un río de noche. Hay un puente estrecho, con capacidad para solo dos personas. Tienen una linterna y, como es de noche, deben usarla para cruzar el puente.
• Propositio de viro et muliere ponderantibus plaustrum . En este problema, que también aparece en Propositiones ad Acuendos Juvenes , un hombre y una mujer de igual peso, junto con dos niños, cada uno de la mitad de su peso, desean cruzar un río en una barca que solo puede soportar el peso de un adulto. ^{[ 4 ]}

Estos problemas pueden analizarse utilizando métodos de teoría de grafos , ^{[ 5 ] [ 6 ]} mediante programación dinámica , ^{[ 7 ]} o mediante programación entera . ^{[ 4 ]}

Dejar${\displaystyle G=(V,E)}$sea ​​un grafo no dirigido cuyo conjunto de vértices${\displaystyle V}$representa los elementos que el agricultor debe llevar y cuyo borde está${\displaystyle E}$consta de pares de elementos que entran en conflicto. Por ejemplo, si un vértice${\displaystyle v_{1}}$representa un ganso y${\displaystyle v_{2}}$la bolsa de frijoles, entonces los dos vértices estarían conectados ya que el ganso no puede dejarse en el mismo lado del río con una bolsa de frijoles. Nótese que las aristas no están dirigidas, ya que la naturaleza del conflicto entre los dos elementos no afecta el hecho de que no pueden dejarse en el mismo lado del río. El objetivo del problema es determinar el tamaño mínimo del bote para que un viaje sea factible; esto se conoce como el número de Alcuin de${\displaystyle G}$.

Consideremos un cruce de río exitoso en el que el agricultor primero lleva un subconjunto${\displaystyle V'}$de artículos al otro lado del río, dejando el resto${\displaystyle V\setminus V'}$artículos en la orilla. Debido a que el viaje es exitoso, no debe haber conflictos en los artículos que se dejaron en la orilla; es decir, en${\displaystyle G}$, no hay bordes en${\displaystyle E}$entre cualesquiera dos elementos de${\displaystyle V\setminus V'}$Esto implica que todos los bordes${\displaystyle E}$tener uno o ambos vértices en${\displaystyle V'}$, es decir, que${\displaystyle V'}$es una cubierta de vértices de${\displaystyle G}$Por lo tanto, el tamaño del barco debe ser al menos tan grande como el tamaño${\displaystyle \tau (G)}$de la cobertura mínima de vértices de${\displaystyle G}$; esto constituye un límite inferior para el número de Alcuin de${\displaystyle G}$:${\displaystyle {\rm {{Alcuino}(G)\geq \tau (G)}}}$.

Por otro lado, es posible completar un viaje exitoso con un tamaño de embarcación igual a${\displaystyle \tau (G)+1}$Esto se puede lograr exigiendo a los miembros${\displaystyle V'}$de una cobertura de vértice mínima que debe permanecer en el barco en todo momento; estos elementos numeran${\displaystyle \tau (G)}$y así dejar un espacio más en el barco. Porque no hay conflictos entre ninguno de los restantes${\displaystyle V\setminus V'}$Los artículos se pueden llevar al otro lado del río uno a uno en cualquier orden, ocupando el único espacio restante en el bote. Por lo tanto,${\displaystyle {\rm {{Alcuino}(G)\leq \tau (G)+1}}}$, formando un límite superior para${\displaystyle {\rm {{Alcuin}(G)}}}$. Combinando estos elementos, tenemos${\displaystyle \tau (G)\leq {\rm {{Alcuin}(G)\leq \tau (G)+1}}}$, es decir,${\displaystyle {\rm {{Alcuin}(G)=\tau (G)}}}$o${\displaystyle {\rm {{Alcuin}(G)=\tau (G)+1}}}$. ^{[ 1 ]}

Csorba, Hurkens y Woeginger demostraron en 2008 que determinar cuál de${\displaystyle {\rm {{Alcuin}(G)=\tau (G)}}}$o${\displaystyle {\rm {{Alcuin}(G)=\tau (G)+1}}}$El problema de la cobertura mínima de vértices es NP-difícil . ^{[ 6 ]} Debido a que el problema de la cobertura mínima de vértices es NP-completo , se deduce que calcular el número de Alcuin de un grafo${\displaystyle G}$es NP-difícil . Sin embargo, para ciertas clases de grafos, se cumplen resultados más fuertes. Por ejemplo, para grafos planares, determinar cuál de las dos relaciones se cumple se puede hacer en tiempo polinomial (aunque determinar cualquiera de las dos relaciones es más complejo).${\displaystyle {\rm {{Alcuin}(G)}}}$o${\displaystyle \tau (G)}$sigue siendo NP-difícil); para grafos bipartitos ,${\displaystyle {\rm {{Alcuin}(G)}}}$y${\displaystyle \tau (G)}$Ambos pueden calcularse exactamente en tiempo polinomial. ^{[ 6 ]}