[kickout]

Buenos días, a ver si alguien puede ayudarme con el siguiente problema.

Supongamos, para simplificar, que tenemos las siguientes ternas de números (inventadas), podrían ser más ternas y con una cantidad de números mayor (los números en cada terna no se pueden repetir, aunque creo que el problema es el mismo independientemente de que se pudieran repetir o no):

A) 1, 4, 5, 6, 7
B) 2, 4, 6, 8, 9
C) 2, 3, 5, 7, 8
D) 2, 3, 4, 5, 6
E) 4, 5, 6, 7, 8

Ahora, tenemos que quitar números. Al quitar un número se quitará de todas las ternas en las que se encuentre.

Queremos hallar cuál es la cantidad mínima de números que hay que quitar (y cuáles son dichos números que hay que quitar) para que en cada terna halla una cantidad igual o menor a n-1 números (siendo n la cantidad de números en cada terna).

¿Hay alguna forma más eficiente de hallarlo que no sea ir calculando todas las combinaciones posibles de números a quitar y ver si se cumple nuestra condición?


(Este problema no sería muy complicado, el problema lo tengo cuando son más ternas y hay más números, por ello me pregunto si hay una forma más eficiente). Si algo no se entiende pueden preguntarme.

Gracias de antemano.
Un saludo.

[Ignacio Larrosa]

Buenos días, a ver si alguien puede ayudarme con el siguiente problema.

Supongamos, para simplificar, que tenemos las siguientes ternas de números (inventadas), podrían ser más ternas y con una cantidad de números mayor (los números en cada terna no se pueden repetir, aunque creo que el problema es el mismo independientemente de que se pudieran repetir o no):

A) 1, 4, 5, 6, 7
B) 2, 4, 6, 8, 9
C) 2, 3, 5, 7, 8
D) 2, 3, 4, 5, 6
E) 4, 5, 6, 7, 8

Ahora, tenemos que quitar números. Al quitar un número se quitará de todas las ternas en las que se encuentre.

Queremos hallar cuál es la cantidad mínima de números que hay que quitar (y cuáles son dichos números que hay que quitar) para que en cada terna halla una cantidad igual o menor a n-1 números (siendo n la cantidad de números en cada terna).

¿Hay alguna forma más eficiente de hallarlo que no sea ir calculando todas las combinaciones posibles de números a quitar y ver si se cumple nuestra condición?


(Este problema no sería muy complicado, el problema lo tengo cuando son más ternas y hay más números, por ello me pregunto si hay una forma más eficiente). Si algo no se entiende pueden preguntarme.

Gracias de antemano.
Un saludo.

Una cuestión terminológica: no estás trabajando con ternas, que tendrían 3 elementos, sino con quintuplas o quintetos. En general puedes hablar de tuplas o de n-tuplas para precisar el número de elementos.

En cuanto al problema, entiendo que lo que buscas es un algoritmo que permita reducir el tamaño de las n-tuplas retirando un mínimo de números. Podría pensarse que un algoritmo 'glotón' que fuese retirando los números más frecuentes solucionaría el problema, pero no es el caso siempre. Si se tienen varia n-tuplas muy similares y otra radicalmente distinta, podría ser incluso estrepitosamente ineficiente.

Pero si los sucesivos números a retirar se escogen de los más abundantes en las tuplas que aún tienen n elementos, creo que funcionaría. Sin más precisiones no parece posible dar una respuesta cerrada a la cantidad mínima de números a retirar.

Saludos,